Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Fibonacci Number
Bookmark
Recursion
Memoization
Iterative
Matrix Power
Input
n = 2
n = 5
n = 7
n = 10
Custom
n
=
2
F(0)
F(1)
F(2)
0
?
1
?
2
?
calls: 0
F(2) branches into F(1) and F(0)
F(0)
F(1)
F(2)
0
?
1
?
2
?
calls: 0
F(2) branches into F(1) and F(0)
F(0)
F(1)
F(2)
0
?
1
?
2
?
calls: 1
F(2) branches into F(1) and F(0)
n
F(0)
F(1)
F(2)
0
?
1
?
2
?
calls: 1
F(2) = F(1) + F(0)
n
F(0)
F(1)
F(2)
0
?
1
?
2
?
calls: 2
F(2) = F(1) + F(0)
n
F(0)
F(1)
F(2)
0
?
1
1
2
?
calls: 2
Base case: F(1) = 1
n
F(0)
F(1)
F(2)
0
?
1
1
2
?
calls: 3
Base case: F(1) = 1
n
F(0)
F(1)
F(2)
0
0
1
1
2
?
calls: 3
Base case: F(0) = 0
n
F(0)
F(1)
F(2)
0
0
1
1
2
1
calls: 3
F(2) = 1 + 0 = 1
n
F(0)
F(1)
F(2)
0
0
1
1
2
1
calls: 3
3 calls to compute F(2)
algo
master
.
io
Step:
Start: Compute F(2) by plain recursion
0 / 8
Input
n = 2
n = 5
n = 7
n = 10
Custom
n
=
2
0 / 8
algo
master
.
io
Step:
Start: Compute F(2) by plain recursion
