Recursion and Tail Calls

In functional code, recursion replaces many loops: a function handles the simple case directly and the rest by calling itself on a smaller problem.

let rec length list =
    match list with
    | [] -> 0
    | _ :: tail -> 1 + length tail

let rec map f list =
    match list with
    | [] -> []
    | head :: tail -> f head :: map f tail

printfn "%d" (length [5; 6; 7])
printfn "%A" (map (fun x -> x * x) [1; 2; 3])

3
[1; 4; 9]

Stack overflow

Each call waits for the recursive call to finish before adding 1, so it needs a stack frame per item. Very long lists overflow the stack:

// illustrative: crashes the process
let rec length list =
    match list with
    | [] -> 0
    | _ :: tail -> 1 + length tail

printfn "%d" (length [1 .. 1_000_000])

The process crashes; the output starts like this:

Stack overflow.
Repeated 24008 times:
--------------------------------
   at FSI_0001.length[[System.Int32, ...]](Microsoft.FSharp.Collections.FSharpList`1<Int32>)
--------------------------------

Tail recursion with an accumulator

If the recursive call is the very last thing a function does (a tail call), F# compiles it into a loop — no stack growth. The trick is to carry the result so far in an accumulator parameter:

let length list =
    let rec loop acc remaining =
        match remaining with
        | [] -> acc
        | _ :: tail -> loop (acc + 1) tail
    loop 0 list

printfn "%d" (length [1 .. 1_000_000])

let sumTo n =
    let rec go acc i = if i > n then acc else go (acc + int64 i) (i + 1)
    go 0L 1

printfn "%d" (sumTo 1_000_000)

1000000
500000500000

The inner loop / go function is a common idiom: the public function has a clean signature, and the helper carries the state.

[<TailCall>]

Mark a function with [<TailCall>] and the compiler warns if any recursive call isn't in tail position. The check runs when you build a project (dotnet build):

// illustrative: Program.fs in a console project
[<TailCall>]
let rec factorial n =
    if n <= 1 then 1 else n * factorial (n - 1)

printfn "%d" (factorial 5)

Program.fs(3,31): warning FS3569: The member or function 'factorial' has the 'TailCallAttribute' attribute, but is not being used in a tail recursive way.

n * factorial (n - 1) must multiply after the call returns, so the call isn't the last thing the function does.

Mutual recursion

Functions that call each other are defined together with and:

let rec isEven n = if n = 0 then true else isOdd (n - 1)
and isOdd n = if n = 0 then false else isEven (n - 1)

printfn "%b %b" (isEven 10) (isOdd 7)

true true

Recursion over trees

Recursive data calls for recursive functions:

type Tree =
    | Leaf
    | Node of left: Tree * value: int * right: Tree

let rec insert x tree =
    match tree with
    | Leaf -> Node (Leaf, x, Leaf)
    | Node (l, v, r) when x < v -> Node (insert x l, v, r)
    | Node (l, v, r) -> Node (l, v, insert x r)

let rec toList tree =
    match tree with
    | Leaf -> []
    | Node (l, v, r) -> toList l @ [v] @ toList r

let tree = [5; 2; 8; 1; 9; 3] |> List.fold (fun t x -> insert x t) Leaf
printfn "%A" (toList tree)

[1; 2; 3; 5; 8; 9]

• Most of the time you don't need explicit recursion — List.fold, List.map, and friends are already tail-safe.
• Reach for recursion when the shape of the problem is recursive (trees, parsers) or when you need to stop early with custom logic.

Practice

Write a tail-recursive digits n that returns the list of decimal digits of a positive integer, so digits 2024 is [2; 0; 2; 4].

let digits n =
    let rec loop acc n =
        if n < 10 then n :: acc
        else loop (n % 10 :: acc) (n / 10)
    loop [] n

printfn "%A" (digits 2024)
printfn "%A" (digits 7)

[2; 0; 2; 4]
[7]