当我开始学习口齿不清时,我遇到了“尾部递归”这个词。这到底是什么意思?
当前回答
术语文件对尾部递归的定义有这样的说法:
尾部递归/n/
如果您还没有厌倦它,请参阅尾部递归。
其他回答
这里有一个例子,而不是用文字来解释。这是阶乘函数的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尾部递归函数使用常数堆栈空间。
这本摘自《Lua编程》一书的摘录展示了如何进行正确的尾部递归(在Lua中,但也应适用于Lisp)以及为什么它更好。
尾部调用[尾部递归]是一种goto-dressed作为呼叫。当函数调用另一个作为其最后一个行动,所以它没有其他事情可做。例如在以下代码中,对g的调用是尾调用:函数f(x)返回g(x)终止在f调用g之后,它没有其他内容在这种情况下,程序不需要返回调用函数时调用的函数末端。因此在尾呼之后,程序不需要保留任何有关调用函数的信息在堆栈中。。。因为正确的尾呼使用no堆栈空间一个程序可以生成。例如,我们可以使用任意数字作为自变量;它永远不会溢出堆栈:函数foo(n)如果n>0,则返回foo(n-1)end终止…正如我前面所说的,尾呼是有点后顾之忧。因此,一个非常有用的正确的尾部调用在Lua用于编程状态机。此类应用程序可以代表功能状态;更改状态是去(或打电话)一个特定的作用例如,让我们考虑一个简单的迷宫游戏。迷宫有几个房间,每个房间最多四个门:北、南、东和西在每个步骤中,用户输入移动方向。如果有门在该方向上,用户将相应的房间;否则程序打印警告。目标是从最初的房间到最后的房间房间该游戏是典型的状态机,其中当前房间是状态。我们可以用一个每个房间的功能。我们用尾巴从一个房间移动到另一个有四个房间的小迷宫可能看起来像这样:功能室1()本地移动=io.read()如果移动==“南”,则返回房间3()elseif move==“east”然后返回room2()否则打印(“无效移动”)返回房间1()--呆在同一个房间终止终止功能室2()本地移动=io.read()如果move==“south”,则返回room4()elseif move==“west”然后返回房间1()否则打印(“无效移动”)返回室2()终止终止功能室3()本地移动=io.read()如果move==“north”,则返回room1()elseif move==“east”然后返回room4()否则打印(“无效移动”)返回室3()终止终止功能室4()打印(“恭喜!”)终止
因此,当您进行如下递归调用时:
function x(n)
if n==0 then return 0
n= n-2
return x(n) + 1
end
这不是尾部递归的,因为在进行递归调用之后,您仍然需要在该函数中做一些事情(添加1)。如果输入的数字很高,可能会导致堆栈溢出。
术语文件对尾部递归的定义有这样的说法:
尾部递归/n/
如果您还没有厌倦它,请参阅尾部递归。
在传统递归中,典型的模型是首先执行递归调用,然后获取递归调用的返回值并计算结果。通过这种方式,在每次递归调用返回之前,您不会得到计算结果。
在尾部递归中,首先执行计算,然后执行递归调用,将当前步骤的结果传递给下一个递归步骤。这导致最后一条语句的形式为(return(递归函数参数))。基本上,任何给定递归步骤的返回值都与下一个递归调用的返回值相同。
这样做的结果是,一旦准备好执行下一个递归步骤,就不再需要当前堆栈帧。这允许进行一些优化。事实上,使用一个适当编写的编译器,您永远不应该有带有尾部递归调用的堆栈溢出窃笑。只需在下一个递归步骤中重用当前堆栈帧。我很确定Lisp会这么做。
这里是前面提到的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
}