Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is this infinite recursion UB?

In C++11, as an infinite loop with no side-effects, the following program is UB:

int main() {    while (true) {} } 

Is the following also UB?

void foo() {    foo(); }  int main() {    foo(); } 

Citations from the standard for both programs would be ideal.

like image 437
Lightness Races in Orbit Avatar asked May 05 '11 23:05

Lightness Races in Orbit


People also ask

What is difference between infinite loop and infinite recursion?

Iteration and recursion can occur infinitely: An infinite loop occurs with iteration if the loop-continuation test never becomes false; infinite recursion occurs if the recursion step does not reduce the problem in a manner that converges on the base case.

Can recursion causes infinite loop?

Infinite recursion is a special case of an infinite loop that is caused by recursion.

Does infinite recursion cause stack overflow?

The most-common cause of stack overflow is excessively deep or infinite recursion, in which a function calls itself so many times that the space needed to store the variables and information associated with each call is more than can fit on the stack.

Can a tail recursive function cause an infinite loop?

A tail recursion can be considered a iterative loop. This is the only type of infinite recursion that doesn't swiftly end with a stack overflow error. const test = (n) => test(n + 1); test(0); It will hang forever and never cause a stack overflow.


2 Answers

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.

like image 191
Johannes Schaub - litb Avatar answered Sep 23 '22 12:09

Johannes Schaub - litb


I don't think the standard says the behavior is undefined, it just says a loop that has no side effects may be assumed to eventually terminate.

So:

int main() {    while (true) {} } 

May terminate or loop forever.

void foo() {    foo(); }  int main() {    foo(); } 

May also terminate, loop forever, or possibly run out of stack space (if the compiler does not implement tail recursion).

I don't think either have any right to do anything other than listed, so I don't think the behavior is completely "undefined".

like image 38
Clinton Avatar answered Sep 22 '22 12:09

Clinton