JavaScript フィボナッチでスタックオーバーフローをちょっと観察

Formula

1, 1, 2, 3, 5, 8, 13, 21.... と続いていく数式

$Fn = Fn-1 + Fn-2$

Noob

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

// 出力
console.log(fib(0)); // 1
console.log(fib(1)); // 1
console.log(fib(2)); // 2
console.log(fib(3)); // 3
console.log(fib(4)); // 5
console.log(fib(50)); // stackoverflow

スタックオーバーフロー ≒ メモリ不足。コールスタックを超えていった

Student

const fib = (n: number): number => (n <= 1 ? n : fib(n - 1) + fib(n - 2));

console.log("fib:", fib(50)); // stackoverflow

Expert

  const memoFib = (n: number) => {
    const memo = new Map();
    memo.set(0, 0);
    memo.set(1, 1);
    const fib_ = (n: number) => {
      if (memo.has(n)) {
        return memo.get(n);
      }
      const result: number = fib_(n - 1) + fib_(n - 2);
      memo.set(n, result);
      return result;
    };
    return fib_(n);
  };

  console.log(memoFib(50)); // 👌

学び

• 参照透過性: 入力(渡す値)が同じであれば、出力（戻り値）が同じであるという性質
• 副作用: 関数とは引数を受け取り、値を返すものである。それ以外の振る舞いを副作用と名付けた。望まれない子か救世主か。それは、生みの親に委ねられた。子供に罪はないと人々は豪語する。
• 純粋関数: 副作用のないピュアな関数