Counting recursive calls
How many times is fib called in total (including the first call) when you run fib(5)?
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)Show hint
Let C(n) be the number of calls for fib(n). Then C(0) = C(1) = 1, and C(n) = 1 + C(n − 1) + C(n − 2).
Show solution
15 calls. C(2) = 3, C(3) = 5, C(4) = 9, C(5) = 1 + 9 + 5 = 15.
The count grows exponentially, roughly 1.6 times for each step up in n, because the same values are recomputed over and over. fib(30) makes over 2.6 million calls. Caching results (see the memoize problem) brings it down to 31.
Want a problem like this every day? See today's problem and keep a streak going.