Fibonacci solution

The question is how bad the recursive Fibonacci algorithm.

To calculate fib n, how many times does this method evaluate fib m, where m < n and both m and n >= 0.

The answer, as you might expect, is pretty bad.

Let’s look at the code again:

let rec fib n = 
  if n < 2 then 1 
  else fib (n-1) + fib (n-2)

When would fib n be called recursively? When fib (n+1) or fib (n+2) is called.

How many times would fib n be called? Count of fib n is count of fib (n+1) plus count of fib (n+2). Look familiar?

The count is the Fibonacci sequence in reverse.

Leave a Reply

You must be logged in to post a comment.