0

I've written the following factorial function which can use tail call recursion. I've added in putchar('x') just so I can see it is running:

#include <stdio.h>
int factorial(int n) {
    if (n > 0) {
        putchar('x');
        return n + factorial(n-1);
    } else 
        return 1;
}

And the compiler optimizes this to not use recursion (i.e., calling the function) but tail-call recursion (like a while loop). I was wondering if someone could explain the basics of how the tail-call assembly works in the above. The 'recursive part' of the assembly is the following:

.L3:
        movq    stdout(%rip), %rsi     // what is this line doing? I don't see `stdout` anywhere
        movl    $120, %edi             // why do we need to re-add 'x' every loop since static?
        addl    %ebx, %ebp
        call    putc
        subl    $1, %ebx
        jne     .L3

Compiler Explorer link is here.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
carl.hiass
  • 1,526
  • 1
  • 6
  • 26
  • 1
    `putchar` is apparently implemented as a wrapper or macro for `putc(x, stdout)`, like the man page says it can be. Also, functions destroy their arg registers so of course it needs to set up EDI and RSI before every call. – Peter Cordes Jan 31 '21 at 00:28
  • 1
    Does it still do this if you switch off the optimization? – cup Jan 31 '21 at 00:30
  • @cup no, removing `-O3` gives me: `call factorial`. You can check out in the compiler link above. – carl.hiass Jan 31 '21 at 00:31
  • 2
    Actually the function is *not* tail recursive. `-O3` just rewrites it aggressively until it is. – Konrad Rudolph Jan 31 '21 at 00:34
  • Try either -O0 or -Og (for gcc). or -Od (for vC++) – cup Jan 31 '21 at 00:37
  • It's also not a factorial, it's a sum of 1..n. (If you do that with a normal loop in the source, clang recognizes the `n*(n+1)/2` closed-form. You used GCC, and for even for clang printing every iteration might defeat that optimization.) – Peter Cordes Jan 31 '21 at 00:38
  • Anyway, what do you want explained? There is no actual tail-call in the asm (that would be `jmp factorial`), just a normal loop once the compiler is done optimizing the recursion into a loop. – Peter Cordes Jan 31 '21 at 00:42

0 Answers0