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 rec keyword:

let rec someFunction = ...

Examples

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:

$fact(n)={\begin{cases}1&{\mbox{if }}n=0\\n\times fact(n-1)&{\mbox{if }}n>0\\\end{cases}}$

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:

$gcd(x,y)={\begin{cases}x&{\mbox{if }}y=0\\gcd(y,remainder(x,y))&{\mbox{if }}x>=y{\mbox{ and }}y>0\\\end{cases}}$

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

Tail Recursion

Let's say we have a function A which, at some point, calls function B. When 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.

Since the 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.

Exercises

Solutions.

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 int or System.Int32 type to represent numbers, but this type has a maximum value of 2,147,483,647. The type bigint is used for arbitrary size integers such as integers with billions of digits. The maximum value of bigint is 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(2ⁿ). 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

Additional Reading

• Understanding Tail Recursion
• How can I implement a tail-recursive append?