1

所以我在玩一些思想实验，我想象当两个函数相互递归时会发生什么。如果这两个函数都可能陷入无限循环，其中之一就是这样。

为此，我想到了这个简单的例子：

#include <iostream>
#include <cstdlib>

int foo(int x);
int bar(int x);


int foo(int x)
{
    return bar(x + 1);
}

int bar(int x)
{
    return foo(x - 1);
}

int main(int argc, char **argv)
{
    if (argc > 1)
        std::cout << "The value is: " << foo(atoi(argv[1])) << std::endl;

    return 0;
}

有趣的是，如果你用 g++ 编译它，它实际上不会打印出任何东西。使用任何 -O 开关编译它，它就会陷入无限循环。

想法？这可能是编译器错误，还是可以预料到的？我认为在 -O 优化的情况下，它会意识到 foo(x) 和 bar(x) 只返回 x。

我没想到它实际上会“优化”调用并完全忽略将“值是”打印到标准输入。

编辑：我在 Cygwin 下使用 GCC 4.5.0 将它编译为 g++ source.cpp (-O1/2/3)。-OX 版本实际上无限循环而没有堆栈溢出。

4

3 回答 3

2

由于您没有指定您使用的是哪个 C++，所以我将给出 C++0x 答案：

这实际上是 C++0x中未定义的行为。

如果您使用的是 C++03，我无法完全解释该行为，但由于您的堆栈最终会溢出，因此您仍然处于依赖于实现的行为的范围内。期望在这里发生任何理智的事情是愚蠢的。

于 2011-06-19T00:38:14.213 回答
1

从数学的角度来看，f(x) = b(x + 1)和b(x) = f(x - 1)不足以定义f和b。一种可能的解决方案是f(x) = x和b(x) = x - 1，而另一种可能是f(x) = 0和g(x) = 0（还有无限多的方法）。所以在数学上，函数应该返回什么的问题没有答案。从计算的角度来看，情况更糟，因为毕竟，您不是在定义数学函数，而是在指定如何执行计算。foo(x - 1)表示“foo()当我们将 的值x - 1作为参数传递时，执行函数中指定的计算”，对于bar(x + 1). 因此，当每个函数无条件地表示要调用另一个函数时，您已指定希望发生无限递归。正如其他人所提到的，一些语言（或语言版本）将此视为明确定义的情况（期望的结果是程序挂起），而另一些则将其视为未定义的情况（即编译器可以做任何它喜欢的事情）。

于 2011-06-19T00:55:38.407 回答
0

由于您的递归没有停止条件，因此进入无限循环是很自然的。您假设这些函数返回“just x”是错误的。他们注定永远不会回来。

编译器不能仅仅优化递归。

于 2011-06-19T00:31:58.643 回答