当我开始学习口齿不清时,我遇到了“尾部递归”这个词。这到底是什么意思?


当前回答

对我来说,理解尾调用递归的最好方法是递归的一种特殊情况,其中最后一个调用(或尾调用)是函数本身。

比较Python中提供的示例:

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

^递归

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

^尾部递归

正如您在常规递归版本中看到的,代码块中的最后一个调用是x+recsum(x-1)。所以在调用recsum方法之后,还有一个操作是x+。。。

然而,在尾部递归版本中,代码块中的最后一个调用(或尾部调用)是tailrecsum(x-1,running_total+x),这意味着最后一次调用是对方法本身进行的,之后不再进行操作。

这一点很重要,因为这里看到的尾部递归不会使内存增长,因为当底层VM看到一个函数在尾部位置(函数中要计算的最后一个表达式)调用自己时,它会消除当前堆栈帧,这就是所谓的尾部调用优化(TCO)。

EDIT

没有。请记住,上面的示例是用Python编写的,其运行时不支持TCO。这只是一个解释这一点的例子。在Scheme、Haskell等语言中支持TCO

其他回答

如果每个递归情况仅由对函数本身的调用组成,并且可能具有不同的参数,则函数是尾部递归的。或者,尾部递归是没有待定工作的递归。注意,这是一个与编程语言无关的概念。

考虑定义如下的函数:

g(a, b, n) = a * b^n

一种可能的尾部递归公式是:

g(a, b, n) | n is zero = a
           | n is odd  = g(a*b, b,   n-1)
           | otherwise = g(a,   b*b, n/2)

如果您检查g(…)的每一个涉及递归情况的RHS,您会发现整个RHS都是对g(……)的调用,仅此而已。这个定义是尾部递归的。

作为比较,非尾部递归公式可能是:

g'(a, b, n) = a * f(b, n)
f(b, n) | n is zero = 1
        | n is odd  = f(b, n-1) * b
        | otherwise = f(b, n/2) ^ 2

f(…)中的每个递归情况都有一些需要在递归调用之后进行的未决工作。

注意,当我们从“g”到“g”时,我们充分利用了关联性(和交换性)乘法。这并不是偶然的,在大多数需要将递归转换为尾递归的情况下,都会利用这些财产:如果我们想急切地做一些工作,而不是让它等待,我们必须使用关联性之类的东西来证明答案是一样的。

尾部递归调用可以通过向后跳转来实现,而不是使用堆栈进行常规递归调用。注意,检测尾部呼叫或发出向后跳转通常很简单。然而,通常很难重新排列参数,以便向后跳转。由于此优化不是免费的,语言实现可以选择不实现此优化,或者通过使用“tailcall”指令标记递归调用和/或选择更高的优化设置来要求选择加入。

然而,某些语言(例如Scheme)确实需要所有实现来优化尾部递归函数,甚至可能需要所有尾部位置的调用。

在大多数命令式语言中,向后跳转通常被抽象为(while)循环,而尾部递归在优化为向后跳转时,与循环同构。

许多人已经在这里解释了递归。我想引用Riccardo Terrell的《.NET中的并发性,并发和并行编程的现代模式》一书中关于递归的一些优点的一些想法:

“函数递归是FP中迭代的自然方式,因为它避免状态突变。在每次迭代期间,都会传递一个新值而不是被更新(变异)。在里面此外,可以编写递归函数,使您的程序更加模块化,并引入了开发机会并行化。"

以下是同一本书中关于尾部递归的一些有趣注释:

尾部调用递归是一种转换规则递归的技术函数转换为可处理大型输入的优化版本没有任何风险和副作用。注:尾部调用作为优化的主要原因是提高数据位置、内存使用率和缓存使用率。通过做尾巴调用时,被调用者使用与调用者相同的堆栈空间。这减少了记忆压力。它略微改善了缓存,因为存储器被后续调用方重用,并且可以留在缓存中,而不是驱逐旧的缓存线,为新的缓存腾出空间线

术语文件对尾部递归的定义有这样的说法:

尾部递归/n/

如果您还没有厌倦它,请参阅尾部递归。

在传统递归中,典型的模型是首先执行递归调用,然后获取递归调用的返回值并计算结果。通过这种方式,在每次递归调用返回之前,您不会得到计算结果。

在尾部递归中,首先执行计算,然后执行递归调用,将当前步骤的结果传递给下一个递归步骤。这导致最后一条语句的形式为(return(递归函数参数))。基本上,任何给定递归步骤的返回值都与下一个递归调用的返回值相同。

这样做的结果是,一旦准备好执行下一个递归步骤,就不再需要当前堆栈帧。这允许进行一些优化。事实上,使用一个适当编写的编译器,您永远不应该有带有尾部递归调用的堆栈溢出窃笑。只需在下一个递归步骤中重用当前堆栈帧。我很确定Lisp会这么做。

对我来说,理解尾调用递归的最好方法是递归的一种特殊情况,其中最后一个调用(或尾调用)是函数本身。

比较Python中提供的示例:

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

^递归

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

^尾部递归

正如您在常规递归版本中看到的,代码块中的最后一个调用是x+recsum(x-1)。所以在调用recsum方法之后,还有一个操作是x+。。。

然而,在尾部递归版本中,代码块中的最后一个调用(或尾部调用)是tailrecsum(x-1,running_total+x),这意味着最后一次调用是对方法本身进行的,之后不再进行操作。

这一点很重要,因为这里看到的尾部递归不会使内存增长,因为当底层VM看到一个函数在尾部位置(函数中要计算的最后一个表达式)调用自己时,它会消除当前堆栈帧,这就是所谓的尾部调用优化(TCO)。

EDIT

没有。请记住,上面的示例是用Python编写的,其运行时不支持TCO。这只是一个解释这一点的例子。在Scheme、Haskell等语言中支持TCO