次のページへフィボナッチ数列のn番目を求める最初は0、次が1、3番目以降は直前の2つの数字を足したものになる数列を、フィボナッチ数列といいます。3番目は0+1=1、4番目は1+1=2、5番目は2+1=3、6番目は2+3=5、といった具合に続いていきます。この数列のn番目を計算するプログラムを作りましょう。フィボナッチ数列は次のように定義されます。(i≧2)定義そのものが再帰的になっているので、プログラムもそのまま再帰を使って書くことができます。加算の回数をカウントするための変数countを定義しています。画面のボタンをクリックするとstartCalc関数が呼ばれ、計算が始まります。7行目2回目以降の実行の際には、前の結果が表示されているので消去します。画面のテキストボックスに入力された数値を取得しています。10行目フィボナッチ数を計算し、結果を表示します。15行目フィボナッチ数を計算するfibonacci関数を定義します。16〜18行目0番目のフィボナッチ数は0なので、0を返します。19〜21行目1番目のフィボナッチ数は1なので、1を返します。23行目2番目以上の場合は1つ前と2つ前のフィボナッチ数の合計を返します。このプログラムの実行には注意してください。25以上の数を入れて計算させると極端に時間がかかります。1ずつ増やして実行してみてください。数が1増えただけで計算時間が加速度的に長くなっていきます。いまどきのPCは劇的に性能がよくなっているのに、たかだか28や29のフィボナッチ数の計算も精一杯です。計算に時間がかかってしまうのはアルゴリズムがよくないからです。4のフィボナッチ数の計算がどうなるかを考えてみましょう。f(4)が4のフィボナッチ数を表しているとします。f(2)が2回、全く同じ計算がされていることが分かると思います。数が大きくなれば大きくなるほど同じ計算を行う回数が飛躍的に増えてしまいます。これを改善するために1度計算した計算結果を覚えておくようにしましょう。改善したプログラムは以下になります。</body></html>先ほどのプログラムとの違いを説明します。4行目n番目のフィボナッチ数を覚えておくための配列を準備します。9〜10行目0番目と1番目のフィボナッチ数は決まっているのであらかじめ代入します。20行目n番目のフィボナッチ数がまだ計算されていなかったときだけ再帰呼び出しでフィボナッチ数を計算します。それではWebブラウザでプログラムを実行してみてください。25や30では計算時間は一瞬です。300でも全く問題なく計算できます。3000だとスタックオーバーフローになります。このようにちょっとしたアルゴリズムの違いでパフォーマンスには大きな差が生まれます。再帰を使わないでフィボナッチ数を計算するフィボナッチ数の計算も再帰を使わないで記述することができます。どのようにしたらよいでしょうか。この場合、数式の定義は忘れて最初の説明どおりに素直に実装するとよいでしょう。0から始まって1ずつ増えるようにループしてn番目まで計算すればよいのです。プログラムは以下になります。</body></html>フィボナッチ数列の場合は再帰を使わなくても分かりやすいですし、パフォーマンスも改善版とほぼ同等です。いった場合はどちらで実装しても問題ないということになります。メールマガジンをご購読ください。申し込みページへITmediaはアイティメディア株式会社の登録商標です。