11

我在 C++ 中搞乱尾递归函数，并且在使用 g++ 编译器时遇到了一些问题。

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

问题是以下哪项导致了这种情况？

  • 以下是我忽略的一个错误，它阻止了尾递归。
  • 我使用 g++ 的错误。
  • 在 g++ 编译器中检测尾递归函数的缺陷。

我正在g++ -O3 -Wall -fno-stack-protector test.c使用 g++ 4.5.0 通过 MinGW 在 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);
}
4

8 回答 8

4

C 或 C++ 中的尾调用优化非常有限，而且几乎是一个失败的原因。原因是通常没有安全的方法从传递指针或引用任何局部变量的函数进行尾调用（作为所讨论调用的参数，或者实际上是同一函数中的任何其他调用）——当然，这在 C/C++ 领域到处都是，而且几乎不可能没有。

您看到的问题可能与此有关：GCC 可能通过实际传递分配在调用者堆栈上的隐藏变量的地址来编译返回结构，被调用者将其复制到该地址中 - 这使其属于上述情况。

于 2013-03-12T09:12:22.673 回答
2

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

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

好吧，无论如何它都不适用于O2。唯一可行的方法是将result对象返回到作为参数给出的引用中。

但实际上，删除 Tail 调用并改用循环要容易得多。TCO 用于优化在内联或执行激进展开时发现的尾调用，但无论如何处理大值时都不应该尝试使用递归。

于 2010-12-21T08:54:57.477 回答
1

即使在这个简单的函数上，我也无法让 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++ 变体。没有尾递归。

于 2011-01-25T21:56:10.507 回答
0

我会看两件事。

  1. if语句中的返回调用将为堆栈帧中的else提供一个分支目标，用于当前运行需要在调用后解决的函数（这意味着任何 TCO 尝试都无法覆盖正在执行的堆栈框架从而否定 TCO）

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

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

于 2011-01-25T20:33:24.453 回答
0

尝试将您的代码更改为：

// 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);
}
于 2013-03-10T20:40:23.620 回答
0

尾调用优化 (TCO) 的支持在 C/C++ 中受到限制。

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

通常，TCO 可以通过以下方式抑制：

  • 将指向递归函数堆栈上对象的指针传递给外部函数（如果 C++ 也通过引用传递此类对象）；
  • 具有非平凡析构函数的局部对象，即使尾递归有效（析构函数在尾return语句之前调用），例如为什么 g++ 尾调用不优化而 gcc 是？

此处 TCO 因按值返回结构而感到困惑。如果所有递归调用的结果都将写入其他函数中分配的相同内存地址，则可以修复twoSum（类似于答案https://stackoverflow.com/a/30090390/4023446对Tail-recursion not occurred）

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

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

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

于 2015-08-03T13:26:39.603 回答
-2

我听过其他人抱怨，尾递归只用 gcc 而不是 g++ 优化。你可以尝试使用 gcc。

于 2013-03-10T20:09:32.007 回答
-3

由于 的代码twoSum_Helper正在调用自身，因此程序集准确地显示了正在发生的事情也就不足为奇了。这就是递归的全部意义 :-) 所以这与 g++ 没有任何关系。

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

真正的解决方案是摆脱递归。参见例如这个问题和这个问题。

于 2010-12-21T08:49:36.030 回答