什么是尾递归? [英] What is tail recursion?

问题描述

在开始学习 lisp 时，我遇到了尾递归这个词.具体是什么意思?

Whilst starting to learn lisp, I've come across the term tail-recursive. What does it mean exactly?

推荐答案

考虑一个将前 N 个自然数相加的简单函数.(例如 sum(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15).

Consider a simple function that adds the first N natural numbers. (e.g. sum(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15).

这是一个使用递归的简单 JavaScript 实现:

Here is a simple JavaScript implementation that uses recursion:

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

如果你调用了 recsum(5)，这就是 JavaScript 解释器会评估的:

If you called recsum(5), this is what the JavaScript interpreter would evaluate:

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 解释器开始实际计算总和之前，每个递归调用都必须完成.

Note how every recursive call has to complete before the JavaScript interpreter begins to actually do the work of calculating the sum.

这是相同函数的尾递归版本:

Here's a tail-recursive version of the same function:

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)，因为默认秒论据).

Here's the sequence of events that would occur if you called tailrecsum(5), (which would effectively be tailrecsum(5, 0), because of the default second argument).

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

在尾递归的情况下，每次对递归调用求值时，running_total 都会更新.

In the tail-recursive case, with each evaluation of the recursive call, the running_total is updated.

注意:原始答案使用了 Python 中的示例.这些已更改为 JavaScript，因为 Python 解释器不支持尾调用优化.然而，虽然尾调用优化是 ECMAScript 2015 的一部分规范，大多数 JavaScript 解释器不支持它.

Note: The original answer used examples from Python. These have been changed to JavaScript, since Python interpreters don't support tail call optimization. However, while tail call optimization is part of the ECMAScript 2015 spec, most JavaScript interpreters don't support it.

这篇关于什么是尾递归?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！