おはようございます(22時)
現在就職活動や卒研でようやくひと段落し，なんとか落ち着きを取り戻したいしかずです．
今回もまたもや巨大数の記事です．
最近はシス研の巨大数の人になりつつありますが，実際そんなことはないです．

今回の記事では，再帰関数の概要，再帰関数を用いた巨大数の制作方法，および巨大数を作るうえでの再帰関数を紹介したいと思います．

再帰関数ってなあに

再帰関数とは，関数内で自分を呼び出す関数のことです．
（ここで久々にプログラムプログラムしてる記事を書いてることに気づいた顔）
再帰関数はプログラム等でたびたび見かけることがあると思います．
たとえば，10000以下までのフィボナッチ数列を出力するコードをwhile()ループだけ，再帰関数で書くと以下のようになります．（あまりコードを書くのは上手くないのでご容赦ください）

whileループ

#include <stdio.h>

int main(){

	int x0 = 0, x1 = 1;//フィボナッチ数の計算に用いる．出力時は交互に出力，ネーミングは許して
	int result;//計算結果
	int count;//計算回数

	printf("000 %5d\n001 %5d\n", x1, x2);//フィボナッチ数列の最初の2項が0,1となるのは自明
	count = 3;//すでに2つ出力しているので3からスタート
	while (1){

		result = x1 + x2;
		if (result < 10000) break;//10000より大きくなると強制的にループを終了させる
		printf("%03d %5d\n", count, result);
		x1 = x2;//後ろの項の数を前の項に移動
		x2 = result;//新たにできたフィボナッチ数を格納
		count++;

	}
	return 0;
}

再帰関数

#include <stdio.h>

int addition(int);//計算をする関数

int main(){

  int n = 1;
  while (1){
    if (addition(n) < 10000)
        printf("%03d %5d\n", n, addition(n));
    else break;//求めた値が10000より大きくなると強制的にループを終了させる
    n++;
  }
  return 0;
}

int addition(int x){
  switch (x){
  case 0:
    return 0;
  case 1:
    return 1;//フィボナッチ数列の最初の2項が0,1となるのは自明
  default:
      return addition(x - 2) + addition(x - 1);//2つ前の要素と1つ前の要素を再帰的に呼び出し足している
  }
}

どちらのほうが効率が良いだとか，プログラムが書きやすいだとか，の話はあまりよくわかりません．
今回の記事はプログラムの書きやすさを目的とした記事ではないので，こんなものがあるんだなー程度で見ていただけたら幸いです．

フィボナッチ数()は，以下のように定義されます．

   

   

   

: その他

ここで，が2以上の時は1つ前の()と2つ前の()を再帰的に呼び出して計算していることがわかります．
このように再帰的に自分自身を呼び出して計算する関数のことを再帰関数と呼びます．

アッカーマン関数

時間の都合上今回はアッカーマン関数のみの紹介となります．アカーーーーーーーン↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓ｗｗｗｗｗｗｗｗｗではありません．

アッカーマン関数の定義

アッカーマン関数は引数を2つ要します．

   

   

   

一見何ともないように見えますが，引数に入れる数によっては極端に巨大化します．
実際に計算してみましょう．
例としてアッカーマン関数に引数(2,1)を入れて計算してみます．
計算過程および結果は以下のようになります．

この調子でに引数(4,1)を代入して計算してみましょう．

 

めんどくさいので途中経過は省略しています．ご了承ください．（時間が有り余ってる方は最後まで解いてみてください）

引数のが2→4となるだけで値が急上昇しました．なお，が6以上になると10進法では理論上記述不可能な値となってしまいます．
このアッカーマン関数を用いた巨大数もいくつか考案されており，現在も多くの数学者に愛用されています．
関数で数が非常に膨大に巨大化するの，ロマンありますよね…私は好きです．

あまり時間が無くなってしまったのでここで終わりたいと思いますが，最後にアッカーマン関数を再帰関数を用いたC言語で書いたソースコードを以下に示します．最後までお読みいただきありがとうございました．

#include <stdio.h>
int ackermann(int,int);

int main(){

    int m,n;

    printf("m=?\n" );
    scanf("%d",&m );
    printf("n=?\n" );
    scanf("%d",&n );

    printf("Ack(%d,%d) = %d\n", m, n, ackermann(m,n));
}

int ackermann(int m, int n){
  if(m == 0){
    return n + 1;
  }else if(n == 0){
    return ackermann(m-1,1);
  }else{
    return ackermann(m-1,ackermann(m,n-1));
  }
}

※なお，このプログラムは理論上は計算できますが計算量の関係上動作しない(など)ことがあります．ご了承ください．
それではこの辺で失礼いたします．次回（あるのかな？）こそはもっと詳しく書きたいと思います．お疲れ様でした．
明日の記事はchatotoさん担当です．お楽しみに．