Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 40 ยท Functions and Recursion

Recursion in OCaml: let rec

Learn recursion the OCaml way: let rec, base cases and recursive cases, thinking inductively, recursion on numbers and lists, mutual recursion with and, and common mistakes.

Recursion means a function calls itself. In OCaml it is the primary tool for repetition: loops exist, but recursive functions on numbers and lists are shorter, easier to check and are what the whole standard library is built from. This lesson teaches how to write them and how to think about them.

let rec

A normal let cannot refer to its own name, because the name is not defined until after the body. To write a recursive function, you must add rec:

OCAML
let rec factorial n =
  if n <= 1 then 1
  else n * factorial (n - 1)
OCAML
# factorial 5;;
- : int = 120

Forget rec and the compiler says Unbound value factorial. That error message in a recursive function almost always means a missing rec.

Two ingredients

Every correct recursive function has:

  1. A base case: an input simple enough to answer directly (n <= 1).
  2. A recursive case: solve the problem using the answer for a smaller input (n - 1), and combine.

If the recursive call does not move toward the base case, the function never stops and eventually overflows the stack. Check both before running.

Thinking inductively

Do not trace every call in your head. Instead, trust the recursive call, as in mathematical induction. To define sum_to n (the sum of 1 to n):

  • If n = 0, the sum is 0.
  • Otherwise, assume sum_to (n - 1) is correct; the answer is n + sum_to (n - 1).
OCAML
let rec sum_to n =
  if n = 0 then 0 else n + sum_to (n - 1)

How the evaluation unfolds for sum_to 3:

TEXT
sum_to 3
= 3 + sum_to 2
= 3 + (2 + sum_to 1)
= 3 + (2 + (1 + sum_to 0))
= 3 + (2 + (1 + 0))
= 6

Recursion with pattern matching

When data has a recursive structure, as lists do, pattern matching mirrors it. A list is either empty or an element followed by a list:

OCAML
let rec length = function
  | [] -> 0
  | _ :: rest -> 1 + length rest

let rec sum = function
  | [] -> 0
  | x :: rest -> x + sum rest

let rec contains target = function
  | [] -> false
  | x :: rest -> x = target || contains target rest
OCAML
# sum [1; 2; 3; 4];;
- : int = 10
# contains 3 [1; 2; 3];;
- : bool = true

The shape is always the same: one case for [] and one for x :: rest. See Lists for more.

Several recursive calls

Some problems split in two. The Fibonacci numbers:

OCAML
let rec fib n =
  if n < 2 then n
  else fib (n - 1) + fib (n - 2)

This is correct but slow: it recomputes the same values exponentially many times (fib 40 takes seconds). You can fix that with an accumulator (tail recursion) or a memo table. The general lesson: first make it correct, then make it fast.

A classic nicely recursive example, the greatest common divisor by Euclid's algorithm:

OCAML
let rec gcd a b =
  if b = 0 then a else gcd b (a mod b)
(* gcd 48 18 = 6 *)

And fast exponentiation, which halves the problem each time:

OCAML
let rec power base exp =
  if exp = 0 then 1
  else
    let half = power base (exp / 2) in
    if exp mod 2 = 0 then half * half
    else half * half * base
(* power 2 10 = 1024 *)

Mutual recursion with and

Two functions that call each other must be defined together with let rec ... and ...:

OCAML
let rec is_even n =
  if n = 0 then true else is_odd (n - 1)
and is_odd n =
  if n = 0 then false else is_even (n - 1)

Without and, is_even would not yet know is_odd.

Local recursive helpers

Often the user-facing function has a simple signature and a recursive helper does the work:

OCAML
let reverse lst =
  let rec go acc = function
    | [] -> acc
    | x :: rest -> go (x :: acc) rest
  in
  go [] lst

go has an extra parameter acc (the accumulator). This pattern is the key to the next lesson.

Common mistakes

  • Missing rec produces Unbound value.
  • No base case or a base case that is never reached. let rec f n = f (n - 1) runs until the stack overflows (OCaml raises Stack_overflow).
  • Wrong smaller step, such as factorial n calling factorial n or factorial (n + 1).
  • Unparenthesized arguments: factorial n - 1 means (factorial n) - 1. Write factorial (n - 1).
  • Negative inputs: factorial (-3) terminates here thanks to n <= 1; had the base case been n = 0 it would loop forever. Always think about inputs outside the intended range.

A stand-in: counting recursive calls

The stand-in below counts calls so you can see why naive fib explodes while the linear version does not.

JS Stand-in: naive vs linear Fibonacci

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does Unbound value factorial inside a recursive definition usually mean?

    Without rec, the function's own name is not visible in its body.
  2. 2. What are the two ingredients of a recursive function?

    The base case stops the recursion; the recursive case reduces the problem.
  3. 3. How do you define two mutually recursive functions?

    let rec ... and ... lets each function see the other.
  4. 4. What is gcd 48 18 with Euclid's algorithm as defined above?

    gcd 48 18 -> gcd 18 12 -> gcd 12 6 -> gcd 6 0 = 6.

Summary

  • Use let rec for functions that call themselves; and for mutual recursion.
  • A recursive function needs a base case and a step toward it.
  • On lists, match [] and x :: rest.
  • Trust the recursive call (think inductively) instead of tracing everything.
  • Naive double recursion can be exponential; fix it with accumulators or memoization.

Next: Tail recursion