Fibonacci: Two Implementations Compared
Problem statement
Compute the $n$-th Fibonacci number, defined by $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$.
Implement the function:
def fib(n):
...
It takes a single non-negative integer n and returns the $n$-th Fibonacci number as an int.
For discussion, consider two implementations -- for example naive recursion versus an iterative (or memoized) version -- and compare their time and space complexity.
Example
fib(6) -> 8 because the sequence is $0, 1, 1, 2, 3, 5, 8$, so index 6 (0-based) is 8. Likewise fib(10) -> 55.
Show hint
If you draw the call tree of the textbook recursive definition, how many times does the same subproblem appear?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.
Related free problems
- Newton's Method vs Gradient DescentLinear Algebra & OptimizationMedium