アルゴリズム講座―再帰関数

再帰関数とは、自分自身を関数定義内で再び呼び出す関数のことです。言葉だと分かりにくいですので、代表的な例をいくつか挙げたいと思います。

例1:階乗を求めるプログラム

n!を求めるプログラムです。普通に考えれば、繰り返し処理をしてやることでプログラムを組めますが、再帰関数を使って組むときは次のように考えます。

n!はn×(n-1)!である
(n-1)!は(n-1)×(n-2)!である
…
2!は2×1!である
1!は1である

という風に考えて、自分自身を呼び出していきます。次のようになるでしょう(long intは整数型の大きなものです)。

long factorial(int n){
	long temp;
	if(n==0||n==1) return 1;
	temp = n*factorial(n-1);
	return temp;
}

重要なのは「factorial(n-1)」です。引数を(n-1)として自分を再帰的に、つまり自分で自分の関数を呼び出しています。

例2:フィボナッチ数列を求める

フィボナッチ数列Fnは、

という風に、n番目の数列の項に対し、n-1番目とn-2番目の項を足したものという風に定義されます。ここから、次のようにプログラムを組むことで任意番目のフィボナッチ数列を求めることができます。

int fibonacci(int n){
	if(n=0)return 0;
	if(n=1)return 1;
	return fibonacci(n-1)+fibonacci(n-2);
}

例3:一般の漸化式の項を求める

例1,例2のように、前の項が決まることで次の項が決まる数列の定義の仕方を漸化式と言います。ここでは、

となる数列a_nを求めてみましょう(これの一般項の求め方は高校数学Bで習ってください)。

int n_seq(int n,int a,int p,int q){
	if(n<=0) return -1;
	if(n==1) return a;
	return p*n_seq(n-1,a,p,q)+q;
}

例3は少し難しい例でしたが、このような形で再帰関数は使うことが出来ます。しかし、計算量的に考えると普通のやり方のほうが優れていることも多いです。