Recursion is a type of iteration that implicitly preserves local state before moving to the next iteration. It is easy enough to reason this through by thinking of just regular functions calling each other, one after the other:
void iteration_2 (int x) {
/* ... */
}
void iteration_1 (int x) {
if (x > 0) return;
iteration_2(x + 1);
}
void iteration_0 (int x) {
if (x > 0) return;
iteration_1(x + 1);
}
Each iteration_#()
is basically identical to each other, but each one has it's own x
, and each one remembers which function had called it, so it can properly return back to the caller when the function it calls is done. This notion doesn't change when the program is converted into a recursive version:
void iteration (int x) {
if (x > 0) return;
iteration(x + 1);
}
The iteration becomes infinite if the stopping condition (the if
check to return
from the function) is removed. There is no returning from the recursion. So the information that is remembered for each successive function call (the local x
and the address of the caller) keeps piling on until the OS runs out of memory to store that information.
It is possible to implement an infinitely recursive function that does not overflow the "stack". At sufficient optimization levels, many compilers can apply an optimization to remove the memory needed to remember anything for a tail recursive call. For instance, consider the program:
int iteration () {
return iteration();
}
When compiled with gcc -O0
, it becomes:
iteration:
.LFB2:
pushq %rbp
.LCFI0:
movq %rsp, %rbp
.LCFI1:
movl $0, %eax
call iteration
leave
ret
But, when compiled with gcc -O2
, the recursive call is removed:
iteration:
.LFB2:
.p2align 4,,7
.L3:
jmp .L3
The result of this infinite recursion is a simple infinite loop, and there will be no overrun of the "stack". So, infinite recursion is allowed since infinite loops are allowed.
Your program, however, is not a candidate for tail call optimization, since the recursive call is not the last thing your function does. Your function still has a return
statement that follows the recursive call. Since there is still code that needs to execute after the recursive call returns, the optimizer cannot remove the overhead of the recursive call. It must allow the call to return normally, so that the code after it may execute. So, your program will always pay the penalty of storing the return address of the calling code.
The standard does not speak to "infinite recursion" in any specific terms. I have collected together what I believe relevant to your question.
- Calling a function recursively is permitted (C.11 §6.5.2.2 ¶11)
Recursive function calls shall be permitted, both directly and indirectly through any chain of other functions.
- Recursive entry into a statement creates new instances of local variables (C.11 §6.2.4 ¶5,6,7)
An object whose identifier is declared with no linkage and without the storage-class
specifier static has automatic storage duration, as do some compound literals. ...
For such an object that does not have a variable length array type, its lifetime extends
from entry into the block with which it is associated until execution of that block ends in
any way. (Entering an enclosed block or calling a function suspends, but does not end,
execution of the current block.) If the block is entered recursively, a new instance of the
object is created each time. ...
For such an object that does have a variable length array type, its lifetime extends from
the declaration of the object until execution of the program leaves the scope of the
declaration. If the scope is entered recursively, a new instance of the object is created
each time.
The standard talks about memory allocation failure in numerous places, but never in the context of an object with automatic storage duration. Anything not explicitly defined in the standard is undefined, so a program that fails to allocate an object with automatic storage duration has undefined behavior. This would apply equally between a program that just had a very long function call chain or too many recursive calls.