再帰的定義
ある物を定義するとき、定義したい「物」を利用して定義する場合があります。これを再起的な定義と呼びます。組み合わせ数やベジェ曲線も再帰的に定義されます。再起的定義された「物」を処理するには、再帰的プログラミングが便利な場合があります。
再帰的プログラミングは単純な繰り返しで置き換わる場合は効率が悪くなりますが、少し複雑な再帰処理は高度なプログラム手法を提供してくれます。
フィボナッチは再帰的に定義される数列で、面白い性質をもっています。
階乗関数の再帰的定義
-
階乗関数の再帰的定義
階乗関数 fact(n) は次のように再帰的に定義できます．
fact(n) =1 : n=0 =n * fact(n-1) : n>0
これで，すべてのnに対する fact(n) の値が求められます．たとえば
fact(2) = 2*fact(1) = 2*1*fact(0) = 2*1*1 = 2
このように，fact(n) を fact(m) (m<n) の定義をそのまま用いて定義することができます．
-
再帰的プログラム手法
次のC言語の関数 Fact(N) は n! を計算します。先の定義に従いそのままプログラムを書くとつぎのようになります。
long Fact(long N) { long L; printf("in Fact(%d)\n", N); if (N == 0) return(1); else { L=N*Fact(N-1); printf("return fact=%ld\n",L); return(L); } } void main() { int Num; printf("number:"); scanf("%d",&Num); printf("\nfact(%d)= %ld \n",Num,Fact(Num)); }Fact(N) で Fact(N-1) を呼び出しています。このように、自分自身を呼び出すことを再帰呼びだしと言います。関数の先頭のlongは倍精度の整数を値として返すことを指示します。long 型の整数は printf の書式では"%ld"とします。n!の値は急激に大きくなりますから、n に大きな値を与えるとオーバーフロ-して正しい値が求められなくなります。
以下はルビーによるプログラム例です。ARGV[0] はコマンドラインからの引数で、to_i は整数への変換を意味します。
#!/usr/bin/ruby #fact.rb def fact(n) return 1 if n ==0 f = 1 while n > 0 f *= n n -= 1 end return f end print fact(ARGV[0].to_i), "\n"
-
実行例
n=5の場合のC言語の実行例を示します。Fact(5) の実行で Fact(4) を呼び出します。同様にFact(0) まで順に同じ関数が呼び出されますが、Fact(0)では 値1 で計算が終了します。すると、Fact(0) の結果を用いてFact(1) の結果がでます。同様に Fact(4) の結果を用いてFact(5) の結果がでます。
number: 5
in Fact(5)
in Fact(4)
in Fact(3)
in Fact(2)
in Fact(1)
in Fact(0)
return fact=1
return fact=2
return fact=6
return fact=24
return fact=120
fact(5)= 120
-
-
演習
１からnまでの和を求める関数 Sum(n) を再帰的に定義してください。
組み合わせ数の再帰的定義
-
再帰的定義
先に、紹介しましたが、組み合わせ数 ｎＣｒ は次のように再帰的に定義されます。
ｎＣｒ＝ｎ-1Ｃr＋ｎ-1Ｃr-1
=1 r=1 または n=r
この定義を利用すると、再帰的に組み合わせ数を計算できます。
-
プログラム
再帰処理による組み合わせ数の計算例です。
//再帰による組み合わせ数 #include "stdafx.h" #include "stdio.h" //組み合わせ数の計算 int combi(int n,int r) { if(n==0) return 1; else if(r==0) return 1; else if(n==r) return 1; else return combi(n-1,r) + combi(n-1,r-1); } int _tmain(int argc, _TCHAR* argv[]) { int n,r; do{ printf("input n,r : "); scanf("%d,%d",&n,&r); if(n<r) printf("??\n"); else printf("%d\n",combi(n,r)); }while (n > 0); return 0; }
-
実行例
input n,r : 4,1
4
input n,r : 4,2
6
input n,r : 4,3
4
input n,r : 4,4
1
input n,r : 4,0
1
input n,r : 6,3
20
input n,r : 6,4
15
input n,r : 6,7
??
フィボナッチ数列
-
再帰処理が有効な場合
先の階乗計算は、単純な繰り返しでプログラムができます。次の場合はどうでしょう。
フィボナッチ数列は次にように再帰的に定義されます。
Ｆ(1)＝Ｆ(2)＝１， Ｆ(n)＝Ｆ(n-1)＋Ｆ(n-2) ｎ≧３の時、
このＦ(n)の計算は、単純な繰り返しでは計算できません（後で計算式を紹介します）。
-
プログラム（ANSI)
再帰処理をするプログラムは簡単です。以下はJava言語で定義をそのままプログラムしています。
long Fib(int N) { long L; //printf("in Fib(%d)\n",N); if (N==1 || N==2) return(1); else { L=Fib(N-1)+Fib(N-2); // printf("return Fib(%d)=%ld\n",N,L); return(L); } }
-
実行例
- n=4
n=4の場合の処理の流れを見てみましょう。Fib(4)を計算するにはFib(3)とFib(2)の計算が必要です。このためには Fib(2) と Fib(1) が必要ですがこの値は１と定義されています。これで、Fib(3)の値が計算され、return Fib(3)=2 が記録されます。次にFib(2)の値を求め、この二つを合計して、return Fib(4)=3 が記録されます。
Fib(4)の計算のため、Fib()の呼び出しが5回起こっています。
number:4
in Fib(4)
in Fib(3)
in Fib(2)
in Fib(1)
return Fib(3)=2
in Fib(2)
return Fib(4)=3
Fib(4)= 3
- n=5
同様に、Fib(5) の計算課程を示します。
in Fib(5)
in Fib(4)
in Fib(3)
in Fib(2)
in Fib(1)
return Fib(3)=2
in Fib(2)
return Fib(4)=3
in Fib(3)
in Fib(2)
in Fib(1)
return Fib(3)=2
return Fib(5)=5
Fib(5)= 5
- n=4
-
階段の昇り方
n段の階段を1段、または2段で上がる方法はフィボナッチ数になります。n段を上がるには、(n-1)段を上り最後に１段上るか、(n-2)昇り最後に2段を上ることになります。したがって、n段上がり型は
F(n) = F(n-1) ＋ F(n-2)
となります。
これを、組み合わせで考えますと、全部1段づつ上る場合（2段とびなし）は1通りで nC0、一度だけ2段上がる場合は n-1C1、
2度2段上がりする場合、n-2C2となります。
したがって、次の関係が成立します。
F(n)=Σ(p=0,(n-1)/2)n-pCp
たとえば、F(6) = 6C0 + 5C1 + 4C2 + 3C3 です。
-
一般解
フィボナッチ数の一般解は次のように計算できます。
F(0)=0,F(1)=1;
証明
数学的帰納法で証明します。
n乗される項を a,b とします。このとき、a・b=-1、a+b=1、となります。
これを利用すると、以下のように証明出来ます。
f(k+1) = f(k) + f(k-1)
=(ak-bk)/√5 + (ak-1 -bk-1)/√5
=(ak-bk)/√5 +(-bak + abk)/√5 (ab=-1)
=((1-b)ak - (1-a)bk)/)/√5
=(ak+1 -bk+1)/√5（a+b=1)）
■
プロジェクト
-
フィボナッチ数列の計算
下はJavaで作成したアプレットプログラムです。上のエディットボックスに計算する値を入れ計算のボタンを押すと、結果が下のエディットボックスに入ります。
-
ソース
以下はJavaでプログラムした例です。
//フィボナッチ数列の計算 //Fibs.java import java.awt.*; import java.awt.event.*; import java.applet.*; public class Fibs extends Applet { int num; private TextField textField1 = new TextField(); private Button button1 = new Button(); private TextField textField2 = new TextField(); //アプレットの初期化 public void init() { try { jbInit(); } catch(Exception e) { e.printStackTrace(); } } //コンポーネントの初期化 private void jbInit() throws Exception { textField1.setText("3"); textField1.setBounds(new Rectangle(28, 28, 97, 21)); this.setLayout(null); button1.setLabel("計算"); button1.setBounds(new Rectangle(43, 67, 77, 25)); button1.addActionListener(new java.awt.event.ActionListener() { public void actionPerformed(ActionEvent e) { button1_actionPerformed(e); } }); textField2.setText("textField2"); textField2.setBounds(new Rectangle(27, 109, 107, 25)); this.add(textField1, null); this.add(button1, null); this.add(textField2, null); } //計算ボタンが押された void button1_actionPerformed(ActionEvent e) { num=Integer.parseInt(textField1.getText());//数値をnumに読み込む textField2.setText(Long.toString(Fib(num)));//Fib(num)を表示する } //フィボナッチ数列の計算 long Fib(int N) { long L; //printf("in Fib(%d)\n",N); if (N==1 || N==2) return(1); else { L=Fib(N-1)+Fib(N-2); // printf("return Fib(%d)=%ld\n",N,L); return(L); } } }このファイルを Fibs.java で保存します。コンパイルは、コマンドプロンプトで
javac Fibs.java
で行います。ファイルの前に、ファイルパスが必要です。コンパイルすると、Fibs.class ファイルが生成されます。
実行するHTMLファイルは以下のようになります。
<html> <head> <meta http-equiv="Content-Type" content="text/html; charset=Shift_JIS"> <title> HTML テストページ </title> </head> <body> フィボナッチ数列の計算Fibs<br> <applet codebase = "." code = "Fibs.class" name = "TestApplet" width = "200" height = "150" > </applet> </body> </html>
これを、Fibs.class と同じフォルダに保存して、ダブルクリックします。ブラウザが立ち上がり、実行できます。
課題
-
コンパイル
ソースファイルを作成し、Fibs.java ファイルとして保存します。
コマンドプロンプトウインドウを立ち上げ、ファイルを保存したフォルダに ｃｄ します。
コマンドプロンプトで、javac Fibs.java でコンパイルします。
Fibs.classファイルが生成されます。
-
実行
HTMLファイルを作成しブラウザでアプレットを実行してください。
実行画面のハードコピーを印刷して提出してください。