Is This Infinite Recursion Ub

Is this infinite recursion UB?

It's UB because it's not worded in terms of loops, but in terms of (1.10p24):

The implementation may assume that any thread will eventually do one of the following:

• terminate,
• make a call to a library I/O function,
• access or modify a volatile object, or
• perform a synchronization operation or an atomic operation.

This applies to both, as opposed to the more older formulation in one of the C++0x drafts. (See this question for discussions).

Note that disregarding of that, the behavior can easily be undefined if the recursion exceeds the implementation limit of the number of nested recursive function calls. That has always been the case.

Infinite loop vs infinite recursion. Are both undefined?

No there is no difference. [basic.progress]p1:

The implementation may assume that any thread will eventually do one of the following:

• terminate,

• make a call to a library I/O function,

• perform an access through a volatile glvalue, or

• perform a synchronization operation or an atomic operation.

It doesn't matter how you have your infinite loop; if it doesn't do any of the points above, you get UB. Including the following:

int bar(int cond) {
    if (cond == 42) bar(cond);
    return 42;
}
bar(some_user_input);

The compiler is allowed to assume that some_user_input will never be 42.

Infinite recursion in C

Whenever you call a function, the arguments are pushed on the stack, which means that data on the stack segment is "allocated". When the function is called, the return adress is also pushed on the stack, by the CPU, so it knows where to return to.

In your example case this means, that no arguments are used, so the only thing that is pushed is the return adress, which is rather small (4 bytes on x86-32 architexture), and additionally the stackframe is adjusted which takes another four bytes on this architecture.

From this is follows that, once the stack segment is exhausted, the function can not be called aynmore and an exception is raised to the OS. Now there can happen two things. Either the OS forwards the exception back to your application which you will see as stack overflow. Or the OS can try to allocate additional space for the stack segemnt, up to a defined limit, after which the application will see the stack overflow.

So this code (I renamed it to infinite_recursion() as main() can not be called) ...

int inifinite_recursion(void)
{
    inifinite_recursion();
    return 0;
}

... looks like this:

_inifinite_recursion:
    push    ebp                    ; 4 bytes on the stack
    mov ebp, esp

    call    _inifinite_recursion   ; another 4 bytes on the stack
    mov eax, 0                 ; this will never be executed.

    pop ebp
    ret 

UPDATE

Regarding the standard C99 for defining recursion, the best I found so far is in Section 6.5.2.2 Paragraph 11:

Recursive function calls shall be permitted, both directly and indirectly through any chain of other functions.

Of course this doesn't answer whether it is defined what happens when the stack overflows. However at least it allows main to be called recursively, while this is explicitly forbidden in C++ (Section 3.6.1 Paragraph 3 and Section 5.2.2 Paragraph 9).

Why does (infinite) recursion give different results with and w/o -O3 in clang (and gcc/g++)?

Is that a (known) bug in the optimization or am I missing something?

It's not a bug in optimisation. It's a bug in the program that is being compiled. The behaviour of the program is undefined in C++.

it returns 0: 1, which is wrong

There is no "wrong" behaviour when the behaviour of the program is undefined.

but the compilation hangs with -O3

This is probably a compiler bug.

how can the compiler just decide to return something, whereas, if you follow the program logic, it should not.

When the behaviour of the program is undefined, the compiler can decide to do anything or to do nothing. There's nothing in particular that it should do or should not do. An undefined program has no logic to it.

why the behaviour is undefined

The C++ standard says:

[intro.progress]

The implementation may assume that any thread will eventually do one of the following:

• terminate,
• make a call to a library I/O function,
• perform an access through a volatile glvalue, or
• perform a synchronization operation or an atomic operation.

In case the argument is 0, the thread would never do any of those things, and as such the [language] implementation is allowed to assume that the function is never called with the argument of 0. When you call the function with such argument, you contradict this assumption and behaviour is undefined.

Prevent infinite recursion in c++

This can be solved by eliminating recursion ad it involves moving the input routine inside of a function that's more self-contained:

int getResponse(string i) {
  for(;;) {
    string i;
    cout << "Are you sad?";
    cin >> i;

    if (i == "yes" or i == "Yes") {
        cout << "\nHello, sad, I'm dad\n";
        return(0);
    }
    else if (i == "no" or i == "No") {
        cout << "Good for you pal\n";
        return(0);
    }
    else {
        cout << "Answer properly you overgrown flatworm\n";
    }
  }
}

why infinite loop terminates? or go infinite

Without the if (arr[i]==arr[j]), you simply have an infinite loop, which is perfectly valid in this case. j will just keep getting incremented (eventually this will overflow, which in undefined behaviour, see [basic.fundamental]/2), and the condition will never be met, since i does not change.

However, with the if (arr[i]==arr[j]) in the code, j is being incremented, and you will go outside the bounds of the array (as you know). In C++, this is Undefined Behaviour, meaning anything can happen. In your case, it seems to be causing the program to crash (which is actually a good thing, since it indicates an error).

Can anyone explain this output to me?

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.

Does this program with bounded recursion have undefined behavior?

With thanks to 101010's standard link, I think the relevant phrase is

4.1 Implementation compliance [intro.compliance]

(2.1) - If a program contains no violations of the rules in this document, a conforming implementation shall, within its resource limits, accept and correctly execute that program.

and

Annex B (informative)

Implementation quantities [implimits]

mostly addresses compiler limitations (max symbol length, characters per line etc.), but the language sounds related:

1. Because computers are finite, C++ implementations are inevitably limited in the size of the programs they can successfully process. Every implementation shall document those limitations where known. This documentation may cite fixed limits where they exist, say how to compute variable limits as a function of available resources, or say that fixed limits do not exist or are unknown.

2. The limits may constrain quantities that include those described below or others ...

So, the standard doesn't say which quantities may be limited by an implementation, or give anything other than guidelines for the minimum values of those limits it does describe.

If your compiler doesn't document its stack depth limit, I guess it may be non-conforming according to the bold sentence, but a statement that "stack depth is limited by these runtime properties" might be sufficient..

Does this program that anybody can compile and run in its entirety invoke undefined behavior according to the C++ standard?

No. But per 4.1/2.1 implementations are permitted to fail to compile, or fail correctly to execute, a correct program.

---

Related Topics