Performance of Fibonacci

Question

f[0] = 0;
f[1] = 1;
f[x_] := f[x-1] + f[x-2]

This function is running slow in Mathematica and I need to increase the speed. I have to use functional programming and recursion. I'm not sure why this is running so slow, and even the slightest idea how to improve this would be helpful.

Answer 1

Memoization is a good way to write a faster recursive function. However, in this case there is a recursive alternative that runs tremendously faster than original function, without requiring memoization.

The key observation is to see that the original definition performs a lot of redundant calculations. Consider what happens if we calculate fib[4]:

fib[4] = fib[3] + fib[2]
  fib[3] = fib[2] + fib[1]
    fib[2] = fib[1] + fib[0]
      fib[1] = 1
      fib[0] = 1
    ∴ fib[2] = 1 + 1 = 2
    fib[1] = 1
  ∴ fib[3] = 2 + 1 = 3
  fib[2] = fib[1] + fib[0]
    fib[1] = 1
    fib[0] = 1
  ∴ fib[2] = 1 + 1 = 2
∴ fib[4] = 2 + 1 = 3

In this process, fib[2] and fib[0] were computed twice each and fib[1] was computed thrice. For larger computations, the waste grows dramatically -- exponentially in fact.

If one were to calculate the same Fibonacci number by hand, one might proceed something like this:

0: given   0
1: given   1
2: 0 + 1 = 1
3: 1 + 1 = 2
4: 1 + 2 = 3

There are no redundant calculations. At any given point, one only needs to consider the previous two results. This latter approach can be expressed recursively thus:

fib2[0] = 0;
fib2[n_] :=
  Module[{f},
    f[n, p1_, _] := p1;
    f[x_, p1_, p2_] := f[x + 1, p1 + p2, p1];
    f[1, 1, 0]
  ]

Block[{$IterationLimit = Infinity}, fib2[100000]]

No doubt, this form is not as easy to read as the original. On the other hand, the original function took 35 seconds to compute fib[35] on my machine whereas the revised function's runtime for same was reported as zero. Furthermore, the revised function computes fib2[100000] in 0.281 seconds, without requiring any of the extra storage of memoization. fib[100000] is quite out of reach of the original function and the memoized version crashed my Mathematica 7.01 kernel -- too many memoized rules perhaps?

Note that Mathematica, by default, will iterate a function no more than 4096 times. To raise that limit, you must assign a higher value to $IterationLimit as illustrated in the example above.

Of course, in Mathematica there are plenty of non-recursive ways to calculate Fibonacci numbers, up to and including the built-in Fibonacci function. But that is not the point of this exercise.

Tail Call Optimization?

It is always desirable to express recursive functions using tail calls. This permits the recursion to be executed by simple iteration, without the overhead of retaining intermediate results on the stack. fib2 is tail recursive. Some languages, like Scheme, mandate tail call optimization. Other languages, like Java, could support it but don't (or won't, as in the case of Python).

In the case of Mathematica, it is not clear to what extent tail call optimization is performed. For further discussion of this point, see another SO question.

Answer 2

A good way to write a faster recursive function is to have it memorize previous values. This does come at the cost of memory, of course, but it can help in cases like this. In order to calculate f[x], you calculate f[x-1] and f[x-2] - and then to calculate f[x-1], you calculate f[x-2] again; you end up recalculating a lot of values a lot of times. (Forgive my imprecision!)

To store things as you go, you can use this idiom:

f[x_] := ( f[x] = (* calculation of f[x] goes here *)  )

Edit: I don't have mathematica on this machine, but I'm pretty sure there's no way this computes the wrong value.

f[0] = 0;
f[1] = 1;
f[x_] := ( f[x] = f[x-1] + f[x-2] );

f[256]

Like I said in a comment below, if you have other definitions of f, you might want to wipe them out first with Clear[f].

Thanks to rcollyer: Be careful about $RecursionLimit! It defaults to 256. (Of course, this is with good reason. Really deep recursion is usually a bad idea.)

Answer 3

Jefromi is right. Look at Memoization on wikipedia. They use the example of factorial and how to speed it up with memoization.