F# · Lesson 7

Recursion and Recursive Types

let rec, tail recursion with accumulators, mutual recursion with `and`, and recursive unions such as trees and expression evaluators.

7 min read

In short

  • Recursive functions need let rec
  • Lists split into [] and head :: tail
  • Work left after the call can overflow the stack on long lists
  • An accumulator makes it a tail call, compiled to a loop
  • Recursive unions model trees; recurse once per case

Why recursion shows up more in F#

F# has loops (for x in xs do ..., while), but idiomatic code avoids mutable counters, and many data structures (lists, trees, JSON, expression trees) are recursive by nature. Pattern matching plus recursion is the natural way to walk them.

In day-to-day code you will still reach for List.map, List.filter and List.fold first. Write your own recursion when no built-in fits: trees, custom walks, "process until a condition", state machines.

let rec

▶ Try
function factorial(n: number): number {
  return n <= 1 ? 1 : n * factorial(n - 1);
}
▶ Try
let rec factorial (n: int) : int =
    if n <= 1 then 1
    else n * factorial (n - 1)
  • rec is required. Without it, the name factorial is not in scope inside its own body, and you get "The value or constructor 'factorial' is not defined". F# reads top to bottom, and nothing is hoisted like JS functions are.
  • factorial (n - 1) needs the parentheses. factorial n - 1 means (factorial n) - 1.

Recursion over a list uses the two list patterns, [] (empty) and head :: tail (first item + the rest):

▶ Try
function sum(xs: number[]): number {
  if (xs.length === 0) return 0;
  const [head, ...tail] = xs;
  return head + sum(tail);
}
▶ Try
let rec sum (xs: int list) : int =
    match xs with
    | [] -> 0
    | head :: tail -> head + sum tail

head :: tail is O(1): F# lists are linked lists, so the tail already exists. (...tail in JS copies the array every time.)

Tail recursion and accumulators

The sum above has a problem. After sum tail returns, there is still work left (head + ...), so every element keeps a stack frame alive. Somewhere between tens of thousands and a couple of hundred thousand elements (it depends on the thread's stack size: about 20,000 on a 1 MB stack), the stack runs out and .NET throws a StackOverflow, which kills the whole process (you cannot try/with it).

The fix is to carry the running result in an extra parameter, the accumulator, so that the recursive call is the very last thing the function does (a tail call). The F# compiler turns tail calls into a loop, so the stack stays flat.

▶ Try
// Most JS engines (V8 in Chrome and Node, Firefox's SpiderMonkey) don't optimise tail calls,
// so in TS you'd just write a loop:
function sum(xs: number[]): number {
  let acc = 0;
  for (const x of xs) acc += x;
  return acc;
}
▶ Try
let sum (xs: int list) : int =
    let rec loop (acc: int) (remaining: int list) : int =
        match remaining with
        | [] -> acc                               // done: the answer is in the accumulator
        | head :: tail -> loop (acc + head) tail  // tail call: nothing left to do afterwards
    loop 0 xs
  • The inner loop hides the accumulator from callers. loop and go are the conventional names.
  • loop (acc + head) tail is in tail position: its result is returned as-is.
  • These are not tail calls: 1 + loop ..., x :: loop rest, or a call inside try ... with.

To build a list tail-recursively, prepend to the accumulator (O(1)) and reverse once at the end:

▶ Try
let doubleAll (xs: int list) : int list =
    let rec loop (acc: int list) (remaining: int list) : int list =
        match remaining with
        | [] -> List.rev acc
        | x :: rest -> loop (x * 2 :: acc) rest
    loop [] xs

Mutual recursion with and

Two functions that call each other must be defined together, joined with and:

▶ Try
function isEven(n: number): boolean { return n === 0 ? true : isOdd(n - 1); }
function isOdd(n: number): boolean { return n === 0 ? false : isEven(n - 1); }
▶ Try
let rec isEven (n: int) : bool =
    if n = 0 then true else isOdd (n - 1)

and isOdd (n: int) : bool =
    if n = 0 then false else isEven (n - 1)

Types work the same way: type A = ... and B = ... lets A mention B and vice versa. You'll meet this with JSON-like data (an object contains properties, a property contains a value) and with parsers.

Recursive discriminated unions

A union case can contain the union itself. Here is a generic binary tree:

▶ Try
type Tree<T> =
  | { kind: "leaf" }
  | { kind: "node"; left: Tree<T>; value: T; right: Tree<T> };
▶ Try
type Tree<'T> =
    | Leaf
    | Node of left: Tree<'T> * value: 'T * right: Tree<'T>

let rec insert (x: 'T) (tree: Tree<'T>) : Tree<'T> =
    match tree with
    | Leaf -> Node(Leaf, x, Leaf)
    | Node(left, v, right) when x < v -> Node(insert x left, v, right)
    | Node(left, v, right) when x > v -> Node(left, v, insert x right)
    | Node _ -> tree // already present
  • 'T is a generic type parameter (<T> in TS). Because we use <, F# infers when 'T : comparison.
  • insert never mutates: it returns a new tree that reuses the untouched branches.

The same shape powers an expression evaluator, the core of rules engines, pricing formulas and query builders:

▶ Try
type Expr =
  | { kind: "num"; value: number }
  | { kind: "add"; left: Expr; right: Expr }
  | { kind: "mul"; left: Expr; right: Expr };

function evaluate(e: Expr): number {
  switch (e.kind) {
    case "num": return e.value;
    case "add": return evaluate(e.left) + evaluate(e.right);
    case "mul": return evaluate(e.left) * evaluate(e.right);
  }
}
▶ Try
type Expr =
    | Num of float
    | Add of Expr * Expr
    | Mul of Expr * Expr

let rec evaluate (expr: Expr) : float =
    match expr with
    | Num n -> n
    | Add(a, b) -> evaluate a + evaluate b
    | Mul(a, b) -> evaluate a * evaluate b

evaluate (Add(Num 2.0, Mul(Num 3.0, Num 4.0))) // 14.0

Trees with any number of children usually hold a list, and recursion combines with list functions:

▶ Try
type Category = { Name: string; Children: Category list }

let rec countCategories (c: Category) : int =
    1 + List.sumBy countCategories c.Children

Trees are rarely deep (a balanced tree of a million items is about 20 levels), so plain non-tail recursion over trees is fine. Accumulators matter for long lists.

Folding over trees

Once you've written size, sum and toList for a tree, you notice they all have the same shape. A fold captures that shape once and takes the "what to do with each value" part as a function:

▶ Try
let rec fold (f: 'S -> 'T -> 'S) (state: 'S) (tree: Tree<'T>) : 'S =
    match tree with
    | Leaf -> state
    | Node(left, v, right) ->
        let afterLeft = fold f state left
        let afterValue = f afterLeft v
        fold f afterValue right

let count tree = fold (fun n _ -> n + 1) 0 tree
let total tree = fold (+) 0 tree
let toList tree = fold (fun acc v -> v :: acc) [] tree |> List.rev // in-order

This is Array.prototype.reduce, but for your own data structure. List.fold, Map.fold and Seq.fold are the same idea for the built-in collections.

Common beginner mistakes

  • Forgetting rec. You get "The value or constructor 'f' is not defined" at the recursive call.
  • f n - 1 instead of f (n - 1). Function application binds tighter than operators.
  • No base case (or one that is never reached), which recurses forever and overflows the stack.
  • Assuming x + loop rest is tail recursive. If anything happens after the call returns, it is not.
  • Appending in a loop with acc @ [x]. That is O(n) per step and O(n²) overall. Prepend with x :: acc, then List.rev.
  • Forgetting and for mutually recursive functions or types. The first definition can't see the second.
  • Writing recursion where List.map/List.filter/List.fold would do. Use the built-ins first.
  • Ignoring warning FS0025 ("incomplete matches") on a recursive union. It means a case will crash at runtime.

Cheat sheet

▶ Try
let rec f x = ... f (x - 1) ...              // self-recursive function
let rec f x = ... g ...
and g y = ... f ...                          // mutually recursive functions
type A = ... and B = ...                     // mutually recursive types
match xs with
| [] -> ...
| x :: rest -> ...                           // list recursion
let rec loop acc xs = ...                    // tail recursion: the accumulator holds the result
loop (x :: acc) rest ... List.rev acc        // build lists in O(n)
type Tree<'T> = Leaf | Node of Tree<'T> * 'T * Tree<'T>
List.sumBy recurse children                  // recursion over n-ary trees

Practise this lesson

In the app: a short video, 6 exercises checked by real tests and a 12-question concept check. Free with a GitHub account. Running the exercises against their tests needs Pro.

Open in the app