平成27年度 III-15

解説

この問題で問われていること

アッカーマン関数の再帰呼出しを、順にたどって値を求める問題。

解き方

① 再帰関数は内側のf(…)から順に計算する。f(1,n)=n+2になることに気付くと早い
② f(2,0)=f(1,1)=3。f(2,1)=f(1, f(2,0))=f(1,3)=5
③ 5(②)

正解が正しい理由

f(2,1)=f(1,f(2,0))。f(2,0)=f(1,1)(y==0の規則)。f(1,1)=f(0,f(1,0))。f(1,0)=f(0,1)=1+1=2。よってf(1,1)=f(0,2)=3。したがって、f(2,0)=3。f(2,1)=f(1,3)。f(1,3)=f(0,f(1,2))。f(1,2)=f(0,f(1,1))=f(0,3)=4。したがって、f(1,3)=f(0,4)=5。f(2,1)=5となり、②が正しい。なお、一般に、f(1,n)=n+2、f(2,n)=2n+3である。

この問題で必要な基礎

■ 再帰呼び出しの読み方
この関数fは、自分自身(f)を中で呼び出しています(再帰)。f(x, y−1)のような内側の呼び出しの値が分からないと外側が計算できないので、yが0になるまで内側へ進み、分かった値を使って外側へ戻りながら計算します。
・xが0なら、すぐにy+1を返す
・yが0なら、f(x−1, 1)を計算して返す
・それ以外は、まずf(x, y−1)を計算し、その結果をkとしてf(x−1, k)を返す
小さい値(f(1,0)、f(1,1)など)から順に求めておくと、何度も同じ計算をせずに済みます。

各選択肢について

• ① 4は、途中のf(1,2)の値で、最終的な戻り値ではない。
• ② f(2,1)=f(1,3)=5で、正しい(f(2,n)=2n+3より、2×1+3=5)。これが正答。
• ③ 6は、この計算では得られない。
• ④ 7は、f(2,2)の値(2×2+3)で、f(2,1)ではない。
• ⑤ 8は、この計算では得られない。

覚えるべきポイント

アッカーマン関数A(m,n): A(0,n)=n+1、A(m,0)=A(m−1,1)、A(m,n)=A(m−1,A(m,n−1))。A(1,n)=n+2、A(2,n)=2n+3。