フィボナッチ数列をつくってみたけれど・・・

質問

ちょうど学校でフィボナッチ数列の話題になったので、思いつきで作ってみました。
そこで、配列を使ったものと再帰呼び出しを使ったものを作りました。

//再帰呼び出し
unsigned long Fibonacci(int n){

if(n==1){ return 1;} //初項
else if(n==2){ return 1;} //第2項

return Fibonacci(n-1) + Fibonacci(n-2);
}

//配列
unsigned long Fibonacci(int n){

unsigned long long f[101];
int i;

f[1] = 1;
f[2] = 1;

for( i=3; i<=n; i++){

f[i] = f[i-1] + f[i-2];
}

return f[n];
}

この二つを比較すると明らかに配列の方が早いです。
ということは再帰呼び出しはあまり使わない方がよいってことですよね？
この場合は配列も似たような感じで見ることができますし。
それとも自分の再帰の書き方が悪いのでしょうか。

回答No.1

chie65536 · ベストアンサー

＞この二つを比較すると明らかに配列の方が早いです。
＞ということは再帰呼び出しはあまり使わない方がよいってことですよね？

いいえ、違います。

求める項ｎが「ある程度以下」なら配列で処理出来ますが、もし、項ｎが大きく、それだけの配列を確保出来ない場合、遅いと判ってても再帰を使わざるを得ない場合があります。

＞それとも自分の再帰の書き方が悪いのでしょうか。

「再帰関数が何回呼び出されるか？」を考えれば「再帰が如何に遅いか」が判ります。

項ｎの呼び出し回数は「項ｎのフィボナッチ数×２－１」です。ｎ＝１０のフィボナッチ数は５５ですから、５５×２－１＝１０９で、１０９回も呼び出されます。

最後に、再帰呼出も配列も使わない（ｎに制限がなく、スピードも速い）関数を書いておきます。参考にして下さい。

unsigned long Fibonacci(int n)
{
　　int i;
　　unsigned long a,b,c;
　　for (i=1,a=0,b=1;i<n;i++) {
　　　　c=a+b;
　　　　a=b;
　　　　b=c;
　　}
　　return b;
}

お礼

＞求める項ｎが「ある程度以下」なら配列で処理出来ますが
一応ｎがそんなに大きくならなくてもｎ項目の値がとても大きかったので、配列でもいいか、と思ってやってみました。
でも、配列も再帰も使わなくてもできるんですね。
とても参考になりました。
ありがとうございました。

回答No.3

chirubou

高速化についてはいろいろと議論があると思いますが。

「この二つを比較すると明らかに配列の方が早いです。
ということは再帰呼び出しはあまり使わない方がよいってことですよね？
この場合は配列も似たような感じで見ることができますし。
それとも自分の再帰の書き方が悪いのでしょうか。」

世の中、プログラムは速く動く事も重要ですが、「キレイに書く／他人が読み易く書く」という事も重要です。

再帰で書くと、フィボナッチの定義により近いと思いませんか？まあ、配列を使わない程度しか違いませんが。

大きなプログラムを、あるいはあなたがオープンソースを書いたとして、他人があなたの書いたプログラムを見て、何をしているのか理解しようとすることがあるとしましょう。この時、プログラムにコメントを入れる事も手助けになりますが、プログラムだけでも「キレイに」（要は他人から見られることを意識する、という意味）書いてあれば、理解の助けになると思いませんか？

職業でプログラムを書いていると、多くの場合、正しく動くことが一番重要で、速さはその次になったりします。多分、フィボナッチの授業は再帰呼び出しが数学的な再帰によくマッチして「キレイ」だ、という事を理解するのが目的だったのではないでしょうか。

P.S.
細かいようですが、C プログラマならば f[0] から始めて欲しかった.....

お礼

一応f[1]から始めたのは、なるべく数列に近づけようと思ったからです。
自分なりに見やすいかな、と思い、f[1]からにしました。
ちなみにフィボナッチの話は仲の良い数学の先生と「美しい！」ということで盛り上がったので・・・。
Cは独学です。

回答No.2

Tacosan

#1 でも書かれてますけど, Fibonacci 数列は「再帰的に定義されているけど本当に再帰で計算するととても時間がかかる」例でよく使われますね. まあ, Fibonacci 数列に限らず, (漸化式で) 再帰的に定義されてる数列はみんなそうなんですが.
で普通は #1 のようにループで計算するわけですが, 計算量的には行列の乗算を使うとか「閉じた式」を使うのが最適だったはず.

お礼

色々な求め方があっておもしろいですね。
ありがとうございました。