• ベストアンサー

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

ちょうど学校でフィボナッチ数列の話題になったので、思いつきで作ってみました。 そこで、配列を使ったものと再帰呼び出しを使ったものを作りました。 //再帰呼び出し 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]; } この二つを比較すると明らかに配列の方が早いです。 ということは再帰呼び出しはあまり使わない方がよいってことですよね? この場合は配列も似たような感じで見ることができますし。 それとも自分の再帰の書き方が悪いのでしょうか。

質問者が選んだベストアンサー

  • ベストアンサー
  • chie65536
  • ベストアンサー率41% (2512/6032)
回答No.1

>この二つを比較すると明らかに配列の方が早いです。 >ということは再帰呼び出しはあまり使わない方がよいってことですよね? いいえ、違います。 求める項nが「ある程度以下」なら配列で処理出来ますが、もし、項nが大きく、それだけの配列を確保出来ない場合、遅いと判ってても再帰を使わざるを得ない場合があります。 >それとも自分の再帰の書き方が悪いのでしょうか。 「再帰関数が何回呼び出されるか?」を考えれば「再帰が如何に遅いか」が判ります。 項nの呼び出し回数は「項nのフィボナッチ数×2-1」です。n=10のフィボナッチ数は55ですから、55×2-1=109で、109回も呼び出されます。 最後に、再帰呼出も配列も使わない(nに制限がなく、スピードも速い)関数を書いておきます。参考にして下さい。 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; }

yata16
質問者

お礼

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

すると、全ての回答が全文表示されます。

その他の回答 (2)

  • chirubou
  • ベストアンサー率37% (189/502)
回答No.3

高速化についてはいろいろと議論があると思いますが。 「この二つを比較すると明らかに配列の方が早いです。 ということは再帰呼び出しはあまり使わない方がよいってことですよね? この場合は配列も似たような感じで見ることができますし。 それとも自分の再帰の書き方が悪いのでしょうか。」 世の中、プログラムは速く動く事も重要ですが、「キレイに書く/他人が読み易く書く」という事も重要です。 再帰で書くと、フィボナッチの定義により近いと思いませんか?まあ、配列を使わない程度しか違いませんが。 大きなプログラムを、あるいはあなたがオープンソースを書いたとして、他人があなたの書いたプログラムを見て、何をしているのか理解しようとすることがあるとしましょう。この時、プログラムにコメントを入れる事も手助けになりますが、プログラムだけでも「キレイに」(要は他人から見られることを意識する、という意味)書いてあれば、理解の助けになると思いませんか? 職業でプログラムを書いていると、多くの場合、正しく動くことが一番重要で、速さはその次になったりします。多分、フィボナッチの授業は再帰呼び出しが数学的な再帰によくマッチして「キレイ」だ、という事を理解するのが目的だったのではないでしょうか。 P.S. 細かいようですが、C プログラマならば f[0] から始めて欲しかった.....

yata16
質問者

お礼

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

すると、全ての回答が全文表示されます。
  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.2

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

yata16
質問者

お礼

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

すると、全ての回答が全文表示されます。

関連するQ&A