再帰

ページトップへ　一つ上へ

ポイント


再帰、フィボナッチ数列



さてさて、今回もアルゴリズムの基礎を説明していきます。
今回は再帰という物について学びます。

まず再帰というのは、例えばｎ次のものを定義する為に
ｎ−１次のものを用い、それを定義する為に
ｎ−２次のものを用います。
このようにより低次のものを用いて定義するような構造を
再帰といいます。

さて再帰の練習問題として、フィボナッチ数列というものがあります。
フィボナッチ数列というのはフィボナッチさんが発見しました。
具体的な例として、

１　１　２　３　５　８　１３　２１　３４　５５　８９　１４３・・・

というような数列をいいます。
第ｎ項を求めるには第ｎ−１項と第ｎ−２項を加えたものであります。
さて、このようなフィボナッチ数列を再帰を使って求めてみましょう。
以下がメインのプログラムです。 
function fibonacci

%
%　フィボナッチ数列（メイン）
%
%

for i = 1 : 20
    f=fib(i);
    fprintf('%2d： %1d\n',i,f);
end

第２０項目までフィボナッチ数列を求めていきます。
ここで、fib関数が呼び出されて、その結果を表示しています。
fib関数は以下のようになります。 
function f=fib(i)

%
%　フィボナッチ数列（処理）
%
%

if i <= 2
    f=1;
else
    f=fib(i-1)+fib(i-2);
end

iが１と２の時の値は１となります。
それ以上の場合はi-1とi-2の加算で求めていきます。
実行結果は以下になります。
 1： 1
 2： 1
 3： 2
 4： 3
 5： 5
 6： 8
 7： 13
 8： 21
 9： 34
10： 55
11： 89
12： 144
13： 233
14： 377
15： 610
16： 987
17： 1597
18： 2584
19： 4181
20： 6765

これでフィボナッチ数列と再帰について理解してくれましたか？