g++中尾递归的问题

Question

我在C++中尝试使用尾递归函数，但使用g++编译器时遇到了一些问题。

当numbers[]的大小超过几百个整数时，以下代码会导致堆栈溢出。检查由g++为以下代码生成的汇编代码，发现twoSum_Helper正在执行递归的call指令。

问题是以下哪一个导致了这个问题？

• 我忽略了防止尾递归的错误。
• 我在使用g++时犯了一个错误。
• g++编译器中检测尾递归函数的缺陷。

我使用的编译命令是g++ -O3 -Wall -fno-stack-protector test.c，在MinGW上通过g++ 4.5.0编译，操作系统是Windows Vista x64。

struct result
{
    int i;
    int j;
    bool found;
};

struct result gen_Result(int i, int j, bool found)
{
    struct result r;
    r.i = i;
    r.j = j;
    r.found = found;
    return r;
}

// Return 2 indexes from numbers that sum up to target.
struct result twoSum_Helper(int numbers[], int size, int target, int i, int j)
{
    if (numbers[i] + numbers[j] == target)
        return gen_Result(i, j, true);
    if (i >= (size - 1))
        return gen_Result(i, j, false);
    if (j >= size)
        return twoSum_Helper(numbers, size, target, i + 1, i + 2);
    else
        return twoSum_Helper(numbers, size, target, i, j + 1);
}

- Swiss

---

你是否已经尝试过分别进行条件增量，并仅使用增加后的参数进行一次递归调用？这种方法可能不如你的示例那么好看，但它可能会帮助你解决问题。 - stefaanv

@stefaanv 是的，但都没有成功。看起来调用是在 else 语句上发生的，但无论如何调整都不能使其使用 jmp 而不是 call。 - Swiss

如果您使用单个语句，例如 return twoSum_Helper(numbers, size, target, i + j_ge_size, j_ge_size ? i + 2 : j + 1)，其中 j_ge_size 是 bool j >= size，它是否有效？（根据自己的喜好进行隐式转换）。 - Tony Delroy

@Tony汇编仍然对自身进行调用，相当于上面的else子句。 - Swiss

汤姆在 https://dev59.com/vXVD5IYBdhLWcg3wRpaX 中做出了有趣的观察 - 他的尾递归需要函数是静态的...？ - Tony Delroy

@Tony：Tom没有说过这个，这是错误的。Tom说如果你将函数链接改为extern，TCO就不再适用——这完全不同。外部链接将有效地推迟调用解析到链接时间，由于GCC默认仅执行非常有限的链接时优化，因此TCO不再适用。但是，函数并不需要是static才能应用此方法。 - Konrad Rudolph

Answer 1

在C或C++中，尾调用优化非常有限，几乎是不可能的。原因在于，通常没有安全的方式可以从传递指针或引用到任何本地变量的函数中进行尾调用（作为所讨论的调用的参数，或者实际上在同一函数中的任何其他调用中）——这当然正在发生在C/C++领域中的各个地方，并且几乎是不可避免的。

你看到的问题可能与此有关：GCC可能通过将调用者堆栈上分配的隐藏变量的地址传递给被调用者来编译返回结构体，从而使其进入以上情况。

- Andreas Rossberg

Answer 2

尝试使用-O2而不是-O3进行编译。

如何检查gcc是否执行尾递归优化？

好吧，无论如何O2都不起作用。唯一有效的方法似乎是将result对象返回到作为参数给定的引用中。

但实际上，更容易的方法是删除尾调用并使用循环代替。TCO用于优化在内联或进行积极展开时发现的尾调用，但您不应该尝试在处理大值时使用递归。

- BatchyX

---

如果你好奇的话，优化尾递归的标志是-foptimize-sibling-calls，它包含在-O2、-O3和-Os中。 - Swiss

好的，我要链接到的答案提供了一个情况，其中O2有效，但O3无效。 - BatchyX

Answer 3

我无法让g++ 4.4.0（在mingw下）执行尾递归，即使是在这个简单的函数中：

static void f (int x)
  {
  if (x == 0) return ;
  printf ("%p\n", &x) ; // or cout in C++, if you prefer
  f (x - 1) ;
  }

我尝试过-O3，-O2，-fno-stack-protector，C和C++变体。没有尾递归。

- TonyK

Answer 4

尝试将您的代码更改为：

// Return 2 indexes from numbers that sum up to target.
struct result twoSum_Helper(int numbers[], int size, int target, int i, int j)
{
    if (numbers[i] + numbers[j] == target)
        return gen_Result(i, j, true);
    if (i >= (size - 1))
        return gen_Result(i, j, false);

    if(j >= size)
        i++; //call by value, changing i here does not matter
    return twoSum_Helper(numbers, size, target, i, i + 1);
}

编辑：根据提问者的评论，删除了不必要的参数。

// Return 2 indexes from numbers that sum up to target.
struct result twoSum_Helper(int numbers[], int size, int target, int i)
{
    if (numbers[i] + numbers[i+1] == target || i >= (size - 1))
        return gen_Result(i, i+1, true);

    if(i+1 >= size)
        i++; //call by value, changing i here does not matter
    return twoSum_Helper(numbers, size, target, i);
}

- ted

---

这可能会起作用，但不幸的是它违背了我测试的总体思路。 - Swiss

此外，在每次递归调用中，j 不一定总是等于 i+1。 - Swiss

@Swiss，我刚刚重写了你代码的底部行，并保留了函数签名，但既然你要求了，我改变了签名并将其缩短了一点。 - ted

@Swiss 如果这个方法可以工作，那么问题可能是你有两个递归点。正如示例所示，这可以很容易地重写（就像使用循环也可以消除递归一样，我认为有一个定理可以证明这一点，因为我没有快速找到它，所以在维基百科中有一个部分提到了这一点）。 - ted

Answer 5

我会看两件事情。

1. if语句中的返回调用将在当前函数的堆栈帧中为else设置一个分支目标，需要在调用后解决（这意味着任何TCO尝试都无法覆盖执行堆栈帧，从而抵消TCO）。

2. numbers[]数组参数是一个可变长度数据结构，也可能阻止TCO，因为在TCO中以一种或另一种方式使用相同的堆栈帧。如果调用是自引用的（像你的一样），那么它将使用新调用的值/引用覆盖堆栈定义的变量（或局部定义）。如果尾调用是到另一个函数，则它将用新函数覆盖整个堆栈帧（在A => B => C可以进行TCO的情况下，在执行期间TCO可以使其看起来像A => C）。我会尝试一个指针。

我已经有几个月没有用C++构建任何东西了，所以我没有运行任何测试，但我认为其中一个/两个正在阻止优化。

- Brandon

---

没有“numbers[]数组参数”，这是误导性的（而且它肯定不是可变长度的）。只有一个指针参数，堆栈帧始终被相同地使用，这几乎肯定不是原因。而if-else也不是原因。每个递归都需要一个基本情况，因此需要一个条件语句。 - Konrad Rudolph

自从学习C++以来已经有一段时间了，我知道它是一个指针，谢谢。不过我认为条件语句才是问题的根源，递归确实需要一个基本情况，但尾调用优化意味着在递归调用完成后，堆栈上没有剩余的指令，为了让编译器进行优化，递归调用必须是帧中的最后一条语句，第二个IF语句仍然有一个分支目标，在执行堆栈中跟随ELSE之后。虽然它是逻辑上的最后一条语句，但不是物理上的（当汇编代码在内存中时）。 - Brandon

我确实是指第三个IF（决定下一个自引用递归调用的那个）。 - Brandon

Answer 6

C/C++ 对尾调用优化（TCO）的支持有限。

因此，如果代码依赖于 TCO 来避免堆栈溢出，最好使用循环重写它。否则需要进行一些自动测试以确保代码已经被优化。

通常情况下，TCO 可能会被抑制：

• 将递归函数中对象的指针传递给外部函数（在 C++ 中还可以通过引用传递这样的对象）；
• 即使尾递归是有效的（析构函数在尾部 return 语句之前被调用），也会抑制具有非平凡析构函数的局部对象，例如 为什么 g++ 没有尾调用优化而 gcc 有？

这里TCO被返回值为结构体所困惑。 如果所有递归调用的结果都写入到在其他函数twoSum中分配的同一内存地址中，就可以解决这个问题（类似于https://stackoverflow.com/a/30090390/4023446中对尾递归未发生的回答）。

struct result
{
    int i;
    int j;
    bool found;
};

struct result gen_Result(int i, int j, bool found)
{
    struct result r;
    r.i = i;
    r.j = j;
    r.found = found;
    return r;
}

struct result* twoSum_Helper(int numbers[], int size, int target,
    int i, int j, struct result* res_)
{
    if (i >= (size - 1)) {
        *res_ = gen_Result(i, j, false);
        return res_;
    }
    if (numbers[i] + numbers[j] == target) {
        *res_ = gen_Result(i, j, true);
        return res_;
    }
    if (j >= size)
        return twoSum_Helper(numbers, size, target, i + 1, i + 2, res_);
    else
        return twoSum_Helper(numbers, size, target, i, j + 1, res_);
}

// Return 2 indexes from numbers that sum up to target.
struct result twoSum(int numbers[], int size, int target)
{
    struct result r;
    return *twoSum_Helper(numbers, size, target, 0, 1, &r);
}

twoSum_Helper的所有递归调用中，res_指针的值都是恒定的。 可以在汇编输出（使用-S标志）中看到，即使有两个递归退出点，twoSum_Helper尾递归也被优化为循环。

编译选项：g++ -O2 -S（g++版本4.7.2）。

- Orest Hera

Answer 7

我听别人抱怨说，在gcc中优化了尾递归，但在g++中没有。 你能试着使用gcc吗？

- Lasse Nielsen

Answer 8

由于twoSum_Helper代码调用了自身，所以汇编显示了确切的发生情况，这一点并不令人惊讶。这就是递归的全部意义 :-) 因此，这与g++无关。

每个递归都会创建一个新的堆栈帧，默认情况下堆栈空间是有限的。您可以增加堆栈大小（不知道如何在Windows上执行此操作，在UNIX上使用ulimit命令），但这只会推迟崩溃。

真正的解决方案是摆脱递归。例如，请参见this question和this question。

- DarkDust

---

尾递归函数是独特的，因为理论上可以将它们的递归从调用指令优化为jmp指令。这将把函数的堆栈需求从O(n)改变为O(1)。实际上并不那么简单，因为它依赖于编译器进行区分和利用优化。 - Swiss

这并没有回答问题：尾递归应该省略调用并防止堆栈溢出，但优化未被应用，而且OP想知道为什么。 - Jon Purdy

抱歉，我错过了一个优化，因为这在问题中没有提到。不过，仍然有点危险依赖于特定的编译器优化，不是吗？ - DarkDust

@DarkDust 我开始对尾递归有同样的感觉了。理论上很好，但在实际应用中却可能出现严重问题而并无明显警告。 - Swiss

@Swiss：这是一个C++问题（或者说是一种特定于语言的问题）。有些语言保证了尾递归的执行。对于那些正在尝试使用自己的编译器进行实验的人来说，最简单的方法是添加一个显式的“tailcall %1”指令。 - MSalters

@Dark：这取决于情况。原则上，尾递归非常出名，是一个相对常见的情况，并且已经被证明所有现代编译器都支持它。因此，许多人争论（我也包括在内）认为您应该能够依赖此优化。确实令人困惑的是，g++在这里没有执行此操作，可以说是一种优化错误。 - Konrad Rudolph