When using recursion, is it possible to remove unneeded function calls from the stack?

[vaderboi]

When a function is called, the call will be pushed on to the stack along with any member variables. In recursion, function calls will continue to stack on top of each other until the base case is reached and the function calls will be released from the stack and therefore released from memory. With a recursive function that traverse back upwards and only goes deeper, a stack overflow is inevitable if the input is high enough.

For example:

    
int addNums( int num, int sum )
{
    if( num == 0 )
    {
        return sum;
    }
    else
    {
        sum += 1;
        return addNums( num - 1, sum );
    }
}

For each function call, you would need the previous function call and all of its member variables in order to push values on to the stack. But would you need any of the function values prior to the previous function call? Would it be possible to release values lower down on the stack in order to free up memory space or would this be impossible in a stack data structure?

[jonnin]

this isnt a 'stack data structure' its the 'operating system's executable code call stack'. Its a stack, as you know one behaves, but its not anything you can tamper with directly on most OS. (There are things you can do if you feel like adventuring off into hackish land, if the OS will let you..).

the way to do this is to not make the unnecessary recursive call OR to have it pop itself before proceeding.

My theory is a bit dated but when I learned this stuff, it was considered proven that anything you can write with recursion can be written with iteration. So "an" answer is that "if its going to blow the stack, rewrite it". Its not always a great answer (at least one example went from 1/2 a page to over 10 pages of code to solve via iteration).

then there is the compiler. Tail recursion (where the last thing you do is recurse) is often turned into a loop by the compiler, which avoids the problem for you. I don't know what else the compiler is smart enough to rewrite here, but sometimes your recursion isn't.

So all that to say, no, you can't do that, and if its a problem, prove it, and if it really is a problem, rewrite it.


edit: this one is optimized to a loop, pretty sure. I changed it to long long and ran it with -1, 0 and got bored at -3923619 it was still going. I didnt look at the assembly, but you can verify there.

[Peter87]

this one is optimized to a loop, pretty sure.

GCC (with optimizations turned on) generates the exact same instructions as for the following function.

int addNums2( int num, int sum )
{
    return sum + num;
}

https://godbolt.org/z/5vySWl

This is of course not something to rely on.

[vaderboi]

@jonnin- Thank you. I should have known that you would have to pop the top elements off the stack before you pop any elements on the bottom. It seems like tail recursion essentially solves the memory issue (at least in terms of saved function calls and their respective member variables) since each recursive loop discards the previous function call and member variables.

[Duthomhas]

All major compilers perform TCO. They are pretty good at it, too.

However, it is not language mandated. You should review your compiler’s specific documentation about TCO, for each compiler you are targeting, as you will need to enable the optimization. For MSVC, use /Ox. For GCC, use -O3.

The real trick is to avoid writing code that prevents TCO from occurring, which you can easily do if you are not carefully aware of how your constructs affect it.