再帰呼び出し
Cで出来て、一昔前のBASICやFORTRRANでは真似できない機能のひとつに”再帰呼び出し”があります。
再帰呼び出しとは、関数の中で自分自身を関数として呼び出すことです。再帰呼び出しを使うと、数列を
求めるプログラムなどは美しく記述できます。
再帰呼び出しを使ったサンプルプログラムは再帰呼び出しショートプログラムにもあります。
１ 再帰呼び出し
再帰呼び出しは、階乗の計算や数列（等差数列や等比数列）を求める時に使うと、美しいコードになります。
もちろん、繰り返し処理（ for , while
）を用いても階乗の計算や数列を求めるプログラムは書けますが、
再帰を使った方が、見やすく簡潔なコードになります。
ただし、再帰呼び出しをかけるたびに、新しいスタック領域が必要になるため、メモリー使用量や、実行速度
の点では効率的とはいえません。また、再帰呼び出しが多すぎると、スタックオーバーフロー（スタック領域が
オーバーフロー）して、プログラムが無限ループにおちいったりしてしまいます。
再帰呼び出しに使う関数では、引数は、値渡しにしておいてください。当たり前のことですが。
２ 階乗の計算
あまりにも有名な例ですが、階乗の計算(1*2*3*....*n)を再帰呼び出しを使って書いてみましょう。
| #include <stdio.h> unsigned long fact(); main() { int n; printf("Nの階乗 Number: "); scanf("%d",&n); printf("\n"); printf("%dの階乗： %ld ",n,fact(n)); } unsigned long fact(n) int n; { if (n == 0) return(1); else return(n*fact(n-1)); } |
関数factでは、nが0の時は1を返し（0! = 1）、それ以外の時は
n*fact(n-1) を返します（n-1を引数として
自分自身を再度呼び出す）。
実行例です
| C:\C>fact Nの階乗 Number: 5 5の階乗： 120 C:\C>fact Nの階乗 Number: 10 10の階乗： 3628800 |
例えば3! を計算する時の関数の呼び出しは、以下のようになります。
fact(3) -> 3*fact(2)を返す -> fact(2) の呼び出し
fact(2) ->
2*fact(1)を返す ->fact(1)の呼び出し
fact(1)
-> 1*fact(0)を返す ->fact(0)の呼び出し
<---
1*fact(0) <- fact(0)=1
<---
2*fact(1) <--- fact(1)=1
<--- 3*fact(2) <-- fact(2)=2
fact(3)=6
３ 数列
それでは、もうひとつ数列の計算をしてみます。
F(1) = 5
F(n) = 2*F(n-1) + 5
という式で表される数列の計算です。
| #include <stdio.h> unsigned long f(); main() { int n; printf("数列 F(1)=5 F(N)=F(N-1)*2+5 Number: "); scanf("%d",&n); printf("\n"); printf("F(%d) ： %ld ",n,f(n)); } unsigned long f(n) int n; { if (n == 1) return(5); else return(2*f(n-1)+5); } |
以下、実行例です。
| C:\C>suretsu 数列 F(1)=5 F(N)=F(N-1)*2+5 Number: 4 F(4) ： 75 C:\C>suretsu 数列 F(1)=5 F(N)=F(N-1)*2+5 Number: 7 F(7) ： 635 |
ちなみにこの数列は、数学的に計算すると以下のようになります。
F(n) = 2*F(n-1) + 5
F(n) +5 =2(F(n-1) +5) = 2n-1(F(1)
+ 5) = 2n-1*10 - 5