关于尾调用优化的问题

Question

据我所知，进行尾调用优化有一个前提条件就是递归点应该是函数中的最后一句，递归调用的结果应该立即返回。但是为什么？

以下是 TCO 的有效示例：

int factorial(int num) {
  if (num == 1 || num == 0)
    return 1;
  return num * factorial(num - 1);
}

那么，有了规则，下面的代码也可以优化吗？为什么不呢？

#include <stdio.h>
int factorial(int num) {
  if (num == 1 || num == 0)
    return 1;
  int temp = num * factorial(num - 1);
  printf("%d", temp);
  return temp;
}

我想知道我应该如何向其他人解释为什么上述规则对于拥有 TCO 是必要的。但不仅仅是简单的跟随。

Answer 1

the result of the recursive call should be returned immediately. But why?

那是因为为了优化尾部调用，您需要将最终的递归调用转换为简单的“跳转”指令。当您这样做时，您只是在“替换”函数参数，然后重新启动该函数。

这只有在您可以“丢弃”当前堆栈帧并再次将其用于同一功能（可能覆盖它）时才有可能。如果你需要记住一个值来做更多的计算然后 return，你不能使用相同的堆栈帧进行递归调用（即不能将“调用”变成“跳转”），因为它可能 erase/modify 在 returning.

之前你想记住的值

此外，如果您的函数非常简单（就像您的函数一样），则有可能根本不使用堆栈来编写它（可能 return 地址除外），并且只将数据存储在寄存器中。即使在这种情况下，如果您需要记住 returning.

之前的值之一，您也不想跳转到相同的函数（使用相同的寄存器）

Here is a valid example for TCO:

int factorial(int num) {
  if (num == 1 || num == 0)
    return 1;
  return num * factorial(num - 1);
}

这对 TCO 无效！你正在做 return num * <recursive-call>。递归调用不是函数做的最后一件事，在 returning 之前有一个乘法。和写一样：

int factorial(int num) {
    if (num == 1 || num == 0)
        return 1;
    int tmp = factorial(num - 1);
    tmp *= num;
    return tmp;
}

can the below code be optimized too?

不！同样，那里根本没有尾声，而且更加明显。您首先进行递归调用，然后进行一些其他操作（乘法和 printf），然后是 returning。这不能被编译器优化为尾调用。

另一方面，以下代码可以优化为尾调用：

int factorial(int n, int x) {
    if (n == 1)
        return x;
    int tmp = factorial(n - 1, n * x);
    return tmp;
}

您不必在函数的最后一行进行递归调用。重要的是你不要在中间工作（在递归调用和 return 语句之间），例如调用其他函数或进行额外的计算。

重要提示：请注意，无法执行经典 TCO 的事实并不意味着编译器无法以其他方式优化您的代码。事实上，您的第一个函数非常简单，以至于在 x86-64 上使用 GCC 至少 -O2 编译时，它只是从递归转换为迭代（它基本上变成了一个循环）。我上面的示例也是如此，编译器只是不关心 TCO，它认为在这种情况下可以进行更好的优化。

这是 GCC 11 在 x86-64 上生成的第一个函数的汇编程序转储（Godbolt link 如果您想使用它）。如果您不熟悉 x86：num 参数在 edi 中，eax 用于 return 值。

factorial:
        mov     eax, 1
        cmp     edi, 1
        jbe     .L1
.L2:
        mov     edx, edi
        sub     edi, 1
        imul    eax, edx
        cmp     edi, 1
        jne     .L2
.L1:
        ret

Answer 2

函数的每次调用都会创建一个堆栈帧，其中包含通过参数传递给该函数的任何数据。如果一个函数调用另一个函数（包括自身）一个新的栈帧被压入栈中。当一个函数完全完成时，它的帧从堆栈中弹出。

堆栈内存有限。如果我们尝试将太多帧压入堆栈，则会出现堆栈溢出错误。

尾调用优化发挥作用的地方在于，如果在尾调用之后没有剩余工作可完成，则识别函数已完成。

考虑一种对一系列数字进行递归求和的方法。

int sum(int start, int stop) {
    if (start == stop) {
        return start;
    }
    else {
        return start + sum(start + 1, stop);
    }
}

如果我们调用 sum(1, 5) 递归类似于：

sum(1, 5)
1 + sum(2, 5)
1 + 2 + sum(3, 5)
1 + 2 + 3 + sum(4, 5)
1 + 2 + 3 + 4 + sum(5, 5)
1 + 2 + 3 + 4 + 5

必须创建几个堆栈框架来保存它。

通常需要建立一个值的东西的尾调用优化涉及传递给函数的 accumulator 参数。

int sum_tco(int start, int stop, int acc) {
    if (start == stop) {
        return start + acc;
    }
    else {
        return sum_tco(start + 1, stop, start + acc);
    }
}

现在考虑递归是什么样的：

sum_tco(1, 5, 0)
sum_tco(2, 5, 1 + 0)
sum_tco(3, 5, 2 + 1 + 0)
sum_tco(4, 5, 3 + 2 + 0)
sum_tco(5, 5, 5 + 4 + 3 + 2 + 1 + 0)
5 + 4 + 3 + 2 + 1 + 0

我们不需要知道 sum(1, 5, 0) 或 sum(3, 5, 2 + 1 + 0) 的结果是什么就可以知道 sum(5, 5, 5 + 4 + 3 + 2 + 1 + 0) 的结果是什么，您的计算机也不需要。

聪明的编译器会意识到这一点，并在运行时删除所有先前的堆栈帧。有了TCO，无论这个函数递归调用多少次，它都不会溢出堆栈。

（关于堆栈行为的描述已经概括，并非旨在深入技术，而是为了展示 TCO 的一般概念。）

关于尾调用优化的问题

Question regarding tail call optimization

c

tail-call-optimization