階乗計算

n!の計算は、次のように定義できる。

$\left\{\begin{array}{ll} n! = n \times (n-1)! & (if \;\; n > 0) \\ 0! = 1 \end{array} \right.$

以上を再帰呼び出しで記述すると以下のようになる。 （そのまま実装すればよい）

long int kaijo( unsigned int n){

if( n > 0 ){

return( n * kaijo(n-1));

}

if( n == 0 ){

return(1L);

}

}

引数nが再帰呼び出しのたびにスタック上に積まれ、 再帰呼び出しからリターンするときには 逆にスタックから戻されていくことに注意せよ。 上記の関数では、引数が負にならないことを想定して、unsigned int型を使用している。また、返り値が大きくなることが予想されるのでlong int型にしてある。

この関数では、$0! = 1$が出口である。再帰呼び出しの引数が0になった時点で、 関数の値が1と定義されているので、これ以上は再帰呼び出しは行われず、 これまで来た道を逆戻りする。 再帰呼び出しにおけるスタックの積み上げ、積み下ろしの様子を図示すると、 図8.1のようになる。

Figure 8.1: 階乗の再帰呼び出しの様子

上記の階乗計算を呼び出すメインプログラムと、その実行結果を以下に示す。

#include <stdio.h>

void main(){

unsigned int n;

printf(”階乗計算結果 \n”);

for(n = 0; n <= 12; n++){

printf(”%2d! = %10ld\n”, n, kaijo(n));

}

}

階乗計算結果

0! = 1

1! = 1

2! = 2

3! = 6

4! = 24

5! = 120

6! = 720

7! = 5040

8! = 40320

9! = 362880

10! = 3628800

11! = 39916800

12! = 479001600