The naive recursive Fibonacci is the textbook example of a function whose time and space are very different:
function fib(n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}
Write fibCosts(n) that returns { calls, depth } for one top-level call fib(n):
calls: the total number of times fib is called, counting the top-level call and every call that hits the base casedepth: the largest number of fib frames on the call stack at the same moment, counting the top-level frame
Do not run fib. The tests go up to n = 60, where it would make over five trillion calls. Write a recurrence for each number and compute it in O(n).