javascriptで実装（再帰）

function fib(n) {
 if (n < 3) return 1;
 return fib(n - 1) + fib(n - 2);
}

O(2^n)

再帰で大事なのは２点

・終了条件の設定

・引数が毎回変わる

ここでの終了条件とは、if (n < 3)に達したら終了。これがないと無限ループになってしまう。whileに終了条件があるのと一緒です。

引数は呼び出す度に、減算していますね。

が、遅い。。。

メモ化

function fibonacci(position, memo = []) {
 if (position < 3) return 1;
 if (memo[position]) return memo[position];
 memo[position] =
   fibonacci(position - 1, memo) + fibonacci(position - 2, memo);
 return memo[position];
}

O(n)

一度計算したらキャッシュに入れる（memo[position]）。

再帰が、よく分からない人は、カウントダウンする単純な関数を作ってみよう。

function countDown(num) {
//終了条件
 if (num <= 0) return;
 console.log(num);
//値を変更
 countDown(num - 1);
}

countDown(10);

アルゴリズムは図解すると分かりやすいです。ってか図解しないとわからない。。

再帰でスタックの積み方を詳しく知りたい人は、この本が超オススメです。