😸

ヘッド再帰と末尾再帰

2024/09/15に公開

 ヘッド再帰普通の再帰関数
例：return 再帰関数+α
関数が演算子より優先されるため、演算子部分が後回しにされている
コールスタックに蓄積される
test.js
// 1 から n までの総和を計算する関数sum
function sum(n){
    // ループを終了させるベースケース
    if (n <= 0) {
        return 0;
    }
        
    return sum(n-1) + n;
}

 末尾再帰関数の処理の末尾で、その関数自体を実行(再帰処理)するのが末尾再帰
例：return 再帰関数
test.js
function sumTail(n){
    return sumTailHelper(n, 0);
}

function sumTailHelper(count, total){

    if(count <= 0 ) {
        return total;
    }

    return sumTailHelper(count-1, total+count);
}

console.log(sumTail(2));

 末尾呼び出し最適化（tail call optimization）末尾再帰を利用することで、一部の言語では末尾呼び出し最適化（tail call optimization）という技術が適用されることがある
ヘッド再帰のように、コールスタックに戻り値がpushされベースケースに到達するまで蓄積されていくのではなく、

その都度自身をpopし、戻り値である次の関数をpushする

（戻り値によってその都度上書きされていくようなイメージ）
コールスタックに蓄積されない
空間計算量が削減できる→スタックオーバーフローを回避できることがある

ヘッド再帰

末尾再帰

末尾呼び出し最適化（tail call optimization）

Discussion