[C]アッカーマン関数で遊んでみる

アッカーマン関数というものがあります。

僕がはじめて知ったのはWebサンデーの巨大数を扱った漫画だったのですが、与える数が増加すると爆発的に大きな値を返す性質を持っているのだそうです。

今回はそのアッカーマン関数を使ってC言語で遊んでみます。

アッカーマン関数は以下のように定義されます。(Wikipedia)

\[Ack(m,n) = \begin{cases} n+1 & (m=0) \\
Ack(m-1,1) & (n=0) \\ Ack(m-1,Ack(m,n-1)) &otherwise \end{cases} \]

実装的に少し考えるのは、n≠0かつm≠0の場合にAck()を再起で呼び出すところですかね。

では実際にソースに起こしていきましょう。

#include <stdlib.h>

/*アッカーマン関数宣言*/
long long Ack(long long m,long long n);

void main(void)
{
	printf("Ack(3,3) = %lld\n",Ack(3,3));
	printf("Ack(3,4) = %lld\n",Ack(3,4));
	printf("Ack(3,5) = %lld\n",Ack(3,5));

	getchar();
}

long long Ack(long long m,long long n)
{
	long long ret = 0;
	if (m == 0)
	{
		return n + 1;
	}
	else if (n == 0)
	{
		return Ack(m - 1,1);
	}
	else
	{
		ret = Ack(m,n-1);
		return Ack(m-1,ret);
	}
}

実際にコーディングしてみると意外と簡単ですね。

main()からAck(3,3)、Ack(3,4)、Ack(3,5)の場合それぞれを計算して結果をprintf()するようにしています。最後にgetchar()して、ユーザーの入力町にしてコマンドプロンプトを閉じないようにしています。

結果はそれぞれ61、125、253でした。これだけだとアッカーマン関数の凄さはあまりわからないかもしれませんが、Ack(4,1)を計算させてみたら計算量が多すぎてダウンしました。