Recursion fib(5) kernel memory cpu source fib.c 1 #include <stdio.h> 2 3 long fib( long n) { 4 if (n < 2 ) 5 return n; 6 return fib(n- 1 ) + fib(n- 2 ); 7 } 8 9 int main( void ) { 10 printf( "%ld\n" , fib( 5 )); 11 return 0 ; 12 } n = 1 calls of fib(n) each result on its call's shoulder 5 4 3 3 3 2 2 1 2 2 1 1 1 1 1 0 0 1 1 1 0 0 call stack newest on top fib n = 1 :4 fib n = 2 :6 fib n = 3 :6 fib n = 5 :6 main :10 registers x86-64 0 0 0 0 5 5 d 4 a 1 c 0 1 1 4 1 rip 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 rax 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 rdi 0 0 0 0 7 f f d 3 a 2 c 1 d c 0 rsp 0 0 0 0 7 f f d 3 a 2 c 1 d e 0 rbp CF ZF SF OF Four calls to fib are still waiting, each with its own n. The newest one just received 1 in rdi.