Can anyone explain this output to me?

Question

So I was playing around with some thought experiments where I imagined what would happen when two functions became mutually recursive. One such one was what if both functions could potentially fall into an infinite loop.

To that end, I thought up of this simple example:

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

Interestingly, this will actually print out absolutely nothing if you compile it with g++. Compile it with any -O switch and it falls into an infinite loop.

Thoughts? Is this potentially a compiler bug, or is this to be expected? I'd think in the case of -O optimizations, it would realize that foo(x) and bar(x) return just x.

I didn't expect it to actually "optimize away" the call and completely ignore printing out "The value is" to standard input.

Edit: I compiled this as just g++ source.cpp (-O1/2/3), under Cygwin using GCC 4.5.0. The -OX versions actually loop infinitely without the stack overflowing.

@delnan: Yet, that's exactly what he's saying happens without optimisations. — Lightness Races in Orbit, Jun 19 '11 at 00:38
It segfaults because the computer doesn't have an infinite stack. Without optimization this recursion will overflow the stack. The optimizer can't make heads or tails of this recursion _except_ that it can see how to change those function calls into jumps. There is no stack overflow in this case because the optimizer has changed these recursive functions into recursive coroutines. Either way, it is undefined behavior. — David Hammen, Jun 19 '11 at 04:43
"The -OX versions actually loop infinitely without the stack overflowing." # You tested it forever? — Lightness Races in Orbit, Jun 19 '11 at 10:34
@Tomalak: I looked at the assembly (i686-apple-darwin10-g++-4.2.1). The compiler changes those function calls into jumps with -O2 or higher. How can the stack overflow if there are no operations on the stack? — David Hammen, Jun 19 '11 at 11:41

score 2 · Accepted Answer · edited May 23 '17 at 12:20

2

Since you didn't specify which C++ you're on about I'll give the C++0x answer:

This is in fact undefined behaviour in C++0x.

I can't fully explain the behaviour if you're using C++03, but since your stack will eventually overflow, you're still really within the realm of implementation-dependent behaviour. Expecting anything sane to happen here is a fool's errand.

edited May 23 '17 at 12:20

Community

1
1

answered Jun 19 '11 at 00:38

Lightness Races in Orbit

378,754
76
643
1,055

score 1 · Answer 2 · answered Jun 19 '11 at 00:55

From a mathematical point of view, f(x) = b(x + 1) and b(x) = f(x - 1) are not sufficient to define f and b. One possible solution is f(x) = x and b(x) = x - 1, while another one is f(x) = 0 and g(x) = 0 (and there are infinitely many more ways). So mathematically, the question of what the function should return doesn't have an answer. From a computational point of view, the situation is even worse, because after all, you are not defining mathematical functions, you are specifying how a computation is to be performed. foo(x - 1) means "perform the computations specified in the function foo() when we pass the value of x - 1 as a parameter", and similarly for bar(x + 1). So when each function says, unconditionally, that the other function is to be called, you have specified that you wish for an infinite recursion to take place. As others have mentioned, some languages (or language versions) treat this as a well-defined situation (where the desired outcome is that the program hangs), while others treat it as an undefined situation (i.e., the compiler may do anything it likes).

score 0 · Answer 3 · answered Jun 19 '11 at 00:31

0

As your recursion has no stopping condition it is only natural that you get into an infinite loop. Your assumption, that these functions return "just x" is false. They are bound to never return.

The compiler cannot just optimize away recursion.

answered Jun 19 '11 at 00:31

ypnos

50,202
14
95
141

Yeah, I figured it wouldn't optimize away the recursion. What confuses me is that it prints nothing without -O switches, and loops when I use the -O switches. – Mike Bailey Jun 19 '11 at 03:47
The compiler has to obey the intent of the code if the code does not invoke undefined behavior. That does not mean the compiler has to implement the code as expressed by the programmer. For example, compilers often transform tail recursion into a loop. In this case, the compiler transformed the mutually-recursive functions into a pair of recursive co-routines. No calls, no stack. So instead of stack overflow you get an infinite loop. – David Hammen Jun 19 '11 at 05:12
@David: This still doesn't really address his first concern, that without optimisation the program terminates without output. – Lightness Races in Orbit Jun 19 '11 at 10:36
1

I don't see that unoptimized behavior. I get a segfault, which results in output (undesired output) on every machine I have used. Perhaps that is what the OP meant by "prints nothing". – David Hammen Jun 19 '11 at 11:42

Can anyone explain this output to me?

3 Answers3