title: Stack frame appearance during recursion. C vs assembly
body: <p>I'm just learning about functions in assembly and the stack frame and so on, so I've been looking at the stack frame in gdb as I run a recursive algorithm to see what happens.</p>
  
  <p>If I run some recursive code in C, the stack looks like I expect it to - an object on the stack for each call of the function.  At the lowest level of recursion in a recursive factorial function, the stack frame looks like this:  (This is a backtrace in gdb with a breakpoint at the first line of the function.)</p>
  
  <pre><code>(gdb) bt
  #0  factorial (n=1) at recursion.c:20
  #1  0x00005555555551c7 in factorial (n=2) at recursion.c:21
  #2  0x00005555555551c7 in factorial (n=3) at recursion.c:21
  #3  0x00005555555551c7 in factorial (n=4) at recursion.c:21
  #4  0x00005555555551c7 in factorial (n=5) at recursion.c:21
  #5  0x00005555555551c7 in factorial (n=6) at recursion.c:21
  #6  0x00005555555551c7 in factorial (n=7) at recursion.c:21
  #7  0x00005555555551c7 in factorial (n=8) at recursion.c:21
  #8  0x00005555555551c7 in factorial (n=9) at recursion.c:21
  #9  0x00005555555551c7 in factorial (n=10) at recursion.c:21
  #10 0x000055555555517f in main (argc=2, args=0x7fffffffe768) at recursion.c:13
  </code></pre>
  
  <p>My C code is like this:</p>
  
  <pre><code>int factorial (int n)
  {   
      if (n &lt;= 1) return 1;
      return n * factorial(n-1);
  }
  </code></pre>
  
  <p>Now I do the same in assembly (I've copied this code from Rey Seyfarth's book "Introduction to 64 bit assembly programming" so I am assuming it's correct) and, regardless of the depth of recursion, the stack frame looks like this: (Line 50 is the line <code>call fact</code>).</p>
  
  <pre><code>(gdb) bt
  #0  fact () at fact.asm:40
  #1  0x00000000004011a8 in greater () at fact.asm:50
  #2  0x0000000000000000 in ?? ()
  </code></pre>
  
  <p>The code for the factorial function is like this - the breakpoint in this case is at the <code>sub rsp, 16</code> line:</p>
  
  <pre><code>fact:                                   ; recursive function
  n       equ     8
  
          push    rbp
          mov     rbp, rsp
          sub     rsp, 16                 ; make room for n
          cmp     rdi, 1                  ; end recursion if n=1
          jg      greater
          mov     eax, 1
          leave
          ret
  
  greater:
          mov     [rsp+n], rdi            ; save n
          dec     rdi                     ; call fact with n-1
          call    fact
          mov     rdi, [rsp+n]            ; restore original n
          imul    rax, rdi
          leave
          ret
  </code></pre>
  
  <p>In fact, the output from backtrace is really confusing me in this case.  If I place the breakpoint on the line before calling the fact function (<code>dec rdi</code>) then the result is usually this:</p>
  
  <pre><code>(gdb) bt
  #0  greater () at fact.asm:49
  #1  0x0000000000000000 in ?? ()
  </code></pre>
  
  <p>But on the fifth call of fact it's this:</p>
  
  <pre><code>(gdb) bt
  #0  greater () at fact.asm:49
  #1  0x00007ffff7f94be0 in ?? () from /usr/lib/libc.so.6
  #2  0x0000000000000006 in ?? ()
  #3  0x00007fffffffe5f0 in ?? ()
  #4  0x00000000004011a8 in greater () at fact.asm:50
  #5  0x0000000000000000 in ?? ()
  </code></pre>
  
  <p>and then on the seventh call, this:</p>
  
  <pre><code>(gdb) bt
  #0  greater () at fact.asm:49
  #1  0x0000003000000008 in ?? ()
  #2  0x0000000000000004 in ?? ()
  #3  0x00007fffffffe5b0 in ?? ()
  #4  0x00000000004011a8 in greater () at fact.asm:50
  #5  0x0000000000000000 in ?? ()
  </code></pre>
  
  <p>My questions:</p>
  
  <ol>
  <li><p>Why is the stack not behaving similarly to in C?</p></li>
  <li><p>Why am I getting that last, seemingly garbage, output occasionally?</p></li>
  </ol>
  
  <p>Thanks!</p>