Here you can find 3 implementations of Fibonacci, in F#. The first is naively recursive which exhibits the poor performance you mentioned. The last is tail recursive which does not.
Now that we seem to have gone a little off piste here, anyone who is unsure about the benefits of tail call optimization might want to check out this recent article: Parsing Protobuf at 2+GB/s: How I Learned To Love Tail Calls in C
Consider the task of computing an (for positive integers n) using simple repetitive multiplication, e.g., compute a4 simply as a product:
aaaa
Now consider that multiplication is associative, so you could compute that as:
((((a)a)a)a)
or:
(a(a(a(a))))
or:
(aa)(aa)
or:
(a(aa)a)
etc.
How many distinct ways could you parenthesize that?
How many distinct ways could you parenthesize an when written out that way?
I devised an algorithm for that once, and coded it in C both iteratively and recursively, and ran this on a 80386. The recursive version slowed down noticeably at about a6 and took many minutes to run for (IIRC) a10 and crashed at about a12. The iterative version ran in less than one second for values up to ahuge.
(The algorithm inherently produced lots of duplicates, so there was additional code to compare each result with previous results to filter out the duplicates.)
I did that for Ackerman’s Function once also, many years ago, using a CDC-6400 computer which had 60-bit integers. The recursive definition could only compute up to about A(3) in any reasonable amount of time. I figured out how to do it iteratively, and got up to something like a(6) or so, before it overflowed the 60-bit integer limit, but the computation was very fast.
Those numbers are called the Catalan numbers (not after Catalonia, but a mathematician of that name). The n-th Catalan number is C_n=\frac{(2n)!}{n!(n+1)!}. They satisfy the recursion equation C_n=\sum_{i=1}^{n-1}C_iC_{n-i} which expresses the fact that you have to start with an “outer multiplication” of a term of length i by one of length n-i. If you form the formal power series f(x)=\sum_{i=1}^{\infty}C_ix^i, then use the recursion above to derive xf(x)^2=1+f(x) and use the quadratic formula to get an expression involving \sqrt(1-4x), which can calculated using the generalized binomial theorem (for the fractional exponent 1/2 to produce, eventually, the formula above. There is more detail in the Wiki entry, q.g.
Using that formula, you can clearly compute the exact value of C_n via a simple loop like
C_5 = \frac72 \times \frac83 \times \frac 94 \times \frac{10}{5}
but can one do better?
Bizarrely, I did something like this renaming in my only published mathematical article. It appeared in the Journal of Undergraduate Mathematics (Volume 7, Number 1), which was published in March of 1975. This journal no longer exists and was pretty obscure anyway. I talked about a generalization of Pascal’s triangle. Pascal’s triangle was known long before Blaise Pascal. One of those who knew about it was Omar Khayyam. My paper was about the n-dimensional generalization of Pascal’s triangle. I called them Khayyamic n-simplices. The paper was titled “Khayyamic n-simplices: a generalization of Pascal’s triangle”.