Recursion in F#

To use recursion in F#, we use the rec keyword after the let keyword to make the identifier available within the function definition. The following example shows recursion in action. Notice how on the fifth line the function makes two calls to itself as part of its own definition.


#light
let rec fib x =
match x with
| 1 -> 1
| 2 -> 1
| x -> fib (x - 1) + fib (x - 2)
printfn "(fib 2) = %i" (fib 2)
printfn "(fib 6) = %i" (fib 6)
printfn "(fib 11) = %i" (fib 11)


output:

The results of this example, when compiled and executed, are as follows:
(fib 2) = 1
(fib 6) = 8
(fib 11) = 89



This function calculates the nth term in the Fibonacci sequence. The Fibonacci sequenceis generated by adding the previous two numbers in the sequence, and it progresses as follows:
1, 1, 2, 3, 5, 8, 13, …. Recursion is most appropriate for calculating the Fibonacci sequence, because the definition of any number in the sequence, other than the first two, depends on being able to calculate the previous two numbers, so the Fibonacci sequence is defined in terms of itself.

Although recursion is a powerful tool, we should always be careful when using it. It is easy to inadvertently write a recursive function that never terminates. Although intentionally writing a program that does not terminate is sometimes useful, it is rarely the goal when trying to perform calculations. To ensure that recursive functions terminate, it is often useful to think of recursion in terms of a base case and the recursive case. The recursive case is the value for which the function is defined in terms of itself; for the function fib, this is any value other than 1 and 2. The base case is the nonrecursive case; that is, there must be some value where the function is not defined in terms of itself. In the fib function, 1 and 2 are the base cases. Having a base case is not enough in itself to ensure termination. The recursive case must tend toward the base case. In the fib example, if x is greater than or equal to 3, then the recursive case will tend toward the base case because x will always become smaller and at some point reach 2. However, if x is less than 1, then x will grow continually more negative, and the function will recurse until the limits of the machine are reached, resulting in a stack overflow error(System.StackOverflowException).