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 5th fibonacci number:
The preceding function is a simple recursive function. One can also implement mutually recursive functions. For example, we can implement functions isEven and isOdd that check whether a number is even or odd, respectively, in a mutually recursive way. We will use 1 and 2 as seed values for odd and even tests, respectively. In a mutually recursive function definition, one function, f1, calls the other function, f2, whereas the other function, f2, calls this function, f1:
isEven 2 = True
isEven n = isOdd (n-1)
isOdd 1 = True
isOdd n = isEven (n-1)
Note how recursive calls are made. Each recursive call is breaking down the problem into a smaller problem. Also, at a certain stage, one has to handle a basic condition to avoid infinite recursion.