[解決済み] 末尾再帰とは何ですか？

質問

lispを学び始めているときに、以下の用語に出会いました。 末尾再帰的 . 具体的にはどのような意味ですか？

どのように解決するのですか？

最初のN個の自然数を足す簡単な関数を考えてみましょう。(例 sum(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15 ).

ここでは、再帰を利用したJavaScriptの簡単な実装を紹介します。

function recsum(x) {
    if (x === 0) {
        return 0;
    } else {
        return x + recsum(x - 1);
    }
}

を呼び出した場合 recsum(5) JavaScriptのインタプリタが評価する内容は、このようなものです。

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + (1 + recsum(0)))))
5 + (4 + (3 + (2 + (1 + 0))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15

JavaScript インタープリタが実際に合計を計算する前に、すべての再帰的な呼び出しが完了しなければならないことに注意してください。

同じ関数を末尾再帰的に実行したものがこちら。

function tailrecsum(x, running_total = 0) {
    if (x === 0) {
        return running_total;
    } else {
        return tailrecsum(x - 1, running_total + x);
    }
}

を呼び出すと、次のような一連の流れになります。 tailrecsum(5) は、（実質的には tailrecsum(5, 0) というのは、デフォルトの第2引数があるからです)。

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

末尾再帰の場合、再帰呼び出しの各評価で running_total が更新されます。

注意: オリジナルの回答では、Pythonの例を使用しています。Python のインタプリタでは テールコールの最適化 . しかし、テールコールの最適化は ECMAScript 2015 の仕様の一部である ほとんどのJavaScriptインタプリタでは をサポートしていません。 .