再帰関数

2012年12月5日：C言語

関数の中でさらに同じ関数を呼び出す方法があります。

その方法が再帰関数です。

再帰関数を使うことで階乗のような計算を簡単なコードで実現できます。

ここでは、プログラム例を通じて再帰関数を学習します。

 

再帰関数の例として、階乗n!を計算するプログラムを作ってみましょう。

#include <stdio.h>
int func(int n);
int main(void){
    int n;
    printf("n=");
    scanf("%d",&n);
    printf("%d\n",func(n));
    return 0;
}
int func(int n){
    if(n==0)return 1;
    return n*func(n-1);
}

このプログラムを実行すると以下のようになります。

n=4
24

では出力例と同様にn=4を入力する場合を考えます。4は0でないので

func(4)=4*func(3)

を返します。func(3)は

func(3)=3*func(2)

となり、同様に

func(2)=2*func(1)

func(1)=1*func(0)=1*1

で、最終的に

func(4)=4*3*2*1*1=24

となるわけです。

フィボナッチ数列を計算する

再帰関数を使って、フィボナッチ数列を計算してみます。

フィボナッチ数列とは

　a_{n}=a_{n-1}+a_{n-2},n>1\\a_{0}=0,a_{1}=1

という数列です。具体的に書くと

0,1,1,2,3,5,8,13,…

となります。では、プログラムを書きます。

#include <stdio.h>
int func(int n);
int main(void){
	int n;
	printf("n=");
	scanf("%d",&n);
	printf("%d\n",func(n));
	return 0;
}
int func(int n){
	if(n<=1) return n;
	return func(n-1)+func(n-2);
}

定義にしたがった形で、すっきりかけますね。実行すると以下のようになります。

n=4
3

では、n=4で計算の流れを見ていきましょう。n=4だと

func(4)=func(3)+func(2)

となります。次に

func(3)=func(2)+func(1)

func(2)=func(1)+func(0)

となります。さらに進めると

func(2)=func(1)+func(0)

func(1)=1

func(1)=1

func(0)=0

もう少し計算すると

func(1)=1

func(0)=0

となります。以上のすべての式からfunc(4)=3と計算できます。

再帰関数における計算の無駄をメモって削除

計算して見てわかると思うのですが、1,2,4,…と指数関数的に計算数が増えます。ですから、func(100)を計算すると、2^{100}くらい計算しないといけないわけです。

これをもう少し改善する方法を考えてみましょう。

まず、先程の計算での無駄は、func(2)を2回、func(1)を3回、func(0)を2回と何度も計算している点にあります。

よって、これをすべて1回だけ計算するようにすれば、計算量を減らせるはずです。

では、プログラムを組んでみましょう。

#include <stdio.h>
int temp[1000];
int func(int n);
int main(void){
	int n,i;
	printf("n=");
	scanf("%d",&n);
	for(i=0;i<n;i++){
		temp[i]=0;
	}
	printf("%d\n",func(n));
	return 0;
}
int func(int n){
	if(n<=1) return n;
	if(temp[n]!=0)return temp[n];
	temp[n]=func(n-1)+func(n-2);
	return temp[n];
}

このプログラムの基本的な考え方は、「計算したらメモを取れ」です。

そして、計算する前にメモを見てあったらその値を使うわけです。

これで、一回計算したものは再び計算する必要がないのでかなり高速化されます。

例えば、func(100)なら以前のプログラムでは2^{100}回でしたが、今回の場合はfunc(100),func(99),func(98),…,func(1),func(0)と計算するので100くらいの計算でできます。

　2^{100}=(10^{3})^{10}=10^{30}

とざっくり見積もり、100と比べると雲泥の差ですね。

自分のプログラムが無駄な計算していないかを常に考えると、あなたのプログラミングスキルは一歩上の段階へと移ることができます。

著者：安井 真人(やすい　まさと)

TOP