尾递归是如何工作的？

Question

我几乎理解尾递归是如何工作的，以及它与普通递归之间的区别。我 唯一 不理解的是为什么它 不需要 堆栈来记住其返回地址。

// tail recursion
int fac_times (int n, int acc) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

int factorial (int n) {
    return fac_times (n, 1);
}

// normal recursion
int factorial (int n) {
    if (n == 0) return 1;
    else return n * factorial(n - 1);
}

在尾递归函数中，调用自身后没有任何事情需要做，但对我来说这没有意义。

- Alan Coromano

---

尾递归就是“普通”的递归，只是指递归发生在函数的末尾。 - Pete Becker

但是在 IL 级别上，它可以以不同于普通递归的方式实现，从而减少堆栈深度。 - KeithS

顺便提一下，gcc可以在这里的“正常”示例上执行尾递归消除。 - dmckee --- ex-moderator kitten

@Geek - 我是一名C#开发者，所以我的“汇编语言”是MSIL或者简称IL。对于C/C++来说，将IL替换为ASM即可。 - KeithS

@ShannonSeverance 我发现gcc通过简单的检查使用 -O3 和不使用 -O3 产生的汇编代码来实现这一点。链接是早期讨论的内容，涵盖了非常相似的领域，并讨论了实现此优化所必需的内容。 - dmckee --- ex-moderator kitten

Answer 1

编译器只需简单地转换这个东西。

int fac_times (int n, int acc) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

变成像这样：

int fac_times (int n, int acc) {
label:
    if (n == 0) return acc;
    acc *= n--;
    goto label;
}

- Alexey Frunze

---

@Mr.32，我不明白你的问题。我将该函数转换为等效函数，但没有显式递归（即没有显式函数调用）。如果您将逻辑更改为某些或所有情况下都不等效的内容，则确实可能使函数永久循环。 - Alexey Frunze

所以，尾递归之所以有效，仅仅是因为编译器对其进行了优化？否则，从堆栈内存的角度来看，它与普通递归相同吗？ - Alan Coromano

没错。如果编译器无法将递归转化为循环，那么你只能使用递归。不折不扣。 - Alexey Frunze

@AlanDert: 正确。你也可以将尾递归视为“尾调用优化”的一种特殊情况，因为尾调用恰好是对同一函数的调用。通常来说，任何满足尾递归的“没有剩余工作要做”要求，并且其返回值直接返回的尾调用（如果编译器可以以设置被调用函数返回地址的方式进行调用，使其返回地址为进行尾调用的函数的返回地址，而不是从进行尾调用的地址）都可以进行优化。 - Steve Jessop

在 C 语言中，这只是一种优化，并没有被任何标准强制执行，因此可移植的代码不应该依赖它。但是有些语言（Scheme 是一个例子），尾递归优化是由标准强制执行的，因此您不需要担心它会在某些环境中出现堆栈溢出的情况。 - Jan Wrobel

Answer 2

你问为什么“它不需要使用栈来记住它的返回地址”。

我想反过来说。它确实使用栈来记住返回地址。诀窍在于，尾递归发生的函数在栈上有自己的返回地址，当它跳转到被调用的函数时，它将把这个地址作为它自己的返回地址。

具体而言，在没有尾调用优化的情况下：

f: ...
   CALL g
   RET
g:
   ...
   RET

在这种情况下，当调用g时，堆栈的状态如下:

   SP ->  Return address of "g"
          Return address of "f"

另一方面，使用尾调用优化：

f: ...
   JUMP g
g:
   ...
   RET

在这种情况下，当调用g时，堆栈的情况如下:

   SP ->  Return address of "f"

显然，当g返回时，它将返回到调用f的位置。

编辑：上面的例子是一个函数调用另一个函数的情况。当函数调用自身时，机制是相同的。

- Lindydancer

---

这个回答比其他回答好得多。编译器很可能没有用于转换尾递归代码的神奇特殊情况，它只是执行一种正常的最后调用优化，恰巧是调用相同的函数。 - Art

Answer 3

尾递归通常可以通过编译器转换为循环，特别是在使用累加器时。

// tail recursion
int fac_times (int n, int acc = 1) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

将会编译为类似以下的内容：

// accumulator
int fac_times (int n) {
    int acc = 1;
    while (n > 0) {
        acc *= n;
        n -= 1;
    }
    return acc;
}

- mepcotterell

---

没有 Alexey 实现的聪明...是在表扬他。 - Matthieu M.

实际上，结果看起来更简单，但我认为实现这种转换的代码比标签/跳转或仅尾调用消除（请参见Lindydancer的答案）要聪明得多。 - Phob

如果这就是尾递归的全部，那么为什么人们会对它如此兴奋呢？我没有看到有人对while循环感到兴奋。 - Buh Buh

@BuhBuh：这个没有使用stackoverflow，并且避免了参数的堆栈推入/弹出。对于像这样的紧密循环，它可以产生天壤之别。除此之外，人们不应该感到兴奋。 - Mooing Duck

Answer 4

递归函数必须包含两个要素：

1. 递归调用
2. 一个保存返回值的位置。

"普通"递归函数会将(2)保存在堆栈帧中。

普通递归函数的返回值由两种类型的值组成:

• 其他的返回值
• 本函数计算结果的值

让我们看一下你的例子:

int factorial (int n) {
    if (n == 0) return 1;
    else return n * factorial(n - 1);
}

例如，框架f(5)“存储”自己计算的结果（5）和f(4)的值。如果我调用factorial(5)，就在堆栈调用开始折叠之前，我有：

 [Stack_f(5): return 5 * [Stack_f(4): 4 * [Stack_f(3): 3 * ... [1[1]]

请注意，每个堆栈存储函数所在作用域以及我提到的值。因此，递归函数f的内存使用量为O(x)，其中x是必须进行递归调用的次数。因此，如果我需要1kb的RAM来计算阶乘(1)或阶乘(2)，那么我需要 ~100k 来计算阶乘(100)等。

一个尾递归函数将 (2) 放入其参数中。

在尾递归中，我使用参数将部分计算的结果传递给下一个递归帧。让我们看看我们的阶乘示例，尾递归：

int factorial (int n) {
    int helper(int num, int accumulated)
        {
            if num == 0 return accumulated
            else return helper(num - 1, accumulated*num)
        }
    return helper(n, 1)    
}

让我们来看一下factorial(4)中的帧：

[Stack f(4, 5): Stack f(3, 20): [Stack f(2,60): [Stack f(1, 120): 120]]]]

看到区别了吗？在“常规”递归调用中，返回函数会递归组合最终值。在尾递归中，它们仅引用基本情况（最后一个被评估的）。我们称累加器为跟踪旧值的参数。

递归模板

常规递归函数如下：

type regular(n)
    base_case
    computation
    return (result of computation) combined with (regular(n towards base case))

为了将其转化为尾递归，我们需要：

• 引入一个带有累加器的辅助函数
• 在主函数内运行带有累加器设为基础情况的辅助函数。

看：

type tail(n):
    type helper(n, accumulator):
        if n == base case
            return accumulator
        computation
        accumulator = computation combined with accumulator
        return helper(n towards base case, accumulator)
    helper(n, base case)

看到区别了吗？

尾调用优化

由于在尾调用栈的非边界情况下没有状态被存储，它们并不那么重要。一些语言/解释器会使用新栈替换旧的栈。因此，在这些情况下，尾调用表现得就像一个for循环，由于没有栈帧限制调用次数。

是否进行优化取决于您的编译器。

- Lucas Ribeiro

Answer 5

这是一个简单的例子，展示了递归函数的工作原理：

long f (long n)
{

    if (n == 0) // have we reached the bottom of the ocean ?
        return 0;

    // code executed in the descendence

    return f(n-1) + 1; // recurrence

    // code executed in the ascendence

}

尾递归是一种简单的递归函数，其中递归在函数末尾完成，因此没有代码在上升过程中执行，这有助于大多数高级编程语言的编译器进行所谓的尾递归优化，也有一个更复杂的优化称为尾递归模。

- Khaled.K

Answer 6

递归函数是一种函数，它自我调用。它允许程序员使用最少的代码编写高效的程序。缺点是，如果编写不当，可能会导致无限循环和其他意外结果。我将解释简单递归函数和尾递归函数。为了编写简单递归函数，第一点要考虑的是什么时候决定退出循环，即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);

实际处理要做什么？

让我逐一分解任务，以便更容易理解。

如果我运行fact(4)，让我们看看内部会发生什么。

1. 将n替换为4

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

如果循环失败，则转到else循环，因此返回4 * fact(3) 在堆栈内存中，我们有4 * fact(3) （将n=3代入）

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

如果循环失败，则进入else循环。

因此，它返回`3 * fact(2)`。

请记住我们调用了`4 * fact(3)`。

`fact(3)`的输出为`3 * fact(2)`。

到目前为止，堆栈中有`4 * fact(3) = 4 * 3 * fact(2)`。

在堆栈内存中，我们有`4 * 3 * fact(2)`。

将n替换为2。

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

如果循环失败，则进入else循环，所以它返回2 * fact(1)。

记住我们调用了4 * 3 * fact(2)。

fact(2)的输出为2 * fact(1)。

到目前为止，堆栈中有4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)。

在堆栈内存中，我们有4 * 3 * 2 * fact(1)。

将n替换为1。

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

如果循环条件为真，则返回1。记住我们调用了4 * 3 * 2 * fact(1)。fact(1)的输出为1。到目前为止，堆栈中有4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1。最终，fact(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循环，然后返回fact(3, 4)。

在堆栈内存中，我们有fact(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循环。

因此，它返回fact（2,12）。

在堆栈内存中，我们有fact（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循环，因此它返回fact(1,24)。

在堆栈内存中，我们有fact(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时，输出结果为24。最终，fact(4,1)的结果为24。

- Noordeen

Answer 7

编译器足够智能，可以理解尾递归。如果在从递归调用返回时，没有挂起的操作并且递归调用是最后一条语句，则属于尾递归的范畴。 编译器基本上执行尾递归优化，删除堆栈实现。请考虑下面的代码。

void tail(int i) {
    if(i<=0) return;
    else {
     system.out.print(i+"");
     tail(i-1);
    }
   }

经过优化后，上述代码转换为下面的代码。

void tail(int i) {
    blockToJump:{
    if(i<=0) return;
    else {
     system.out.print(i+"");
     i=i-1;
     continue blockToJump;  //jump to the bolckToJump
    }
    }
   }

这就是编译器如何进行尾递归优化的方式。

- Varunnuevothoughts

Answer 8

我的答案更像是一个猜测，因为递归是与内部实现相关的东西。

在尾递归中，递归函数在同一函数的末尾被调用。编译器可能会以以下方式进行优化：

1. 让正在运行的函数结束（即使用的堆栈被回收）
2. 将要用作函数参数的变量存储在临时存储器中
3. 在此之后，使用临时存储的参数再次调用函数

正如您所看到的，我们在下一次迭代相同函数之前结束了原始函数，因此我们实际上没有“使用”堆栈。

但我认为，如果函数内部有需要调用的析构函数，则此优化可能不适用。

- iammilind