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


当前回答

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

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

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

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

其他回答

重要的一点是尾部递归本质上等同于循环。这不仅仅是一个编译器优化的问题,而是一个关于表现力的基本事实。这是双向的:你可以采取任何形式的循环

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);
}

(用参数较少的函数“包装”尾部递归函数是一种常见的函数习惯用法。)

尾部递归是指递归算法中最后一条逻辑指令中的最后一个递归调用。

通常在递归中,您有一个基本情况,即停止递归调用并开始弹出调用堆栈。使用一个经典的例子,尽管比Lisp更具C语言,阶乘函数说明了尾部递归。递归调用在检查基本情况条件后发生。

factorial(x, fac=1) {
  if (x == 1)
     return fac;
   else
     return factorial(x-1, x*fac);
}

对阶乘的初始调用将是阶乘(n),其中fac=1(默认值),n是要计算阶乘的数字。

为了理解尾部调用递归和非尾部调用递归之间的一些核心区别,我们可以探索这些技术的.NET实现。

这是一篇包含C#、F#和C++\CLI中的一些示例的文章:C#、F#和C++/CLI中的尾部递归冒险。

C#没有针对尾部调用递归进行优化,而F#进行了优化。

原理的差异涉及循环与Lambda演算。C#的设计考虑到了循环,而F#是基于Lambda演算的原理构建的。有关Lambda微积分原理的一本非常好(免费)的书,请参阅Abelson、Sussman和Sussman的《计算机程序的结构和解释》。

关于F#中的尾部调用,有关非常好的介绍性文章,请参阅F#中尾部调用的详细介绍。最后,这里有一篇文章介绍了非尾部递归和尾部调用递归(在F#中)之间的区别:尾部递归与F sharp中的非尾部递归。

如果您想了解C#和F#之间尾部调用递归的一些设计差异,请参阅在C#和F#中生成尾部调用操作码。

如果您非常想知道哪些条件阻止C#编译器执行尾部调用优化,请参阅本文:JIT CLR尾部调用条件。

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

尾部递归/n/

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

使用常规递归,每个递归调用将另一个条目推送到调用堆栈中。递归完成后,应用程序必须将每个条目向下弹出。

使用尾部递归,根据语言的不同,编译器可以将堆栈折叠为一个条目,这样可以节省堆栈空间。。。大型递归查询实际上会导致堆栈溢出。

基本上,尾部递归可以优化到迭代中。