令和7年度 III-7

解説

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

アッカーマン関数の形の再帰関数について、f(1,3)の値を求める問題。

解き方

① m=0ならn+1を返す。それ以外は、内側のf(m, n−1)を先に計算して外側に戻る
② f(1,0)=f(0,1)=2 → f(1,1)=f(0,2)=3 → f(1,2)=f(0,3)=4 → f(1,3)=f(0,4)=5(f(1,n)=n+2)
③ 5(①)

正解が正しい理由

関数の定義は、f(0,n)=n+1、f(m,0)=f(m-1,1)、f(m,n)=f(m-1, f(m,n-1)) である。これはアッカーマン関数である。f(1,0)=f(0,1)=2。f(1,1)=f(0,f(1,0))=f(0,2)=3。f(1,2)=f(0,f(1,1))=f(0,3)=4。f(1,3)=f(0,f(1,2))=f(0,4)=5。したがって f(1,3)=5 であり、①が正しい。一般に f(1,n)=n+2 となる。

この問題で必要な基礎

■ 再帰呼び出しの読み方
この関数fは、自分自身(f)を中で呼び出しています(再帰)。f(m, n−1)のような内側の呼び出しの値が分からないと外側が計算できないので、nが0になるまで内側へ進み、分かった値を使って外側へ戻りながら計算します。
・mが0なら、すぐにn+1を返す
・nが0なら、f(m−1, 1)を計算して返す
・それ以外は、まずf(m, n−1)を計算し、その結果をkとしてf(m−1, k)を返す
正解の理由では、f(1,0)→f(1,1)→f(1,2)→f(1,3)と、分かった値を順に使って外側へ戻る形で計算しています。

各選択肢について

• ① f(1,3)=f(0,f(1,2))=f(0,4)=5で、これが正答。
• ② 6は、f(1,n)=n+3と誤って計算した場合の値である。
• ③ 7は、f(2,2)などの値であり、f(1,3)ではない。
• ④ 8は、f(1,3)の値ではない。
• ⑤ 9は、f(2,3)=2×3+3=9の値であり、f(1,3)ではない。

覚えるべきポイント

アッカーマン関数 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 で、mが増えると急激に増大する。