JavaScriptでフィボナッチ数列を再帰関数なしで計算してみた

フィボナッチ数列とは次の数列のこと

1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...

1	1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...

これをJavaScriptで計算するには、

再帰関数を使ったやり方
単純ループを使ったやり方

この２つがあって僕は再帰関数が嫌いです。

そこで再帰関数を使わなくてもできる、
フィボナッチ数列の計算方法を考えてみました。

このページの目次

フィボナッチ数列の定義は簡単
安易な再帰版フィボナッチ数列のコード例
再帰関数版は40項目すら爆発的な計算時間
ループのみでフィボナッチ数計算のコード例
ループ版と再帰版では処理速度が天と地の差
本当に再帰関数って必要？そう思わない

フィボナッチ数列の定義は簡単

ここは説明するまでもないですね。

フィボナッチ数列はこういう数列です。

▼ 次のような定義

▼ 言葉の意味と由来

初項と第2項を1とし、第3項以後次々に前2項の和をとって得られる数列。つまり、a1＝1, a2＝1, an＋1＝an＋an-1 (n＝2, 3, 4,……) で表され、1, 1, 2, 3, 5, 8, 13, 21, 34,…… という数列となる。これはフィボナッチが『算術の書』（1202）のなかで、次のような問題として提起したものである。

引用元　：　https://kotobank.jp/word/フィボナッチ数列-615599

神秘的な数列として知られています。

例えば自然界なら花びらの数だったり、DNAの構造だったり、台風や銀河の渦巻きだったり…あらゆる場面で出現する普遍的な数列のようです。

ここではそれをコード的に求めてみます。

安易な再帰版フィボナッチ数列のコード例

ということで初めに再帰関数による方法

フィボナッチ数列を求めるコードがこれです。

▼ 再帰版のフィボナッチ数列のコード例

function fib(n){
  if(n===1||n===2){ return 1; }
  if(isNaN(n)){ return NaN; }
  return fib(n-1)+fib(n-2)
}

for(let n=1; n<=10; ++n){
  console.log('['+n+'] : '+fib(n));
}

function fib(n){

if(n===1||n===2){ return 1; }

if(isNaN(n)){ return NaN; }

return fib(n-1)+fib(n-2)

}

for(let n=1; n<=10; ++n){

console.log('['+n+'] : '+fib(n));

}

▼ 上記コードの出力結果

[1] : 1
[2] : 1
[3] : 2
[4] : 3
[5] : 5
[6] : 8
[7] : 13
[8] : 21
[9] : 34
[10] : 55

[1] : 1

[2] : 1

[3] : 2

[4] : 3

[5] : 5

[6] : 8

[7] : 13

[8] : 21

[9] : 34

[10] : 55

とってもスマートなコードに見えてしまう。

もちろん計算結果も間違えてません。

でも再帰関数を使うこと自体が間違っています。

再帰関数版は40項目すら爆発的な計算時間

上記の再帰版フィボナッチ数列のコード。

問題なのは計算に爆発的な時間がかかることです。

試しに30項目と40項目の計算、
それにかかる時間（ミリ秒精度）を計測しました。

▼ このようなコードで時間計測

var start = performance.now();
fib(30);
var end = performance.now();
console.log( '実行時間 = ' + (end - start) + 'ミリ秒' );
  /// 実行時間 = 7.7ミリ秒

var start = performance.now();
fib(40);
var end = performance.now();
console.log( '実行時間 = ' + (end - start) + 'ミリ秒' );
  /// 実行時間 = 1145.7ミリ秒

var start = performance.now();

fib(30);

var end = performance.now();

console.log( '実行時間 = ' + (end - start) + 'ミリ秒' );

/// 実行時間 = 7.7ミリ秒

var start = performance.now();

fib(40);

var end = performance.now();

console.log( '実行時間 = ' + (end - start) + 'ミリ秒' );

/// 実行時間 = 1145.7ミリ秒

計測時間の測り方は次記事を見てください。

▼ 処理時間計測の本当に正しい方法

PisukeCode - Web開発まとめ

JavaScriptで処理時間を計測する本当に正しい方法

https://pisuke-code.com/javascript-measure-processing-time

どの処理にどれだけ時間がかかっているのか・・・調べたいことってありますよね？でも正しい計測方法を知っていないと精度が悪かったり余計な手間がかかってしまうかもしれません。ということでJavaScriptでの本当に正しい処理時間の計測方法について紹介します。Date.nowは時間計測に使ってはダメ！JavaScriptには現在の時間をミリ秒で返してくれるDate.now関数が用意されています。しかし、処理時間を計測するのにこの Date.now は使うべきではありません。確かにこの関数を使えば次のように簡単に時間が計測できます。/** 始...

上記コードの実行時間を見てみましょう。

ヤバさが見えてきたと思います。

たった10項の差しかないにも関わらず、30項では計算時間7.7ミリ秒なのに、40項目になると1145ミリ秒と爆発的に計算時間が増えてます。

これは再帰には次の弱点があるから。

関数呼び出しのオーバーヘッド
致命的な弱点。関数はタダでポンポン呼び出せるものではなく、それ自体を実行するまでにオーバーヘッド（ムダな時間）がかかってしまう
項数が増えるほどに計算量が爆発
この関数の中では n >= 2 のとき、2回自分自身を再帰実行している。つまりnの値に比例して呼び出し回数が指数的に増えてしまう…

これが再帰関数を使うべきでない理由です。

そもそもメモリ自体が有限なんだから、そのメモリを食い尽くした時点で再帰関数は実行できなくなります。再帰そのものが問題を引き起こすわけです。

だから再帰は不用意に使うべきではない。

むしろgoto文同様に忌避すべきだと考えます。

ループのみでフィボナッチ数計算のコード例

ということで再帰を使わない方法について。

フィボナッチ数列は単純ループで求められます。

▼ 非再帰でのフィボナッチ計算コード例

function fib(n){
  /// nが1または2なら1を返す
  if(n===1||n===2){ return 1; }
  /// 非数を渡されたときの処理
  if(isNaN(n)){ return NaN; }
  
  let n0=1, n1=1;
  while(n-- > 3){
    /// 次項を計算する
    [n0,n1] = [n1,n0+n1];
  }
  /// 結果を返す
  return n0+n1;
}

for(let n=1; n<=10; ++n){
  console.log('['+n+'] : '+fib(n));
}

function fib(n){

/// nが1または2なら1を返す

if(n===1||n===2){ return 1; }

/// 非数を渡されたときの処理

if(isNaN(n)){ return NaN; }

let n0=1, n1=1;

while(n-- > 3){

/// 次項を計算する

[n0,n1] = [n1,n0+n1];

}

/// 結果を返す

return n0+n1;

}

for(let n=1; n<=10; ++n){

console.log('['+n+'] : '+fib(n));

}

実行結果は再帰版とおなじです。

▼ 少し工夫したのが次の部分

/// 次項を計算する
[n0,n1] = [n1,n0+n1];

1 2	/// 次項を計算する [n0,n1] = [n1,n0+n1];

▼ この記事を参考にした

Qiita

変数の中身を入れ替える際は分割代入を使うとスマート - Qiita

https://qiita.com/Nossa/items/bb8768f5bfd3509732bb

以下のような二つの変数があるとします。変数を2つ用意let a = 'A';let b = 'B';分割代入を使うと以下のように書くことができます。分割代入を使った値の交換 = ;...

ここでは前項と前々項を n0 , n1 で表したんですが、次項の計算には一時変数が必要になります。それが嫌なので上記qiitaの分割代入を応用しました。

あとは特に変わったことはないです。

再帰でやってたことをループに落としただけ

このように大抵の処理は再帰なしでできます。

ループ版と再帰版では処理速度が天と地の差

ということでループ版の速度を測ってみます。

測り方は先ほどの再帰版のときと同じです。

▼ 30項・40項の計算の間計測

var start = performance.now();
fib(30);
var end = performance.now();
console.log( '実行時間 = ' + (end - start) + 'ミリ秒' );
  /// 実行時間 = 0ミリ秒

var start = performance.now();
fib(1000);
var end = performance.now();
console.log( '実行時間 = ' + (end - start) + 'ミリ秒' );
  /// 実行時間 = 0ミリ秒