F Sharp Programming/Recursion
|F# : Recursion and Recursive Functions|
A recursive function is a function which calls itself. Interestingly, in contrast to many other languages, functions in F# are not recursive by default. A programmer needs to explicitly mark a function as recursive using the
let rec someFunction = ...
Factorial in F#
The factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example, 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720.
In mathematics, the factorial is defined as follows:
Naturally, we'd calculate a factorial by hand using the following:
fact(6) = = 6 * fact(6 - 1) = 6 * 5 * fact(5 - 1) = 6 * 5 * 4 * fact(4 - 1) = 6 * 5 * 4 * 3 * fact(3 - 1) = 6 * 5 * 4 * 3 * 2 * fact(2 - 1) = 6 * 5 * 4 * 3 * 2 * 1 * fact(1 - 1) = 6 * 5 * 4 * 3 * 2 * 1 * 1 = 720
In F#, the factorial function can be written concisely as follows:
let rec fact x = if x < 1 then 1 else x * fact (x - 1)
But note that this function as it stands returns 1 for all negative numbers but factorial is undefined for negative numbers. This means that in real production programs you must either design the rest of the program so that factorial can never be called with a a negative number or trap negative input and throw an exception. Exceptions will be discussed in a later chapter.
Here's a complete program:
open System let rec fact x = if x < 1 then 1 else x * fact (x - 1) (* // can also be written using pattern matching syntax: let rec fact = function | n when n < 1 -> 1 | n -> n * fact (n - 1) *) Console.WriteLine(fact 6)
Greatest Common Divisor (GCD)
The greatest common divisor, or GCD function, calculates the largest integer number which evenly divides two other integers. For example, largest number that evenly divides 259 and 111 is 37, denoted GCD(259, 111) = 37.
Euclid discovered a remarkably simple recursive algorithm for calculating the GCD of two numbers:
To calculate this by hand, we'd write:
gcd(259, 111) = gcd(111, 259 % 111) = gcd(111, 37) = gcd(37, 111 % 37) = gcd(37, 0) = 37
In F#, we can use the
% (modulus) operator to calculate the remainder of two numbers, so naturally we can define the GCD function in F# as follows:
open System let rec gcd x y = if y = 0 then x else gcd y (x % y) Console.WriteLine(gcd 259 111) // prints 37
Let's say we have a function
A which, at some point, calls function
B finishes executing, the CPU must continue executing
A from the point where it left off. To "remember" where to return, the function
A passes a return address as an extra argument to
B on the stack;
B jumps back to the return address when it finishes executing. This means calling a function, even one that doesn't take any parameters, consumes stack space, and it's extremely easy for a recursive function to consume all of the available memory on the stack.
A tail recursive function is a special case of recursion in which the last instruction executed in the method is the recursive call. F# and many other functional languages can optimize tail recursive functions; since no extra work is performed after the recursive call, there is no need for the function to remember where it came from, and hence no reason to allocate additional memory on the stack.
F# optimizes tail-recursive functions by telling the CLR to drop the current stack frame before executing the target function. As a result, tail-recursive functions can recurse indefinitely without consuming stack space.
Here's non-tail recursive function:
> let rec count n = if n = 1000000 then printfn "done" else if n % 1000 = 0 then printfn "n: %i" n count (n + 1) (* recursive call *) () (* <-- This function is not tail recursive because it performs extra work (by returning unit) after the recursive call is invoked. *);; val count : int -> unit > count 0;; n: 0 n: 1000 n: 2000 n: 3000 ... n: 58000 n: 59000 Session termination detected. Press Enter to restart. Process is terminated due to StackOverflowException.
Let's see what happens if we make the function properly tail-recursive:
> let rec count n = if n = 1000000 then printfn "done" else if n % 1000 = 0 then printfn "n: %i" n count (n + 1) (* recursive call *);; val count : int -> unit > count 0;; n: 0 n: 1000 n: 2000 n: 3000 n: 4000 ... n: 995000 n: 996000 n: 997000 n: 998000 n: 999000 done
If there was no check for
n = 1000000, the function would run indefinitely. It's important to ensure that all recursive function have a base case to ensure they terminate eventually.
How to Write Tail-Recursive Functions
Let's imagine that, for our own amusement, we wanted to implement a multiplication function in terms of the more fundamental function of addition. For example, we know that
6 * 4 is the same as
6 + 6 + 6 + 6, or more generally we can define multiplication recursively as
M(a, b) = a + M(a, b - 1), b > 1. In F#, we'd write this function as:
let rec slowMultiply a b = if b > 1 then a + slowMultiply a (b - 1) else a
It may not be immediately obvious, but this function is not tail recursive. It might be more obvious if we rewrote the function as follows:
let rec slowMultiply a b = if b > 1 then let intermediate = slowMultiply a (b - 1) (* recursion *) let result = a + intermediate (* <-- additional operations *) result else a
The reason it is not tail recursive is because after the recursive call to
slowMultiply, the result of the recursion has to added to
a. Remember tail recursion needs the last operation to be the recursion.
slowMultiply function isn't tail recursive, it throws a
StackOverFlowException for inputs which result in very deep recursion:
> let rec slowMultiply a b = if b > 1 then a + slowMultiply a (b - 1) else a;; val slowMultiply : int -> int -> int > slowMultiply 3 9;; val it : int = 27 > slowMultiply 2 14;; val it : int = 28 > slowMultiply 1 100000;; Process is terminated due to StackOverflowException. Session termination detected. Press Enter to restart.
It's possible to re-write most recursive functions into their tail-recursive forms using an accumulating parameter:
> let slowMultiply a b = let rec loop acc counter = if counter > 1 then loop (acc + a) (counter - 1) (* tail recursive *) else acc loop a b;; val slowMultiply : int -> int -> int > slowMultiply 3 9;; val it : int = 27 > slowMultiply 2 14;; val it : int = 28 > slowMultiply 1 100000;; val it : int = 100000
The accumulator parameter in the inner loop holds the state of our function throughout each recursive iteration.
Faster Fib Function
The following function calculates the nth number in the Fibonacci sequence:
let rec fib = function | n when n=0I -> 0I | n when n=1I -> 1I | n -> fib(n - 1I) + fib(n - 2I)
- Note: The function above has the type
val fib : bigint -> bigint. Previously, we've been using the
System.Int32type to represent numbers, but this type has a maximum value of
2,147,483,647. The type
bigintis used for arbitrary size integers such as integers with billions of digits. The maximum value of
bigintis constrained only by the available memory on a users machine, but for most practical computing purposes we can say this type is boundless.
The function above is neither tail-recursive nor particularly efficient with a computational complexity O(2n). The tail-recursive form of this function has a computational complexity of O(n). Re-write the function above so that it's tail recursive.
You can verify the correctness of your function using the following:
fib(0I) = 0 fib(1I) = 1 fib(2I) = 1 fib(3I) = 2 fib(4I) = 3 fib(5I) = 5 fib(10I) = 55 fib(100I) = 354224848179261915075