Fibonacci inefficiency

The Fibonacci function is often the first code that someone writes to learn a new functional language. Ironically, it's not always the best example of functional programming. Here's the Fibonacci function in F#:

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

The code matches the mathematical definition, which is a strength of functional programming. However, it performs poorly unless the language has a feature called "memoization". F# does not have this feature.

Can you spot the difference between these two statements?

  • Each Fibonacci number is the sum of the prior two Fibonacci numbers.
  • To calculate Fibonacci of n, add Fibonacci of n-1 to Fibonacci of n-2.

They might seem to say the same thing, but in fact they are different. The first is a definition. The second is an algorithm.

Memoization is a memory/time tradeoff wherein the results of a function are stored in the expectation that the same function will be called with the same parameters. It helps us get across the gap between definition and algorithm.

Your homework
Nevertheless, F# does not have built-in memoization. So when you execute this Fibonacci function, it will execute recursively and redundantly. It will call fib for smaller numbers multiple times. Your homework is to find out how many times.

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

Email or post your answers. Code is good, but proof is better.

Leave a Reply

You must be logged in to post a comment.