## Get a free weekly practice problem!

Keep that axe sharp.

### You only have free questions left (including this one).

But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.

Write a method fib that takes an integer n and returns the nth Fibonacci number.

Let's say our Fibonacci series is 0-indexed and starts with 0. So:

fib(0) # => 0 fib(1) # => 1 fib(2) # => 1 fib(3) # => 2 fib(4) # => 3 ...

Our solution runs in n time.

There's a clever, more mathy solution that runs in time, but we'll leave that one as a bonus.

If you wrote a recursive method, think carefully about what it does. It might do repeat work, like computing fib(2) multiple times!

We can do this in space. If you wrote a recursive method, there might be a hidden space cost in the call stack!

The nth Fibonacci number is defined in terms of the two previous Fibonacci numbers, so this seems to lend itself to recursion.

fib(n) = fib(n - 1) + fib(n - 2)

Can you write up a recursive solution?

As with any recursive method, we just need a base case and a recursive case:

1. Base case: n is 0 or 1. Return n.
2. Recursive case: Return fib(n - 1) + fib(n - 2).
def fib(n) if n == 0 || n == 1 n else fib(n - 1) + fib(n - 2) end end

Okay, this'll work! What's our time complexity?

It's not super obvious. We might guess n, but that's not quite right. Can you see why?

Each call to fib makes two more calls. Let's look at a specific example. Let's say n=5. If we call fib(5), how many calls do we make in total?

Try drawing it out as a tree where each call has two child calls, unless it's a base case.

Here's what the tree looks like: We can notice this is a binary tree whose height is n, which means the total number of nodes is .

So our total runtime is . That's an "exponential time cost," since the n is in an exponent. Exponential costs are terrible. This is way worse than or even .

Our recurrence tree above essentially gets twice as big each time we add 1 to n. So as n gets really big, our runtime quickly spirals out of control.

The craziness of our time cost comes from the fact that we're doing so much repeat work. How can we avoid doing this repeat work?

We can memoize!

Let's wrap fib in a class with an instance variable where we store the answer for any n that we compute:

class Fibber def initialize @memo = {} end def fib(n) # edge case: negative index if n < 0 raise ArgumentError, "Index was negative. No such thing as a negative index in a series." # base case: 0 or 1 elsif n == 0 || n == 1 n # see if we've already calculated this elsif @memo.include?(n) @memo[n] else result = fib(n - 1) + fib(n - 2) # memoize @memo[n] = result result end end end

What's our time cost now?

Our recurrence tree will look like this: The computer will build up a call stack with fib(5), fib(4), fib(3), fib(2), fib(1). Then we'll start returning, and on the way back up our tree we'll be able to compute each node's 2nd call to fib in constant time by just looking in the memo. n time in total.

What about space? @memo takes up n space. Plus we're still building up a call stack that'll occupy n space. Can we avoid one or both of these space expenses?

Look again at that tree. Notice that to calculate fib(5) we worked "down" to fib(4), fib(3), fib(2), etc.

What if instead we started with fib(0) and fib(1) and worked "up" to n?

We use a bottom-up approach, starting with the 0th Fibonacci number and iteratively computing subsequent numbers until we get to n.

def fib(n) # edge cases: if n < 0 raise ArgumentError, "Index was negative. No such thing as a negative index in a series." elsif n == 0 || n == 1 n else # we'll be building the fibonacci series from the bottom up # so we'll need to track the previous 2 numbers at each step prev_prev = 0 # 0th fibonacci prev = 1 # 1st fibonacci (n - 1).times do # Iteration 1: prev = 2nd fibonacci # Iteration 2: prev = 3rd fibonacci # Iteration 3: prev = 4th fibonacci # To get nth fibonacci ... do n - 1 iterations. prev_prev, prev = prev, prev + prev_prev end prev end end

time and space.

• If you're good with matrix multiplication you can bring the time cost down even further, to . Can you figure out how?

This one's a good illustration of the tradeoff we sometimes have between code cleanliness and efficiency.

We could use a cute, recursive method to solve the problem. But that would cost time as opposed to n time in our final bottom-up solution. Massive difference!

In general, whenever you have a recursive solution to a problem, think about what's actually happening on the call stack. An iterative solution might be more efficient.

Reset editor

Powered by qualified.io

. . .