6-4 再帰呼び出し

C言語の関数では、内部で自分自身を呼び出しすることができます。これを、再帰呼び出しと言います。

#include <stdio.h>
int fact(int n){
	if (n==1||n==0) return 1;
	else return n*fact(n-1);
}
int main(void){
	printf("5!=%d\n",fact(5));
	return 0;
}

実行結果

5!=120

このプログラムでは関数factの中でfactを呼び出しています。

関数factはnの階乗を計算します。階乗は、1から自身までの整数の積のことです。

1!=1

2!=1×2

3!=1x2x3

n!=1x2x…xn

階乗の定義より、正の整数nに対してn!=nx(n-1)!と表せます。

5!を計算するためにfact(4)を呼び出し4!を計算します。4!を計算するためfact(3)が呼び出されます。このように自分自身と同じ関数が何回も呼び出されます。

#include <stdio.h>
int fact(int n){
	int ans;
	printf("fact(%d)呼び出されました。\n",n);
	if (n==1||n==0) ans=1;
	else ans=n*fact(n-1);
	printf("fact(%d)が終了します。%dをreturnします\n",n,ans);
	return ans;
}
int main(void){
	printf("5!=%d\n",fact(5));
	return 0;
}

実行結果

fact(5)呼び出されました。
fact(4)呼び出されました。
fact(3)呼び出されました。
fact(2)呼び出されました。
fact(1)呼び出されました。
fact(1)が終了します。1をreturnします
fact(2)が終了します。2をreturnします
fact(3)が終了します。6をreturnします
fact(4)が終了します。24をreturnします
fact(5)が終了します。120をreturnします
5!=120

再帰呼び出しを何万回もすると関数の引数のデータが溢れてプログラムが停止する場合があります。(スタックオーバーフローと言います。)そのため膨大な数の処理をする場合は再帰呼び出しをしない方がいいです。

まとめ

関数の中で自分自身と同じ関数を呼び出すことを再帰呼び出しといいます。

再帰呼び出しをするときは、スタックオーバーフローに注意する。