Haskell Cookbook

How it works...

The heart of the definition is as follows:

    fib n = fib (n-1) + fib (n-2)

Simple recursion involves calling the same function we are defining. In the definition of fib n, we will call fib (n-1) and fib (n-2) and add their results. 

The evaluation of the fibonacci number by this recursive definition is shown in the following diagram. The diagram shows the evaluation of fib 5. Note how at each stage, the fib function gradually reduces the argument and recursively calculates the value of the 5^th fibonacci number:

The preceding function is a simple recursive function. One can also implement mutually recursive functions. For example, ...