アッカーマン関数とは？あっかーまんかんすう
アッカーマン関数とは、非負整数2つを引数にとり、Ack(0,n)=n+1、Ack(m,0)=Ack(m-1,1)、Ack(m,n)=Ack(m-1,Ack(m,n-1)) の3式で定義される全域関数。第3式は外側の引数が内側の呼出し結果になるため、値を求めるには必ず内側から順に確定させる。原始再帰では表せない例として、再帰の展開順を追えるかを試す題材になる。
最終更新：2026-10-06
この語が出る過去問を解く →背景
再帰の理解度は、階乗やフィボナッチのように引数が1ずつ減る関数では測れない。それらは繰返しに書き換えても同じ手数で済むからである。アッカーマン関数は引数の減り方が入れ子の結果に依存するので、定義式を機械的にたどれるかどうかで正誤が分かれる。科目Aでこの種の関数が出るのは、公式の暗記ではなく適用手順を持っているかを見たいためである。
具体例
ヒルベルトの弟子ヴィルヘルム・アッカーマンが1920年代に示した関数で、Ack(1,3) は Ack(1,0)=Ack(0,1)=2、Ack(1,1)=Ack(0,2)=3、Ack(1,2)=Ack(0,3)=4 と m を固定して n を下から積み上げ、最後に Ack(0,4)=5 と求まる。Ack(4,2) は2万桁近くになり、素直に走らせるとスタックを使い切って止まる。
試験での引っ掛け
外側から展開すると内側の引数が未確定のまま行き詰まるので、手を動かす順序は内側の Ack(m,n-1) が先である。第2式を Ack(m-1,0) と書き間違える誤りも定番で、正しくは Ack(m-1,1)。第3式だけを見て引数が単調に減ると思い込まないこと。
関連用語
出た過去問
出典：平成30年度 春期 応用情報技術者試験 午前 問5（IPA）
非負の整数m, nに対して次のとおりに定義された関数Ack(m, n)がある。Ack(1, 3)の値はどれか。Ack(m, n)＝Ack(m-1, Ack(m,…
正解：5
要点：アッカーマン関数は定義式を素直に再帰展開して求める
定義に従って展開する。まずAck(1,0)＝Ack(0,1)＝2、続いてAck(1,1)＝Ack(0,Ack(1,0))＝Ack(0,2)＝3、Ack(1,2)＝Ack(0,3)＝4、Ack(1,3)＝Ack(0,4)＝5となる。m＝1のときはAck(1,n)＝n＋2という規則になることも確認できる。
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。