Haskell Cookbook

There's more...

The recursive functions are sometimes ridiculously easy to write, and lead to a very simple and elegant function definition. However, one has to exercise caution to avoid infinite recursion and even a long recursion. For example, the evaluation of fib 5, as shown in the preceding diagram, denotes that each fibonacci value is calculated multiple times. fib 2 is called three times, fib 3 is called twice, and fib 4 is calculated once. 

The preceding implementation of the fibonacci number is very simple and looks very elegant. However, values are calculated multiple times, and in fact, the evaluation order for calculating the n^th fibonacci number is directly proportional to the fibonacci series itself. Hence, if you try to evaluate ...