虽然开始学习口齿不清，我遇到这个词的尾递归的。这是什么意思？

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

推荐答案

尾递归是很好的描述在previous答案，但我认为，在行动的一个例子有助于说明这一概念。

Tail recursion is well-described in previous answers, but I think an example in action would help to illustrate the concept.

考虑一个简单的功能，其将所述第一N个整数。 （例如：和（5）= 1 + 2 + 3 + 4 + 5 = 15 ）。

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

下面是一个使用递归一个简单的Python实现：

Here is a simple Python implementation that uses recursion:

def recsum(x):
 if x == 1:
  return x
 else:
  return x + recsum(x - 1)

如果你叫 recsum（5），这是Python的跨preTER将评估。

If you called recsum(5), this is what the Python 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)))
15

请注意每一个递归调用怎么了Python的跨preTER开始真正做计算总和的工作之前完成。

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

下面是一个尾递归版本相同的功能：

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

def 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不具有内置的支持，优化掉尾调用，所以没有优势，在Python这样做。但是，您可以使用装饰，以达到最优化。的

Note: As mentioned in the comments, Python doesn't have built-in support for optimizing away tail calls, so there's no advantage to doing this in Python. However, you can use a decorator to achieve the optimization.