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

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 2

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