アッカーマン関数

アッカーマン関数（アッカーマンかんすう、英: Ackermann function、独: Ackermannfunktion）とは、非負整数 m と n に対し、 によって定義される関数のことである。 与える数が大きくなると爆発的に計算量が大きくなるという特徴があり、性能測定などに用いられることもある。 また、数学的な意味として、原始再帰関数でないμ再帰関数の実例として有名である。これを（再帰呼出しのない手続き型の）プログラミング言語の言葉で言えば、アッカーマン数をプログラムで計算することはできるが、While文を使わずFor文のみでそれを計算することができない、ということになる。