パソコン活用研究シリコンバレー(C、C++、の活用研究)

再帰呼び出し

Cで出来て、一昔前のBASICやFORTRRANでは真似できない機能のひとつに”再帰呼び出し”があります。
再帰呼び出しとは、関数の中で自分自身を関数として呼び出すことです。再帰呼び出しを使うと、数列を
求めるプログラムなどは美しく記述できます。


1 再帰呼び出し
再帰呼び出しは、階乗の計算や数列(等差数列や等比数列)を求める時に使うと、美しいコードになります。
もちろん、繰り返し処理( for , while )を用いても階乗の計算や数列を求めるプログラムは書けますが、
再帰を使った方が、見やすく簡潔なコードになります。
ただし、再帰呼び出しをかけるたびに、新しいスタック領域が必要になるため、メモリー使用量や、実行速度
の点では効率的とはいえません。また、再帰呼び出しが多すぎると、スタックオーバーフロー(スタック領域が
オーバーフロー)して、プログラムが無限ループにおちいったりしてしまいます。

再帰呼び出しに使う関数では、引数は、値渡しにしておいてください。当たり前のことですが。


2 階乗の計算
あまりにも有名な例ですが、階乗の計算(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


3 数列
それでは、もうひとつ数列の計算をしてみます。
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

TopPage