What are Recursive Functions

Recursive functions are the ones that call themselves. Recursive functions are commonly used in F#.

The keyword rec is used for creating recursive functions:

let funcName = ....

let rec funcName = ...

Here's an example to calculate the sum of a given list:

let rec sum list =
    match list with
    | head :: tail -> head + sum tail
    | [] -> 0

Here's what's going on:

1. Pattern matching is used

2. If the list is empty, you hit [] case

   1. The function returns 0

3. If the list isn't empty, you hit head :: tail case

   1. head is the value of the first item

   2. tail is the remaining list, the list after the first item

   3. head + sum tail is where recursion happens

   4. sum function is called again with tail

   5. This goes on and on till the terminal condition isn't met, [] case

Recursive Functions and Stack Overflow

Pay attention to head + sum tail in the previous example. The function sum is calling sum again. When a function calls another function, the called function is stacked on top of the caller. There is a practical limit to this.

Consider this example:

// int list -> int
let rec sum list =
    match list with
    | head :: tail -> head + sum tail
    | [] -> 0

sum [ 1; 2; 3; 4; 5 ] |> printfn "%d" // 15
sum [ 1..100 ] |> printfn "%d" // 5050
sum [ 1..1000 ] |> printfn "%d" // 500500
sum [ 1..10000 ] |> printfn "%d" // 50005000
sum [ 1..100000 ] |> printfn "%d" // crash... stack overflow

For 100,000 items in the list, too much memory is required for stack growth.

You won't frequently counter lists with 100,000 items, but a call like sum [ 1..1000 ], which is with 1,000 items is also problematic. It's a call depth of 1,000, which will require a considerable amount of memory.

Understanding Tail Recursion

Going back to the previous example:

let rec sum list =
    match list with
    | head :: tail -> head + sum tail
    | [] -> 0

In case of head :: tail, the expression is head + sum tail. This is effectively saying:

1. Solve the expression sum tail

2. And then, do head + <whatever the result is>

This will happen for all the items. In other words, stack space (for function call) is required for each item in the supplied list. This is highly inefficient, and for large lists, it's impossible.

To solve this, tail recursion is used. The basic idea is:

1. When the function calls itself, there should be no need of saving its state (the state of the currently running/called instance of the function)

2. With head + sum tail state is maintained

3. When saving the state is not required F# compiler can utilize tail recursion

Here's the optimized version of the same function:

// int list -> int
let safeSum list =
    let rec inner l total =
        match l with
        | head :: tail -> inner tail (head + total)
        | [] -> total
    inner list 0

safeSum [ 1; 2; 3; 4; 5 ] |> printfn "%d" // 15
safeSum [ 1..100 ] |> printfn "%d" // 5050
safeSum [ 1..1000 ] |> printfn "%d" // 500500
safeSum [ 1..10000 ] |> printfn "%d" // 50005000
safeSum [ 1..100000 ] |> printfn "%d" // 705082704
safeSum [ 1..1000000 ] |> printfn "%d" // 1784293664

This technique typically involves 3 ideas:

1. An inner recursive function (inner)

2. An accumulated value:

   1. updated per cycle (head + total)

   2. passed to the inner function (inner tail (head + total))

   3. the final result at the terminal condition ([] -> total)

3. The outer function triggers the chain with an initial value accumulated value (inner list 0)

Here's the function for finding min value from a list:

let min list =
    if List.length list = 0 then
        raise (System.ArgumentException("Empt list provided!"))
    else
        let rec loop list acc =
            match list with
            | head :: tail -> loop tail (if head < acc then head else acc)
            | [] -> acc
        loop list Int32.MaxValue

Here's the function for finding max value from a list:

// recursive function for finding max
// no stack overflow, tail recursion
let max list =
    if List.length list = 0 then
        raise (System.ArgumentException("Empt list provided!"))
    else
        let rec loop list acc =
            match list with
            | head :: tail -> loop tail (if head > acc then head else acc)
            | [] -> acc
        loop list Int32.MinValue

Here's an example of using StringBuilder to convert char list to string:

open System.Text

let charListToString list =
    let rec inner (l: char list) (sb: StringBuilder) =
        match l with
        | head :: tail -> inner tail (sb.Append(head))
        | [] -> sb.ToString()

    inner list (StringBuilder())

charListToString [ 'a'; 'b'; 'c'; 'd'; 'e' ] |> printfn "%A" // "abcde"

If you have reached so far, congratulations.

Keep reading!