How to prevent recursive function call (tail-recursion) from piling up in stack?

Question

When a function calls itself in the last line or with return command, it seems to be unnecessary to keep caller in stack.

I tested this theory with "gcc" and found out that caller function remains in stack:

#include <iostream>

void a(int i)
{
    std::cout << i << std::endl;
    if (i > 0)
        a(i - 1);
    // Also tested return a(i - 1);
}

int main()
{
    a(10);
}

call stack:

...
a(int i) (/mnt/temp/hackerrank/src/main.cpp:30)
a(int i) (/mnt/temp/hackerrank/src/main.cpp:30)
a(int i) (/mnt/temp/hackerrank/src/main.cpp:30)
main() (/mnt/temp/hackerrank/src/main.cpp:35)

Why optimization doesn't force parent to be poped?

According to comments: this topic is famous for "Tail recursion".

The way you solve this issue is to write the function using iterative methods, and not recursive. — PaulMcKenzie, May 13 '19 at 03:44
Of course the "previous" call has to be on the stack, it's not finished yet. It might be possible to *reuse* the stack-frame if you make your function properly tail-recursive (as in `if (i <= 0) return; a(i - 1);`). Although for such a simple function the compiler might as well optimize it all away. — Some programmer dude, May 13 '19 at 03:57
Related: [What is tail recursion?](https://stackoverflow.com/questions/33923/): "*Compilers and interpreters **that implement tail call optimization or tail call elimination** can optimize recursive code to prevent stack overflows.*" — Remy Lebeau, May 13 '19 at 04:02
@PaulMcKenzie "iterative methods", exactly!. I wish I could mark this as answer. — Null, May 13 '19 at 04:03
See [trampoline](https://en.wikipedia.org/wiki/Trampoline_(computing)). — Mulan, May 13 '19 at 05:22

Cruz Jean · Accepted Answer · 2019-05-13T04:06:43.643

I've tossed this into godbolt

On gcc (8.3) and clang (8.0.0) with -O3 optimizations, that function compiles into a no-op function. Impressively, this is even true for MSVC v19.20 with /O2 optimizations.

GCC 8.3 / Clang 8.0.0:

a(int):
        ret

MSVC v19.20 (x64):

i$ = 8
void a(int) PROC                               ; a, COMDAT
        ret     0
void a(int) ENDP                               ; a

I've also taken the liberty of making the example non-trivial. The code I'm using from here on is:

#include <iostream>

void a(int i)
{
    std::cout << "hello\n";
    if (i > 0)
        a(i - 1);
}

The compiler output for this with gcc trunc with -O3 optimizations enabled is the following:

.LC0:
        .string "hello\n"
a(int):
        push    rbx
        mov     ebx, edi
        jmp     .L3
.L6:
        sub     ebx, 1
.L3:
        mov     edx, 6
        mov     esi, OFFSET FLAT:.LC0
        mov     edi, OFFSET FLAT:_ZSt4cout
        call    std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
        test    ebx, ebx
        jg      .L6
        pop     rbx
        ret
_GLOBAL__sub_I_a(int):
        sub     rsp, 8
        mov     edi, OFFSET FLAT:_ZStL8__ioinit
        call    std::ios_base::Init::Init() [complete object constructor]
        mov     edx, OFFSET FLAT:__dso_handle
        mov     esi, OFFSET FLAT:_ZStL8__ioinit
        mov     edi, OFFSET FLAT:_ZNSt8ios_base4InitD1Ev
        add     rsp, 8
        jmp     __cxa_atexit

From careful examination, the only call instruction is to the io method to write the message on each iteration. A test is then performed (the if statement). If i > 0, control jumps up, decrements i and does it all again. The other branch of the if statement (false case) simply returns (after stack cleanup).

Thus, there is no buildup of stack frames even in this non-trivial example. It is performed via the jmp instruction because (as you said) the previous execution information is irrelevant.

Yes, but that is probably for simple functions. I doubt you would get the same results if say, you wrote a recursive merge sort. — PaulMcKenzie, May 13 '19 at 03:45
@PaulMcKenzie Well yeah, but then op should have provided the example that was causing the issue. From question phrasing, it seems like that's the actual code op was using for testing. — Cruz Jean, May 13 '19 at 03:47

How to prevent recursive function call (tail-recursion) from piling up in stack?

1 Answers1