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

2021-09-30
2022-04-14

Formula

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

Fn=Fn1+Fn2Fn = Fn-1 + Fn-2

Noob

js
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

ts
const fib = (n: number): number => (n <= 1 ? n : fib(n - 1) + fib(n - 2)); console.log("fib:", fib(50)); // stackoverflow

Expert

ts
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)); // 👌

学び

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