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.
In short
- Recursive functions need
let rec - Lists split into
[]andhead :: 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
function factorial(n: number): number {
return n <= 1 ? 1 : n * factorial(n - 1);
}
let rec factorial (n: int) : int =
if n <= 1 then 1
else n * factorial (n - 1)
recis required. Without it, the namefactorialis 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 - 1means(factorial n) - 1.
Recursion over a list uses the two list patterns, [] (empty) and head :: tail (first item + the rest):
function sum(xs: number[]): number {
if (xs.length === 0) return 0;
const [head, ...tail] = xs;
return head + sum(tail);
}
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.
// 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;
}
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
loophides the accumulator from callers.loopandgoare the conventional names. loop (acc + head) tailis in tail position: its result is returned as-is.- These are not tail calls:
1 + loop ...,x :: loop rest, or a call insidetry ... with.
To build a list tail-recursively, prepend to the accumulator (O(1)) and reverse once at the end:
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:
function isEven(n: number): boolean { return n === 0 ? true : isOdd(n - 1); }
function isOdd(n: number): boolean { return n === 0 ? false : isEven(n - 1); }
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:
type Tree<T> =
| { kind: "leaf" }
| { kind: "node"; left: Tree<T>; value: T; right: Tree<T> };
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
'Tis a generic type parameter (<T>in TS). Because we use<, F# inferswhen 'T : comparison.insertnever 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:
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);
}
}
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:
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:
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 - 1instead off (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 restis 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 withx :: acc, thenList.rev. - Forgetting
andfor mutually recursive functions or types. The first definition can't see the second. - Writing recursion where
List.map/List.filter/List.foldwould 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
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