Can't understand why this simple recursion begins to work and then crashes

Question

I was doing some trick questions about C++ and I run on similar code to this then I modified it to see what will happen.

I don't understand why at first place this recursion is working (it's printing values from 2 to 4764) and then suddenly it throws exception.

I don't understand also why I can say return in void function and actually return something other than "return;"

Can anyone explain this two problems?

#include<iostream>
using namespace std;

void function(int& a){
    a++;
    cout << a << endl;
    return function(a);
}

void main() {

    int b = 2;
    function(b);

    system("pause>0");
}

C++ doesn't use tail recursion, so every call is a brand new stack frame pushed on the stack, eventually that will crash after the stack grows to some point where implementation dependent bad thing happens. — Grady Player, May 30 '19 at 22:21
Every time a function is called recursively it allocates more space in the Call Stack, until eventually you run out of it and the application crashes in what is known as Stack Overflow. — Havenard, May 30 '19 at 22:21
You didn't add a stop recursion condition. That is why stack will overflow. — Cristián Ormazábal, May 30 '19 at 22:24
Regarding second question: https://en.cppreference.com/w/cpp/language/return `In a function returning void, the return statement with expression can be used, if the expression type is void.` — , May 30 '19 at 22:27
"*I don't understand also why I can say return in void function and actually return something other than "return;"*" See this question: [Can I return in void function?](https://stackoverflow.com/questions/2249108/can-i-return-in-void-function) — Yksisarvinen, May 30 '19 at 22:27
If you compile it with `-O2` (or higher) on any modern compiler, it will probably do tail-call optimization, and turn your recursive call into a loop. It should then run forever without stack overflow. — HAL9000, May 30 '19 at 22:37
@GradyPlayer it's up to the compiler whether or not to do tail recursion optimization. The standard doesn't prohibit it. — M.M, May 31 '19 at 01:22
Even without stack overflow, the program causes undefined behaviour due to signed integer overflow. — M.M, May 31 '19 at 01:23

score 0 · Accepted Answer · answered May 30 '19 at 22:57

The comments have correctly identified that your infinite recursion is causing a stack overflow - each new call to the same function is taking up more RAM, until you use up the amount allocated for the program (the default C++ stack size varies greatly by environment, and anywhere from 10s kB on old systems to 10+ MB on the upper end).The comments have correctly identified that your infinite recursion is causing a stack overflow - the space amount allocated for this purpose (the default C++ stack size varies greatly by environment, and anywhere from 10s kB on old systems to 10+ MB on the upper end). While the function itself is doing very little in terms of memory, the stack frames (which keep track of which function called which other ongoing function with what parameters) can take up quite a lot.

While useful for certain data structures, recursive programs should not need to go several thousand layers deep and usually add a stop condition (in this case, even checking whether a > some_limit) to identify the point where they have gone to deep and need to stop adding more things to the stack (plain return;).

In this case, the exact same output can be achieved with a simple for loop, so I guess these trick questions are purely experimental.

score 0 · Answer 2 · answered May 30 '19 at 23:40

On x86-64 platforms, like your laptop or desktop, functions get called one of two ways:

with a call assembly instruction
with a jmp assembly instruction

What's the difference? A call assembly instruction has additional instructions after it: when the function is called, the code will return to the place it was called from. In order to keep track of where it is, the function uses memory on the stack. If a recursive function calls itself using call, then as it recurses it'll use up more and more of the stack, eventually resulting in a stack overflow.

On the other hand, a jmp instruction just tells the CPU to jump to the section of code where the other function is stored. If a function is calling itself, then the CPU will just jmp back up to the top of the function and start it over with the updated parameters. This is called a tail-call optimization, and it prevents stack overflow entirely in a lot of common cases because the stack doesn't grow.

If you compile your code at a higher optimization level (say, -O2 on GCC), then the compiler will use tail-call optimization and your code won't have a stack overflow.

Can't understand why this simple recursion begins to work and then crashes

2 Answers2