Why it takes a long time to compute Fibonacci number?

Question

I started learning Ocaml a few days ago. I tried to make a program of fibonaaci numbers:

  let rec fib a=
      if a=1||a=2 then 1 else fib(a-1)+fib(a-2);;

This code is not optimal as I do not know how to deal with exception cases. But for now, if I try to compute fib 50 or fib 100, then the computer takes a long time to evaluate. I am wondering why, because Ocaml is supposed to be very fast, and adding numbers up is obviously a linear time task. If I paste this code in "Try Ocaml" (http://try.ocamlpro.com/), then the whole website freezes when I execute fib 50.

Sorry if the level of the question is too low.

Answer 1

Because this is the poster example for bad recursion usage. There should be a ban for using this as an example for the elegance of recursion, because it really is totally inelegant w.r.t. the machine.

For every call to fib, you reap another two fib calls:

depth | call tree
------+------------------------------------------------------------------------
1     | fib-----+
      | |        \
2     | fib      fib
      | |   \    |   \
3     | fib  fib fib  fib
      | ....
4     | fib fib  fib  fib fib fib  fib  fib
      | ....
5     | fib fib  fib  fib fib fib  fib  fib 
      | fib fib  fib  fib fib fib  fib  fib
      | ....
6     | fib fib  fib  fib fib fib  fib  fib  
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib  
      | fib fib  fib  fib fib fib  fib  fib
      | ....
7     | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | ....
8     | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib          
      | ....
9     | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib

... and for depth 50, ...

 [562,949,950,000,000] × fib

... all existing in parallel, roughly 560 million packets of each a million fib.

What you have is not an OCaml problem, but rather a computation/algorithm problem. Fibonacci numbers are a good example for a case where "simple" recursion is not desirable. It looks simple and elegant, but denies reality.

So, implement this as a loop instead and your problem will be gone.

Complexity

This is a good question to point out computational complexity (Big O Notation). Your implementation has exponential complexity O(2ⁿ), i.e. the time required to run your algorithm grows exponentially w.r.t. to the input. A summing loop will run in O(n), i.e. the time required to solve the problem grows linearly w.r.t. to the input.

See also Algorithm function for fibonacci series.

Answer 2

phresnel is absolutely right that the usual recursive definition of the Fibonacci function is an exceptionally poor way to actually compute it. It's easy to see there's at least one recursive call for every time you want to add 1 to the result. Since the Fibonacci function is exponential (roughly 1.6 ^ n), you have to make an exponential number of recursive calls.

Here is a reasonably fast recursive Fibonacci function:

let fib n =
    let rec ifib i a b =
        if i = n then b
        else ifib (i + 1) b (a + b)
    in
    ifib 0 0 1

Answer 3

You've written the notorious doubly-recursive Fibonacci function. Because there are two recursive calls in every invocation, the total number of calls grows exponentially with the number of levels of recursion.

The usual way to handle this is to either rewrite the function to calculate in a way that doesn't require recursion (for Fibonacci, you can start with 1 and go up, instead of going down to a-1 and a-2, so that you already have the earlier values in the series when you need them), or to use memoization to cache values so that you never need to calculate the same value more than once. Once fib 23 has been calculated, any subsequent call for it just pulls it from the cache rather than calculating it again.

However, the Fibonacci sequence also has a closed form (search for "closed form" at that link) which is related to Φ, the golden ratio:

let round f =
    int_of_float (f +. 0.5)

let phi = (1. +. (sqrt 5.)) /. 2.

let fibf n =
    (phi ** n) /. (sqrt 5.)

let fib n =
    round (fibf n)

This implementation calculates a value of the Fibonacci sequence directly, with no iteration or recursion. It is, however, limited by floating point precision. It would not be suitable as a replacement for an iterative solution that was intended to continue up into the realm of bignums, for example.

Answer 4

And for completeness, here is a logarithmic version of fibonacci:

(* exponentiation by squaring *)
let rec pow e ( * ) x = function
| 0 -> e
| 1 -> x
| n ->
  let r = pow e ( * ) x (n/2) in
  if n mod 2 = 0 then r * r else r * r * x

(* matrix product *)
let ( ** ) a b = 
  assert
    (Array.length a = Array.length a.(0)
  && Array.length b = Array.length b.(0)
  && Array.length a = Array.length b);
  let n = Array.length a in
  let c = Array.make_matrix n n 0 in
  for i = 0 to n-1 do
    for j = 0 to n-1 do
      for k = 0 to n-1 do
        c.(i).(j) <- c.(i).(j) + a.(i).(k) * b.(k).(j)
      done;
    done;
  done;
  c

let id = [|[|1; 0|]; [|0; 1|]|]

(* companion matrix for fibonacci *)
let f0 = [|[|0; 1|]; [|1; 1|]|]

let fibo n = (pow id ( ** ) f0 n).(1).(1)

It works by taking the companion matrix and computing its power.