Recursion And Stack Overflow

Few days ago, the Twitter account of StackOverflow (the famous site of technical questions and answers) has published the following tweet:

The intention was to recall the name of the site by presenting a situation that every developer has been warned about.

Of course I got the pun but a light bulb has turned on in my mind: tail calls. Some years ago I've read something about it on the blog of Gustavo Duarte: Tail Calls, Optimization, and ES6.

Do It Yourself

It's not that I don't trust Gustavo, but I've tried to do my own test (on x86-64bits with gcc 4.8):

#include <stdio.h>

int main()
{
        fprintf(stderr, "Go!\n");
        return main();
}

Compiled with the optimization enabled:

$ gcc -O2 -o so so.c

Launching the executable so (that stands for stack overflow), it prints a never ending series of "Go!", without crashing. The explanation is exactly the same Gustavo presented in his old post: the compiler optimizes this call with a jump. So basically it transforms a recursion in a loop. This is clear looking at the disassembled code, with the following command:

$ objdump -d so

This is the result (leaving only the interesting part):

  0000000000400480 <main>:
  400480:   48 83 ec 08            sub    $0x8,%rsp
  400484:   0f 1f 40 00            nopl   0x0(%rax)
  400488:   48 8b 0d b1 0b 20 00   mov    0x200bb1(%rip),%rcx   # 601040 <__TMC_END__>;
  40048f:   ba 04 00 00 00         mov    $0x4,%edx
  400494:   be 01 00 00 00         mov    $0x1,%esi
  400499:   bf 14 06 40 00         mov    $0x400614,%edi
  40049e:   e8 cd ff ff ff         callq  400470 <fwrite@plt>
  4004a3:   eb e3                  jmp    400488 <main+0x8>

As you can see, fprintf is mapped with a callq to fwrite, while the recursion is made by the instruction jmp

Conclusions

Basically there are three considerations that can be done:

1. Gustavo was right;
2. compilers are smarter than you think;
3. the same thing I've wrote about goto and do-while loops apply also for recursion.

Cover image taken from Wikimedia Commons (public domain).