Call count of memoized Fibonacci

You compute fib(10)\text{fib}(10) with top-down recursion plus a memo cache, counting every invocation of the fib function - including calls that return immediately from the cache and the base cases fib(0)\text{fib}(0), fib(1)\text{fib}(1). The initial call fib(10) counts as one. How many total calls occur? (Convention: fib(0)=0\text{fib}(0)=0, fib(1)=1\text{fib}(1)=1.)

Show hints (2)+
  1. Each of the recursing values makes exactly two child calls.
  2. Total calls =1+2(n−1)=2n−1= 1 + 2(n-1) = 2n-1.

Answer

Reveal answer →

19

Create a free account to see the full worked solution and track your progress.

Interview format: Market Maker, Options Trading

Related questions