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


当前回答

递归函数是一个自己调用的函数

它允许程序员用最少的代码编写高效的程序。

缺点是,如果编写不当,它们可能会导致无限循环和其他意外结果。

我将解释简单递归函数和尾部递归函数

为了编写简单的递归函数

首先要考虑的一点是你应该什么时候决定出来是if循环的第二个问题是,如果我们是自己的职能部门,我们应该做什么

从给定的示例中:

public static int fact(int n){
  if(n <=1)
     return 1;
  else 
     return n * fact(n-1);
}

从上面的例子中

if(n <=1)
     return 1;

是何时退出循环的决定因素

else 
     return n * fact(n-1);

是否要进行实际处理

为了便于理解,让我逐一完成任务。

让我们看看如果我运行事实(4),内部会发生什么

替换n=4

public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

如果循环失败,则转到else循环因此它返回4*事实(3)

在堆栈内存中,我们有4*事实(3)替换n=3

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

如果循环失败,则转到else循环

因此它返回3*事实(2)

记住我们称之为“4*事实”(3)``

事实(3)的输出=3*事实(2)

到目前为止,堆栈具有4*事实(3)=4*3*事实(2)

在堆栈内存中,我们有4*3*事实(2)替换n=2

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

如果循环失败,则转到else循环

因此它返回2*事实(1)

记住我们称之为4*3*事实(2)

事实(2)的输出=2*事实(1)

到目前为止,堆栈具有4*3*事实(2)=4*3*2*事实(1)

在堆栈内存中,我们有4*3*2*事实(1)替换n=1

public static int fact(1){
  if(1 <=1)
     return 1;
  else 
     return 1 * fact(1-1);
}

如果循环为真

所以它返回1

记住我们称之为4*3*2*事实(1)

事实(1)的输出=1

到目前为止,堆栈具有4*3*2*事实(1)=4*3*2*1

最后,事实(4)的结果=4*3*2*1=24

尾部递归将是

public static int fact(x, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(x-1, running_total*x);
    }
}

替换n=4

public static int fact(4, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(4-1, running_total*4);
    }
}

如果循环失败,则转到else循环因此它返回事实(3,4)

在堆栈内存中,我们有事实(3,4)替换n=3

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

如果循环失败,则转到else循环

因此它返回事实(2,12)

在堆栈内存中,我们有事实(2,12)替换n=2

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

如果循环失败,则转到else循环

因此它返回事实(1,24)

在堆栈内存中,我们有事实(1,24)替换n=1

public static int fact(1, running_total=24) {
    if (x==1) {
        return running_total;
    } else {
        return fact(1-1, 24*1);
    }
}

如果循环为真

因此它返回running_total

running_total=24的输出

最后,事实(4,1)的结果=24

其他回答

为了理解尾部调用递归和非尾部调用递归之间的一些核心区别,我们可以探索这些技术的.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尾部调用条件。

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

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

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

尾部递归是你现在的生活。您不断重复使用相同的堆栈帧,因为没有理由或方法返回到“先前”帧。过去已经结束,可以抛弃。你得到一帧,永远走向未来,直到你的过程不可避免地消亡。

当您考虑到某些进程可能会使用额外的帧,但如果堆栈没有无限增长,则仍然被认为是尾部递归时,这种类比就失败了。

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

考虑定义如下的函数:

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)循环,而尾部递归在优化为向后跳转时,与循环同构。

这里有一个例子,而不是用文字来解释。这是阶乘函数的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尾部递归函数使用常数堆栈空间。