什么是尾递归？
在开始学习Lisp的同时，我遇到了术语"尾递归"。到底是什么意思？
解决方案
回答
我不是Lisp程序员，但我认为这会有所帮助。
基本上，这是一种编程风格，因此递归调用是我们要做的最后一件事。
回答
使用常规递归，每个递归调用都会将另一个条目推入调用堆栈。递归完成后，该应用程序必须将所有条目从头向下弹出。
借助尾递归，编译器可以将堆栈折叠为一个条目，从而节省堆栈空间...大型的递归查询实际上可能导致堆栈溢出。
基本上，可以将尾递归优化为迭代。
回答
尾递归是指递归调用在递归算法中的最后逻辑指令中位于最后。
通常，在递归中，我们有一个基本情况，这是停止递归调用并开始弹出调用堆栈的基础。使用经典示例，尽管C函数比Lisp多，但阶乘函数说明了尾递归。在检查基本情况后，将进行递归调用。
factorial(x, fac) {
if (x == 1)
return fac;
else
return factorial(x-1, x*fac);
}
注意，对阶乘的初始调用必须是阶乘(n，1)，其中n是要为其计算阶乘的数字。
回答
在传统的递归中，典型的模型是先执行递归调用，然后取递归调用的返回值并计算结果。这样，直到我们从每个递归调用中返回后，我们才能获得计算结果。
在尾部递归中，首先执行计算，然后执行递归调用，将当前步骤的结果传递到下一个递归步骤。这导致最后一条语句的格式为((return(recursive-function params)))。基本上，任何给定递归步骤的返回值都与下一个递归调用的返回值相同。
这样的结果是，一旦我们准备好执行下一个递归步骤，就不再需要当前的堆栈框架。这样可以进行一些优化。实际上，使用适当编写的编译器，我们永远都不应使用尾部递归调用来实现堆栈溢出窃笑。只需将当前堆栈帧重用于下一步递归步骤即可。我很确定Lisp会这样做。
回答
这里有一个例子，而不是用语言解释。这是阶乘函数的Scheme版本：
(define (factorial x)
(if (= x 0) 1
(* x (factorial (- x 1)))))
这是尾递归的阶乘版本：
(define factorial
(letrec ((fact (lambda (x accum)
(if (= x 0) accum
(fact (- x 1) (* accum x))))))
(lambda (x)
(fact x 1))))
在第一个版本中，我们会注意到对事实的递归调用被输入到乘法表达式中，因此在进行递归调用时必须将状态保存在堆栈中。在尾递归版本中，没有其他S表达式在等待递归调用的值，并且由于没有其他工作要做，因此不必将状态保存在堆栈中。通常，Scheme尾递归函数使用恒定的堆栈空间。
回答
术语文件说了有关尾递归的定义：
尾递归/n./
如果我们还不满意，请参阅尾递归。
回答
摘自《 Lua编程》一书的摘录显示了如何进行适当的尾递归(在Lua中，但也应适用于Lisp)以及为什么更好。
A tail call [tail recursion] is a kind of goto dressed
as a call. A tail call happens when a
function calls another as its last
action, so it has nothing else to do.
For instance, in the following code,
the call to g is a tail call:
function f (x)
return g(x)
end
After f calls g, it has nothing else
to do. In such situations, the program
does not need to return to the calling
function when the called function
ends. Therefore, after the tail call,
the program does not need to keep any
information about the calling function
in the stack. ...
Because a proper tail call uses no
stack space, there is no limit on the
number of "nested" tail calls that a
program can make. For instance, we can
call the following function with any
number as argument; it will never
overflow the stack:
function foo (n)
if n > 0 then return foo(n - 1) end
end
... As I said earlier, a tail call is a
kind of goto. As such, a quite useful
application of proper tail calls in
Lua is for programming state machines.
Such applications can represent each
state by a function; to change state
is to go to (or to call) a specific
function. As an example, let us
consider a simple maze game. The maze
has several rooms, each with up to
four doors: north, south, east, and
west. At each step, the user enters a
movement direction. If there is a door
in that direction, the user goes to
the corresponding room; otherwise, the
program prints a warning. The goal is
to go from an initial room to a final
room.
This game is a typical state machine,
where the current room is the state.
We can implement such maze with one
function for each room. We use tail
calls to move from one room to
another. A small maze with four rooms
could look like this:
function room1 ()
local move = io.read()
if move == "south" then return room3()
elseif move == "east" then return room2()
else print("invalid move")
return room1() -- stay in the same room
end
end
function room2 ()
local move = io.read()
if move == "south" then return room4()
elseif move == "west" then return room1()
else print("invalid move")
return room2()
end
end
function room3 ()
local move = io.read()
if move == "north" then return room1()
elseif move == "east" then return room4()
else print("invalid move")
return room3()
end
end
function room4 ()
print("congratulations!")
end
因此，当我们进行如下递归调用时，我们会看到：
function x(n) if n==0 then return 0 n= n-2 return x(n) + 1 end
这不是尾部递归，因为在进行递归调用后，我们仍然需要在该函数中做一些事情(加1)。如果输入很高的数字，则可能会导致堆栈溢出。
回答
重要的一点是，尾递归实质上等同于循环。这不仅是编译器优化的问题，还是表达能力的基本事实。这是双向的：我们可以采用任何形式的循环
while(E) { S }; return Q
其中" E"和" Q"是表达式，" S"是语句序列，并将其转换为尾部递归函数
f() = if E then { S; return f() } else { return Q }
当然，必须定义" E"，" S"和" Q"以计算一些变量上的有趣值。例如，循环功能
sum(n) {
int i = 1, k = 0;
while( i <= n ) {
k += i;
++i;
}
return k;
}
等效于尾递归函数
sum_aux(n,i,k) {
if( i <= n ) {
return sum_aux(n,i+1,k+i);
} else {
return k;
}
}
sum(n) {
return sum_aux(n,1,0);
}
(这种尾部递归函数与较少参数的函数的"包装"是常见的函数习语。)
回答
考虑一个简单的函数，该函数将前N个整数相加。 (例如，" sum(5)= 1 + 2 + 3 + 4 + 5 = 15")。
这是一个使用递归的简单JavaScript实现：
function recsum(x) {
if (x===1) {
return x;
} 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))) 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))将会发生的事件序列。
tailrecsum(5, 0) tailrecsum(4, 5) tailrecsum(3, 9) tailrecsum(2, 12) tailrecsum(1, 14) tailrecsum(0, 15) 15
在尾递归的情况下，每次对递归调用进行评估时，都会更新running_total。
注意：原始答案使用了Python中的示例。这些已更改为JavaScript，因为现代JavaScript解释器支持尾部调用优化，而Python解释器则不支持。
回答
这意味着我们无需将指令指针压入堆栈，只需跳转到递归函数的顶部并继续执行即可。这允许函数无限期递归而不会溢出堆栈。
我写了一篇有关该主题的博客文章，其中有一些图形示例显示了堆栈框架的外观。
回答
递归意味着一个调用自身的函数。例如：
(define (un-ended name) (un-ended 'me) (print "How can I get here?"))
Tail-Recursion表示结束函数的递归：
(define (un-ended name) (print "hello") (un-ended 'me))
可以看到，无休止的函数(在Scheme术语中，过程)所做的最后一件事就是调用自身。另一个(更有用的)示例是：
(define (map lst op)
(define (helper done left)
(if (nil? left)
done
(helper (cons (op (car left))
done)
(cdr left))))
(reverse (helper '() lst)))
在帮助程序过程中，如果剩下的不为零，它做的最后一件事是调用自身(AFTER CONS事物和CDR事物)。基本上，这就是映射列表的方式。
尾递归具有很大的优势，即中断器(或者编译器，取决于语言和供应商)可以对其进行优化，并将其转换为等同于while循环的内容。实际上，在Scheme传统中，大多数" for"和" while"循环都是以尾递归方式完成的(据我所知，没有for和while)。
回答
这是前面提到的tailrecsum函数的Perl 5版本。
sub tail_rec_sum($;$){
my( $x,$running_total ) = (@_,0);
return $running_total unless $x;
@_ = ($x-1,$running_total+$x);
goto &tail_rec_sum; # throw away current stack frame
}
回答
在Java中，这是Fibonacci函数的可能的尾部递归实现：
public int tailRecursive(final int n) {
if (n <= 2)
return 1;
return tailRecursiveAux(n, 1, 1);
}
private int tailRecursiveAux(int n, int iter, int acc) {
if (iter == n)
return acc;
return tailRecursiveAux(n, ++iter, acc + iter);
}
将此与标准递归实现进行比较：
public int recursive(final int n) {
if (n <= 2)
return 1;
return recursive(n - 1) + recursive(n - 2);
}
回答
这是比较两个功能的快速代码段。第一种是用于查找给定数字阶乘的传统递归。第二种使用尾递归。
非常简单直观。
判断递归函数是否为尾递归的简单方法是在基本情况下是否返回具体值。这意味着它不会返回1或者true或者类似的东西。然后，它很可能返回方法参数之一的某些变体。
另一种方法是判断递归调用是否没有任何加法，算术，修改等。这意味着它只是一个纯递归调用。
public static int factorial(int mynumber) {
if (mynumber == 1) {
return 1;
} else {
return mynumber * factorial(--mynumber);
}
}
public static int tail_factorial(int mynumber, int sofar) {
if (mynumber == 1) {
return sofar;
} else {
return tail_factorial(--mynumber, sofar * mynumber);
}
}
