当我开始学习口齿不清时,我遇到了“尾部递归”这个词。这到底是什么意思?
当前回答
这里有一个例子,而不是用文字来解释。这是阶乘函数的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尾部递归函数使用常数堆栈空间。
其他回答
我不是Lisp程序员,但我认为这会有所帮助。
基本上,这是一种编程风格,递归调用是最后一件事。
使用常规递归,每个递归调用将另一个条目推送到调用堆栈中。递归完成后,应用程序必须将每个条目向下弹出。
使用尾部递归,根据语言的不同,编译器可以将堆栈折叠为一个条目,这样可以节省堆栈空间。。。大型递归查询实际上会导致堆栈溢出。
基本上,尾部递归可以优化到迭代中。
尾部递归是指递归算法中最后一条逻辑指令中的最后一个递归调用。
通常在递归中,您有一个基本情况,即停止递归调用并开始弹出调用堆栈。使用一个经典的例子,尽管比Lisp更具C语言,阶乘函数说明了尾部递归。递归调用在检查基本情况条件后发生。
factorial(x, fac=1) {
if (x == 1)
return fac;
else
return factorial(x-1, x*fac);
}
对阶乘的初始调用将是阶乘(n),其中fac=1(默认值),n是要计算阶乘的数字。
这是《计算机程序的结构和解释》中关于尾部递归的摘录。
在对比迭代和递归时,我们必须小心不要将递归过程的概念与递归过程。当我们将过程描述为递归时指过程定义所指的句法事实(直接或间接)到程序本身。但当我们将过程描述为遵循一种模式,即线性递归,我们谈论的是过程如何演变,而不是如何编写过程的语法。这似乎令人不安我们将递归过程(如事实iter)称为生成迭代过程。然而,这个过程实际上是迭代的:它的状态被其三个状态变量完全捕获解释器只需要跟踪三个变量执行该过程。过程和程序之间的区别可能是令人困惑的是,大多数通用语言的实现(包括Ada、Pascal和C) 以这样一种方式设计过程消耗的内存量会随着过程调用,迭代。因此,这些语言可以描述迭代仅通过使用专用的“循环构造”来处理例如do、repeat、until、for和while。实施方案不具有此缺陷。它将在恒定空间中执行迭代过程,即使迭代过程由递归过程描述。一具有此属性的实现称为尾部递归。用一个尾部递归实现,可以使用普通过程调用机制,使特殊迭代构造只作为句法糖有用。
在传统递归中,典型的模型是首先执行递归调用,然后获取递归调用的返回值并计算结果。通过这种方式,在每次递归调用返回之前,您不会得到计算结果。
在尾部递归中,首先执行计算,然后执行递归调用,将当前步骤的结果传递给下一个递归步骤。这导致最后一条语句的形式为(return(递归函数参数))。基本上,任何给定递归步骤的返回值都与下一个递归调用的返回值相同。
这样做的结果是,一旦准备好执行下一个递归步骤,就不再需要当前堆栈帧。这允许进行一些优化。事实上,使用一个适当编写的编译器,您永远不应该有带有尾部递归调用的堆栈溢出窃笑。只需在下一个递归步骤中重用当前堆栈帧。我很确定Lisp会这么做。