当我开始学习口齿不清时,我遇到了“尾部递归”这个词。这到底是什么意思?
当前回答
许多人已经在这里解释了递归。我想引用Riccardo Terrell的《.NET中的并发性,并发和并行编程的现代模式》一书中关于递归的一些优点的一些想法:
“函数递归是FP中迭代的自然方式,因为它避免状态突变。在每次迭代期间,都会传递一个新值而不是被更新(变异)。在里面此外,可以编写递归函数,使您的程序更加模块化,并引入了开发机会并行化。"
以下是同一本书中关于尾部递归的一些有趣注释:
尾部调用递归是一种转换规则递归的技术函数转换为可处理大型输入的优化版本没有任何风险和副作用。注:尾部调用作为优化的主要原因是提高数据位置、内存使用率和缓存使用率。通过做尾巴调用时,被调用者使用与调用者相同的堆栈空间。这减少了记忆压力。它略微改善了缓存,因为存储器被后续调用方重用,并且可以留在缓存中,而不是驱逐旧的缓存线,为新的缓存腾出空间线
其他回答
这本摘自《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)。如果输入的数字很高,可能会导致堆栈溢出。
我不是Lisp程序员,但我认为这会有所帮助。
基本上,这是一种编程风格,递归调用是最后一件事。
这意味着不需要将指令指针推到堆栈上,只需跳到递归函数的顶部并继续执行即可。这允许函数无限递归而不会溢出堆栈。
我写了一篇关于这个主题的博客文章,里面有堆栈框架的图形示例。
这是《计算机程序的结构和解释》中关于尾部递归的摘录。
在对比迭代和递归时,我们必须小心不要将递归过程的概念与递归过程。当我们将过程描述为递归时指过程定义所指的句法事实(直接或间接)到程序本身。但当我们将过程描述为遵循一种模式,即线性递归,我们谈论的是过程如何演变,而不是如何编写过程的语法。这似乎令人不安我们将递归过程(如事实iter)称为生成迭代过程。然而,这个过程实际上是迭代的:它的状态被其三个状态变量完全捕获解释器只需要跟踪三个变量执行该过程。过程和程序之间的区别可能是令人困惑的是,大多数通用语言的实现(包括Ada、Pascal和C) 以这样一种方式设计过程消耗的内存量会随着过程调用,迭代。因此,这些语言可以描述迭代仅通过使用专用的“循环构造”来处理例如do、repeat、until、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
}