【課題４−１１　再帰的関数】

＜再帰的呼び出しとは＞

ある関数から，自分自身とおなじ関数を呼び出すこと．あえて用いる必要もないが，アルゴリズムによっては必須な場合や，プログラムが簡潔になる場合がある．

＜再帰の流れ＞

（例）nの階乗を求める関数をつくる

n!は，nに(n-1)!をかける，と考えると，

long fact(int n) //nの階乗を求める関数

{ long f;

f = n * fact(n-1); // nに，再帰呼び出しで(n-1)!をかける

return f;

}

のような関数を書けば，次々と一つ少ない数の階乗を求めるためのルーチンにおりていき，階乗が計算できる．ただしこれだと終わりがないので

long fact(int n)

{ long f;

if (n > 0)

f = n * fact(n-1);

else

f = 1;

return f;

}

として，n=0の時にはそれ以上再帰呼び出しはせずに0!=1を返すようにする．以後は次々と戻っていって，最終的は始めに呼び出したfactがn!を返す．

＜関数とスタック＞

関数では，仮引数や関数内の変数をメモリ上のスタック領域に格納する．スタックは，入れるときには下から上に向かって積み上げ，出すときには上から下に向かって取り出す構造をしている．関数は呼ばれるたびにスタック領域に仮引数や変数を積み，returnするとその情報を破棄している．

再帰はどんどん深く自分自身と同じ関数を呼び続ける．たとえばn=100でn!を実行しようとするとスタックに101層積み上がる．スタック領域の大きさは処理系に依存しているので，再帰関数を使うときにはスタックオーバーフローに注意しなくではならない．

戻る