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

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

元ネタ：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);