はじめに

はじめに

こんにちは！さいとーです。

個人的にフィボナッチ数列というものを最近よく耳にします。

会社内のプランニングポーカーに使われていたり、最近よんだ本にでてきたり、、

ちょこっと調べてみるとアルゴリズムを勉強できそうだったので記事にしました。

フィボナッチ数列とは

13 世紀のイタリア数学者レオナルド・フィボナッチが著書「算盤の書」でウサギの繁殖モデルを例に紹介したのが起源
フィボナッチ数列は、最初の二項を 0 と 1 とし、それ以降の項を直前二項の和で定義する整数列である。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597.....

数値が大きくなるほどタスクの不確実性も増すので、フィボナッチ特有の「差がどんどん広がる」増え方は実際のプロジェクトでのリスク感覚とマッチするためタスク見積もりの一種でああるプランニングポーカーに多く使用されている
フィボナッチ数列を隣同士の項を割って比率を出すことで「黄金比」と言われる1:1.618...の比率と収束していくことが判明している。

黄金比とは「人間が美しいと感じる神の比」ともいわれており、黄金比はモナリザの絵画や身近のところでいうとクレジットカードや名刺縦横比やいろいろなデザインにも多く使われ地ます。
不思議なことに、人間が美しいと思う花びらの数がフィボナッチ数列の数と一致していたり、貝殻や巻貝の螺旋がフィボナッチ数列に沿った構造になっていたりと偶然とは思えない奇妙な関係があります。

https://arbis.jp/creation/fibonacci.html

黄金比1:1.618..に収束していく

1÷1=1
2÷1=2
3÷2=1.5
5÷3=1.6666...
8÷5=1.6
13÷8=1.625
21÷13=1.6153...
34÷21=1.6190...
55÷34=1.6176...

再帰関数とは

フィボナッチ数列をコード上で表すと再帰関数をつかうことになります。

今回の記事ではjavascriptを使います。

再帰関数とは、自分自身を呼び出す関数のことです。複雑な問題を小さな同じパターンの問題に分解して解決するアプローチです。

function recursive() {
  // 何らかの処理
  recursive(); // 自分自身を呼び出す
  // 何らかの処理
}

しかし、上記のような単純な再帰は無限ループを引き起こします。実用的な再帰関数には必ず「基底条件（ベースケース）」が必要です。これは再帰呼び出しを停止させる条件です。元の問題よりも小さな問題となるように再帰呼び出しを行い、そのような「より小さい問題の系列」が最終的にベースケースに辿り着くようにします。

function factorial(n) {
  // 基底条件
  if (n <= 1) {
    return 1;
  }
  // 再帰呼び出し
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120

再帰のメリットとデメリット

メリット

コードの可読性が向上する場合がある
複雑な問題を小さな同型の問題に分解できる
データ構造（木構造など）の操作に自然に適合する

デメリット

スタックオーバーフローのリスク
反復（ループ）と比較してパフォーマンスが劣ることがある
デバッグが難しい場合がある

0からn番目までフィボナッチ数列を表すコード

/**
 * 0 〜 n 番目までのフィボナッチ数列を配列で返す
 * @param {number} n — 非負整数
 * @returns {number[]} 長さ n+1 の配列（[F(0), F(1), …, F(n)]）
 */
function fibonacciArray(n) {
  if (n < 0) throw new Error('n は 0 以上の整数を指定してください');
  // n が 0 のときは [0]、1 のときは [0,1] を返す
  const result = [0, 1];
  if (n === 0) return [0];
  if (n === 1) return result;

  // 2 以上はループで計算
  for (let i = 2; i <= n; i++) {
    result[i] = result[i - 1] + result[i - 2];
  }
  return result;
}

// 使用例
console.log(fibonacciArray(10));
// → [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

JavaScript での実装例

n番目のフィボナッチの数を知るコード

function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(10)); // 55

再帰的にベースケースまで降りた回数を数えると、177 回の関数呼び出しが行われます。

C(n): 関数の呼び出し回数の再帰式は

C(n)=C(n−1)+C(n−2)+1

最後の「＋1」は自分自身（fibonacci(n) 本体）の呼び出しをカウントしています。

C(0)=1,

C(1)=1,

C(2)=C(1)+C(0)+1=1+1+1=3,

C(3)=C(2)+C(1)+1=3+1+1=5

⋮

C(10)=177

つまり、fibonacci(10) を呼ぶと 177 回の関数呼び出しが内部で行われる、ということを示しています。

let callCount = 0;

function fibonacci(n) {
  callCount++;                 // ← 呼び出されるたびにカウント
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

// 計算実行
const result = fibonacci(10);

// 結果と呼び出し回数を表示
console.log('fib(10) =', result);       // fib(10) = 55
console.log('呼び出し回数 =', callCount); // 呼び出し回数 = 177

日常生活のこんな謎もフィボナッチ数列で解決することができます。

あなたの家の階段は10段あります。
一度に登れるのは1段または、2段のみです。
10段の階段を登る方法は何通りありますか？

1段目の登り方は1通りです。

2段目は1段ずつと2段上がる登り方の2通り。

3段目は1段ずつ・1段登って2段登る・2段登って1段登るの3通りです。

4段目は1段ずつ・1段×2登って2段登る・1段登って2段登って1段登る、

2段登ってあとは1段ずつ、2段ずつ登るの5通りです。

登り方の総数をW(ｎ)にすると

W(0)=1,
W(1)=1,
W(n)=W(n−1)+W(n−2),

と表すことができます。まさにフィボナッチ数列そのものです。

/**
 * n段の登り方の総数を再帰で計算する
 * @param {number} n — 段数（0以上の整数）
 * @returns {number} 登り方の通り数
 */
function countWays(n) {
  if (n < 0) return 0;     // 負の段数は方法なし
  if (n === 0) return 1;   // 0段なら1通り
  if (n === 1) return 1;   // 1段なら1通り
  // 段前と2段前の合計
  return countWays(n - 1) + countWays(n - 2);
}

console.log(countWays(10)); // → 89

となり89通りとわかります。

分割統治法（Divide and Conquer）

分割統治法は「問題を小さな部分問題に分割し、それらを個別に解いてから結果を結合する」というアプローチです。先ほどのコードフィボナッチ数のコードはまさに分割統治法といえます。

問題（n番目のフィボナッチ数を求める）を2つの部分問題（n-1番目とn-2番目のフィボナッチ数を求める）に分割し、それぞれを再帰的に解いて結果を足し合わせています。

分割統治法を身近なもので例えると、開発のプロジェクトで「バックエンド→フロントエンド→統合」などに細分化して担当を割り振る。みたいなイメージ

分割統治法の問題点

ただし、この単純な実装は重複計算により非効率です。

先程のfibonacci のコードでたとえばfibonacci(5)を呼んだとき

               
fib(5)
├─ fib(4)
│  ├─ fib(3)
│  │  ├─ fib(2)
│  │  │  ├─ fib(1) → 1
│  │  │  └─ fib(0) → 0
│  │  └─ fib(1) → 1
│  └─ fib(2)
│     ├─ fib(1) → 1
│     └─ fib(0) → 0
└─ fib(3)
   ├─ fib(2)
   │  ├─ fib(1) → 1
   │  └─ fib(0) → 0
   └─ fib(1) → 1

このツリーでは同じ fib(2) や fib(3) が何度も計算されています。

この重複が指数的な計算量O(2ⁿ) を生み出し、n が大きくなるほど急激に遅くなります。

nが大きくなるとこの重複が爆発的に増加し、計算量はO(2ⁿ)になります。つまり、nが1増えるごとに計算量がおよそ2倍になるのです。

例: n=10→2¹⁰=1,024 回、n=11→2¹¹=2,048 回

さきほど見たようにfib(10) なら177回も関数が呼び出されています。

n=10 ならすぐ終わりますが、n=40 などだと何秒もかかるようになります。

フィボナッチ数列をプログラムで表すのだったら分割統治法はあまり適していません。

動的計画法（Dynamic Programming）

動的計画法は、部分問題の解を記憶（メモ化）することで、同じ計算を繰り返すことを避ける手法です。フィボナッチ数列の計算における動的計画法には、主に2つのアプローチがあります。

1. トップダウン方式（メモ化）

トップダウン方式（メモ化）を使った改良版を見てみましょう。

既に計算した結果をキャッシュすることで重複計算を避けられます。

計算量は線形時間O(n)になります

n が増えると処理回数もほぼ同じだけ増え、n を 2 倍にすると処理量も 2 倍になります。

こちらを身近なもので例えると、毎回ゼロから作るのではなく、一度作った報告書や企画書のフォーマットを保管し、「○○プロジェクト用」「△△案件用」として都度コピー＆編集して使い回す。みたいなイメージです。

let callCount = 0;

function fibonacciMemo(n, memo = {}) {
  callCount++;                  // ← 呼び出されるたびにカウント

  if (n in memo) return memo[n];
  if (n <= 1) return n;

  memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
  return memo[n];
}

// 呼び出し回数のリセット
callCount = 0;

// 計算実行
console.log(fibonacciMemo(5));    // → 5
console.log('呼び出し回数 =', callCount); // → 9

fib(5) → fib(4) → fib(3) → fib(2)

ここまではキャッシュなしで再帰的に降りていき、ベースケース fib(1)=1, fib(0)=0 を得ます。

memo[2] が 1 でキャッシュされます。

上がってきて fib(3) の計算が完了すると、memo[3] = fib(2)+fib(1) = 1+1 = 2。

さらに上がって memo[4] = fib(3)+fib(2) = 2+1 = 3。

fib(5)
├─ fib(4)
│  ├─ fib(3)
│  │  ├─ fib(2)
│  │  │  ├─ fib(1) → (ベースケース: 1)
│  │  │  └─ fib(0) → (ベースケース: 0)
│  │  │     └─ memo[2] = 1
│  │  └─ fib(1) → (ベースケース: 1)
│  │     └─ memo[3] = 2
│  └─ fib(2) → (memoヒット: 1)
│        └─ memo[4] = 3
└─ fib(3) → (memoヒット: 2)
      └─ memo[5] = 5

メモ化を使わない場合はfib(5) は合計 15 回 呼び出されるのに対して

メモ化を使うとfib(5) は合計 9 回 の呼び出しになります

これを見るとあまり回数が変わらないように見えますが、fib(10) の場合は変化が顕著になります。

メモ化を使わない場合→177回

メモ化をつかう場合→19回

2. ボトムアップ方式（タビュレーション）

動的計画法のもう一つのアプローチは、最小の部分問題から始めて、順番に大きな問題を解いていく方法です。これはメモリ使用量を最小限に抑え、さらにスタックオーバーフローの心配もありません。

こちらは全ての部分問題を解くためのテーブル(配列)を用意して事前に作成して最後の配列のインデックスを返すことでフィボナッチ数が求められる

function fibonacciTabulation(n) {
  if (n <= 0) return 0;
  if (n === 1) return 1;

  // dp[i] に F(i) を格納する配列
  const dp = new Array(n + 1);
  dp[0] = 0;
  dp[1] = 1;

  // 2 から n まで順に埋めていく
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n];
}

console.log(fibonacciTabulation(10)); // 55

これをn分の配列を作成せずにシンプルに書き直したものがこちらです

temp = a + b で次のフィボナッチ数 F(i) を計算し変数をシフトa = b（旧 F(i-1)）、b = temp（新 F(i)）これにより配列を使わずに「直前２項だけ」を保持しながら順次計算できます

function fibonacciDP(n) {
  if (n <= 0) return 0;
  if (n === 1) return 1;
  
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    const temp = a + b;
    a = b;
    b = temp;
  }
  
  return b;
}