Recursion and Tail Calls

The compiler turns self tail calls into loops; .NET also supports tail-call instructions (tail. prefix) for other tail calls in release builds.

let rec factorial n = if n <= 1 then 1I else bigint n * factorial (n - 1)

// Tail recursion with an accumulator: compiled into a loop (no stack overflow)
let factorialTail n =
    let rec loop acc n = if n <= 1 then acc else loop (acc * bigint n) (n - 1)
    loop 1I n
factorialTail 1000                              // works

let rec sumList acc = function
    | [] -> acc
    | x :: xs -> sumList (acc + x) xs           // tail call
sumList 0 [1 .. 1_000_000]

// [<TailCall>] attribute (F# 8): the compiler warns if the function isn't tail recursive
[<TailCall>]
let rec countDown n = if n = 0 then () else countDown (n - 1)

// Continuation-passing style for non-tail recursion on trees
type Tree = Leaf | Node of Tree * int * Tree
let rec sumTree tree cont =
    match tree with
    | Leaf -> cont 0
    | Node (l, v, r) ->
        sumTree l (fun ls -> sumTree r (fun rs -> cont (ls + v + rs)))
sumTree (Node (Node (Leaf, 1, Leaf), 2, Node (Leaf, 3, Leaf))) id   // 6

// Memoization
let memoize f =
    let cache = System.Collections.Generic.Dictionary<_, _>()
    fun x ->
        match cache.TryGetValue x with
        | true, v -> v
        | _ ->
            let v = f x
            cache[
…