アッカーマン関数とは？あっかーまんかんすう
アッカーマン関数とは、2つの非負整数を引数に取り、再帰の深さが爆発的に増える関数。Ack(0,n)=n+1、Ack(m,0)=Ack(m-1,1)、Ack(m,n)=Ack(m-1,Ack(m,n-1)) と定義され、内側の呼出しの結果が外側の引数になる入れ子構造をもつ。原始再帰では表せない全域関数の例として知られ、値の増え方が極端に速いことから、再帰の理解を試す題材として繰り返し出題される。値を求めるときは定義の3本の式を機械的に当てはめ、内側から順に展開していくのが確実である。
最終更新：2026-10-07
この語が出る過去問を解く →具体例
Ack(1,3) を求めるには、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が小さいほうから順に確定させていく。Ack(4,2) は既に2万桁近い値になり、素直に計算することはできない。
試験での引っ掛け
外側から展開しようとして途中で行き詰まる誤りが定番で、内側の Ack(m,n-1) を先に確定させるのが正しい順序である。Ack(m,0) の場合に Ack(m-1,0) としてしまう誤りも多い（正しくは Ack(m-1,1)）。定義の3本目だけを見て「必ず引数が1つずつ減る」と考えないこと。
関連用語
出た過去問
出典：平成30年度 春期 高度試験 午前Ⅰ 問2（IPA）
非負の整数m、nに対して次のとおりに定義された関数Ack(m, n)がある。Ack(1, 3)の値はどれか。 Ack(m, n) = Ack(m-1, Ack(…
正解：5
要点：アッカーマン関数は定義に従い内側から順に展開する
m=0のときAck(0,n)=n+1であることを使って内側から順に展開する。Ack(1,0)=Ack(0,1)=2、Ack(1,1)=Ack(0,Ack(1,0))=Ack(0,2)=3、Ack(1,2)=Ack(0,Ack(1,1))=Ack(0,3)=4、よってAck(1,3)=Ack(0,Ack(1,2))=Ack(0,4)=5となる。
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。