課題７　「フィボナッチ数(再帰処理)」

内容

　　41番目のフィボナッチ数fib(41)を、再帰処理を使う場合と使わない場合とで求めよ。

	フィボナッチ数：fib(n)=fib(n-1)+fib(n-2)  (n≧2)
			fib(0)=0 , fib(1)=1

　　※ fib(0)は「0番目」のフィボナッチ数とする。

　　※ 再帰処理を行う場合の関数 fib1(n) と、行わない場合の関数 fib2(n) を作成し、
　　　 ひとつのプログラムにまとめること。

　　※ fib1(n)とfib2(n)の出力の型は integer とする。

入力

　　今回の課題では、入力は無くても構わない。
　　例えば、以下のように定数として処理してよい。



　　const
	N = 41;

　　{～関数を書く～}

　　begin
　　　　writeln('再帰あり fib(',N:0,')=',fib1(N));　
　　　　writeln('再帰なし fib(',N:0,')=',fib2(N));　
　　end.



　　任意のフィボナッチ数を出力したい場合は、
　　n番目のフィボナッチ数を意味するnの値を入力とせよ。

　　但し、今回の課題ではフィボナッチ数を Integer型 で作成する為、
　　n ≧ 47 の数値を与えるとオーバーフローする。

	Integer型の値域：-2147483648～2147483647
	fib(47) = 2971215073

出力

　　出力は以下の2つとする。

	・再帰処理(有)で求めた41番目のフィボナッチ数(fib(41))
	・再帰処理(無)で求めた41番目のフィボナッチ数(fib(41))

　　再帰処理を使用する方は、出力に時間がかかる。(fib(41)で約10秒)

実行

　　入力を設けなかった場合は、コンパイルしたプログラムをそのまま実行すればよい。
　　入力を設けた場合は、n=41と入力してフィボナッチ数を求めよ。

ヒント

再帰的プログラム

　　再帰処理の方法は、恐らく他の演習で学習済みだと思うが、
　　復習の意味も込めて簡単に説明しておく。必要ない学生は読み飛ばして課題を進めてよい。

　　再帰処理とは、簡単に言えば「定義した関数の中で、自分自身を関数として呼び出す」処理のことを指す。

　　例えば、「階乗の計算」を行う関数を作成しようとする。
　　階乗の計算は一般的に式(1)のようにして解く。

　　　　n! = n * (n-1) * (n-2) * … * 1		(1)

　　式(1)をプログラムに実装すると、以下のようなfor文を使用した関数になる。



　　function fac2(n : integer) : integer;　
　　var
	i , sum : integer ;
　　begin
	sum := 1;
	for i := 1 to n do
		sum := sum*i ; 
	fac2 := sum;
　　end;



　　ここで、階乗の計算式を式(2)のように変形する。

	n! = n * (n-1)!				(2)

　　これは、例えば5の階乗を求める時、4の階乗の解が分かっていれば
　　式(3)のようにして解を求めることができることを意味する。

	5! = 5 * 4!				(3)

　　4の階乗の解が分からない場合は、3の階乗の解から求め、
　　3の階乗の解が分からない場合は、2の階乗の解から求め、
　　2の階乗の解が……

　　と徐々に掘り下げていけば、

　　0の階乗の解は1である。

　　という最も単純な解にたどり着く。
　　ここから、逆順に処理を戻っていけば、5の階乗の解を導き出すことができる。

	5! = 5 * 4!
	4! = 4 * 3!
	3! = 3 * 2!
	2! = 2 * 1!
	1! = 1 * 0!
	0! = 1

	1! = 1 * 1 = 1
	2! = 2 * 1 = 2
	3! = 3 * 2 = 6
	4! = 4 * 6 = 24
	5! = 5 * 24 = 120

　　このような階層的な処理をプログラムに実装すると、以下のようになる。



　　function fac1(n : integer) : integer;　
　　var
	int : integer;
　　begin
	if (n=0) then
		fac1 := 1
	else
		fac1:= n * fac1(n-1);
　　end;



　　赤字の「自分自身の関数を呼び出す」部分が再帰処理である。
　　再帰処理を行う際に重要になってくるのが、青字で示した初期条件である。
　　初期条件を指定しておかないと、再帰処理は潜ったっきり帰ってこなくなるので注意すること。

出力例

　　入力を赤字で示した。



　　n = 10
　　再帰あり fib(10)=55　
　　再帰なし fib(10)=55　


　　ただし、先に述べたとおり、今回の課題では入力はなくても構わない。