逆に考えるんだ、ループを末尾再帰に変換すればいいやって

元ネタ：Haskellをかける少女

ワイ君のコード

fibo.js

const fibo = n => {
  const arr = [0, 1];

  for (let i = 2; i <= n; i++) {
    arr.push(arr[i - 1] + arr[i - 2]);
  }

  return arr[n];
};

配列の最後の要素を返す

n !== 0のとき、arr[n]は配列の最後の要素なので、そのことが明示的になるようにfiboAのように書き直してみる。

fiboA.js

const fiboA = n => {
  if (n === 0) {
    return 0;
  }

  const arr = [0, 1];

  for (let i = 2; i <= n; i++) {
    arr.push(arr[i - 1] + arr[i - 2]);
  }

  return arr[arr.length - 1];
};

配列の最後の要素と、最後から2番目の要素で更新する

また、arr[i - 2]は最後の要素、arr[i - 1]は最後から2番目の要素になっているから、下記のfiboBのように書き直せる。

fiboB.js

const fiboB = n => {
  if (n === 0) {
    return 0;
  }

  const arr = [0, 1];

  for (let i = 2; i <= n; i++) {
    arr.push(arr[arr.length - 2] + arr[arr.length - 1]);
  }

  return arr[arr.length - 1];
};

配列いらなくね？

最後の要素と最後から2番目の要素しか登場していないので、下記fiboCのように、それぞれarrLast1、arrLast2の変数に書き換えられる。ただし、値の更新には一時変数が必要になる。

fiboC.js

const fiboC = n => {
  if (n === 0) {
    return 0;
  }

  let temp;
  let arrLast1 = 1;
  let arrLast2 = 0;

  for (let i = 2; i <= n; i++) {
    temp = arrLast1;
    arrLast1 = arrLast2 + arrLast1;
    arrLast2 = temp;
  }

  return arrLast1;
};

添字いらなくね？

配列がなくなったため、添字としてのiは不要になる。nを直接更新することで、下記のfiboDようにループを書き換えられる。

fiboD.js

const fiboD = n => {
  if (n === 0) {
    return 0;
  }

  let temp;
  let arrLast1 = 1;
  let arrLast2 = 0;

  for (; n !== 1; n--) {
    temp = arrLast1;
    arrLast1 = arrLast2 + arrLast1;
    arrLast2 = temp;
  }

  return arrLast1;
};

forからwhileへ

fiboE.js

const fiboE = n => {
  if (n === 0) {
    return 0;
  }

  let temp;
  let arrLast1 = 1;
  let arrLast2 = 0;

  while (n !== 1) {
    n = n - 1;
    temp = arrLast1;
    arrLast1 = arrLast2 + arrLast1;
    arrLast2 = temp;
  }

  return arrLast1;
};

末尾再起にする

ここまでくれば、下記fiboFのような末尾再帰に変換できる。計算量を変えないように関数を変換していったので、fiboFも計算量は$O(n)$になっている。

fiboF.js

const fiboF = (n, arrLast1 = 1, arrLast2 = 0) => n === 0 ? 0 : n === 1 ? arrLast1 : fiboF(n - 1, arrLast2 + arrLast1, arrLast1);

おわり

ちなみに、引数累積するなら下記のコードのほうが短い。
あと、$F_{78}$ < Number.MAX_SAFE_INTEGER < $F_{79}$ なので、スタック・オーバーフローよりも先に計算誤差が問題になる。

fib.js

const fib = (n, a = 0, b = 1) => n === 0 ? a : fib(n - 1, a + b, a);