Write a recursive function that returns the n-th Fibonacci number, where
fib(0) = 0, fib(1) = 1, and each later value is the sum of the two before it.
fib(n)
Assume n >= 0. A direct two-way recursion is fine here; in the Dynamic
Programming section you'll make it fast with memoization.
fib(0) // → 0
fib(1) // → 1
fib(6) // → 8 (0, 1, 1, 2, 3, 5, 8)
fib(10) // → 55
Fibonacci is recursive by definition: each number is the sum of the two before it. Unlike the earlier problems here, where a call reduced to exactly one smaller subproblem, Fibonacci branches into two recursive calls per step — which changes both how you reason about it and how expensive it gets.
By definition, fib(0) is 0 and fib(1) is 1 — given directly, not derived from anything smaller. Both can be captured in one check: for any n less than 2, return n itself, since fib(0) = 0 and fib(1) = 1 both equal their own index. You need both covered, since the recursive case is about to branch in two directions, and both need somewhere to bottom out.
For n of 2 or more, trust that fib(n-1) and fib(n-2) each correctly return their own Fibonacci number. The answer for n is just the sum of those two trusted results — a direct translation of the definition into code.
Here's where Fibonacci differs from the earlier problems: each call spawns two further calls, so the calls form a branching tree instead of a straight line. Computing fib(4) calls fib(3) and fib(2). fib(3) calls fib(2) and fib(1). fib(2) (called from fib(3)) calls fib(1) and fib(0). Notice fib(2) gets computed twice — once as a child of fib(4), once as a child of fib(3) — redoing the same fib(1) and fib(0) work both times, since the function has no memory of calls it already made. As the tree bottoms out at the base cases, those values sum back up through each branch until the root produces the answer.
Each non-base call spawns two more, so the number of calls roughly doubles with every increase in n — exponential time, O(2ⁿ), even though the answer only needs n additions if computed the smart way. The waste is entirely from recomputing the same subproblems repeatedly. That's intentional at this stage: the goal is to get comfortable with a recursive function that branches, and see where the repeated work comes from by tracing the tree. Later, in Dynamic Programming, you'll fix exactly this by remembering (memoizing) results you've already computed, turning the same structure into an O(n) algorithm.
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.