Zenn
💡

フィボナッチ数列のn番目の数を求める再帰関数

に公開
初心者
再帰
tech

ヘッド再帰

  • 二つの再帰関数を呼び出すことになるので、計算量が膨大になってしまいます。
test.js
// ヘッド再帰
function fibonacci(n){
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n-1) + fibonacci(n-2);
}

末尾再帰

  • 末尾再帰を用いることで計算量を抑えること(最適化)ができます。
  • ヘッド再帰では計算量が大きすぎて処理し切れないものも、末尾再帰なら問題なく処理できることがあります
test.js
// 末尾再帰
function fibonacciTail(n){
    return fibonacciTailHelper(0,1,n);
}

function fibonacciTailHelper(f1,f2,n) {
    if (n == 0) return f1;
    return fibonacciTailHelper(f2,f1+f2,n-1);
}

fibonacciTail(4)の場合

関連

https://zenn.dev/417yr/articles/263fc740904152

https://zenn.dev/417yr/articles/b9cd036bf554d0

Discussion