令和7年度 I-2-6

解説

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

3つの式で定義される再帰関数(アッカーマン関数)A(m,n)について、A(2,2)の値を求める問題。

解き方

① 定義どおりに小さい方から計算し、A(1,n)とA(2,n)の規則を見つける
② A(1,0)=A(0,1)=2、A(1,n)=A(1,n−1)+1 → A(1,n)=n+2。A(2,0)=A(1,1)=3、A(2,n)=A(1,A(2,n−1))=A(2,n−1)+2 → 3, 5, 7
③ A(2,2)=7(①)

正解が正しい理由

定義式を用いて段階的に計算する。まずA(1,n)=n+2となることが分かる(A(1,0)=A(0,1)=2、A(1,n+1)=A(0,A(1,n))=A(1,n)+1という漸化式からA(1,n)=n+2)。次にA(2,0)=A(1,1)=3。さらにA(2,n+1)=A(1,A(2,n))=A(2,n)+2という漸化式が成り立つため、A(2,n)=2n+3となる。したがってA(2,2)=2×2+3=7となり、①が正しい。

各選択肢について

• ① 定義式を順に展開して計算するとA(2,2)=7となり、これが正答。
• ② 8は計算過程で1回分の加算を余分に行うなど、途中の展開でずれが生じた場合に出やすい値であり、正しい計算結果とは一致しない。
• ③ 9はA(2,n)=2n+3の式でnを誤って3として計算した場合などに生じやすい値であり、正しい計算結果とは一致しない。
• ④ 10は再帰の展開を1段階多く、あるいは少なく行った場合に生じやすい値であり、正しい計算結果とは一致しない。
• ⑤ 11はA(m+1,0)=A(m,1)の適用を誤るなど、定義式の適用順序を間違えた場合に生じやすい値であり、正しい計算結果とは一致しない。

覚えるべきポイント

アッカーマン関数は非常に急速に値が増大する再帰関数として知られる。A(1,n)=n+2、A(2,n)=2n+3、A(3,n)=2^(n+3)-3のように、mの値ごとに閉じた式を導出してから計算すると効率よく求められる。