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.