FSharp Functional Programming—Recursion
| CSharp-Online.NET:Articles |
| .NET Articles |
| © 2007 Robert Pickering |
Recursion
Recursion means defining a function in terms of itself; in other words, the function calls itself within its definition. Recursion is often used in functional programming where you would use a loop in imperative programming. Many believe that algorithms are much easier to understand when expressed in terms of recursion rather than loops.
To use recursion in F#, 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)
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 sequence is 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, you 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).
The previous code also uses F# pattern matching, which I discuss in the "Pattern Matching" section later in this chapter.
 
|
