Skip to content
LumenaryAcademy
Foundations 55 min

Recursion and termination

Lean has no loops in its core, only recursion, and it insists that every recursive function ends. Structural recursion, well-founded recursion with termination_by, and the honest escape hatches.

Code tested · 5AI-draftedAwaiting review by a computer scientist
MotivationH

Why Lean insists on termination

In lesson 3, every function on a tree called itself on a subtree, and Lean accepted them silently. Try writing a function that calls itself on its own argument, in a file called bad.lean, and Lean refuses:

lean
def bad (n : Nat) : Nat := bad n + 1
text
bad.lean:1:4: error: fail to show termination for
  bad
with errors
failed to infer structural recursion:
Not considering parameter n of bad:
  it is unchanged in the recursive calls
no parameters suitable for structural recursion

well-founded recursion cannot be used, `bad` does not take any (non-fixed) arguments

In Python, the same function would run until the stack overflowed. Why is Lean stricter than Python?

Because a Lean definition is not just code; it is also a mathematical equation that proofs may use. If bad were accepted, Lean would know that bad 0 = bad 0 + 1 for the natural number bad 0. Subtract bad 0 from both sides and you have 0 = 1, and from a false statement anything can be proved. One careless definition would make every theorem in the system worthless. So Lean requires every ordinary function to be total: defined, and terminating, for every input of its type. (That is also why 7 / 0 had to be something, 0, in lesson 2.)

Of course, Lean cannot decide in general whether a program terminates; Turing proved in 1936 that no program can (see Computability). So Lean asks you for an argument: either the recursion follows the structure of the data, which Lean checks automatically, or some quantity decreases with every call, which you name and Lean (usually) proves. When neither is possible, Lean gives you honest ways out, as long as you label them. This lesson covers all three.

DefinitionsH

Structural recursion

Definition— Structural recursion

A function is structurally recursive when each recursive call is on a strict piece of one of its arguments, a piece obtained by pattern matching: n inside n + 1, xs inside x :: xs, a subtree inside a node. Since values of an inductive type are finite, built by finitely many constructors, such recursion must end. Lean checks this automatically.

lean
def factorial : Nat → Nat
  | 0 => 1
  | n + 1 => (n + 1) * factorial n

def length : List α → Nat
  | [] => 0
  | _ :: xs => 1 + length xs

def zipWith (f : α → β → γ) : List α → List β → List γ
  | x :: xs, y :: ys => f x y :: zipWith f xs ys
  | _, _ => []

/-- The naive definition: two recursive calls per step. -/
def fibSlow : Nat → Nat
  | 0 => 0
  | 1 => 1
  | n + 2 => fibSlow n + fibSlow (n + 1)

/-- The same numbers, carrying the last two along: one call per step. -/
def fibPair : Nat → Nat × Nat
  | 0 => (0, 1)
  | n + 1 => let (a, b) := fibPair n; (b, a + b)

def fib (n : Nat) : Nat := (fibPair n).1

#eval factorial 20
#eval length ["a", "b", "c"]
#eval zipWith (· * ·) [1, 2, 3] [10, 20, 30, 40]
#eval (List.range 11).map fibSlow
#eval fib 90
text
2432902008176640000
3
[10, 40, 90]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
2880067194370816120

The pattern n + 1 matches any natural number except zero and names its predecessor n; n + 2 matches 2 and above. Since Nat is the inductive type of lesson 3 (zero or succ n), these are really the patterns zero, succ n and succ (succ n), and every recursive call is on something structurally smaller. Lists work the same way: x :: xs names the head and the tail, and the call is on the tail.

length and zipWith work for lists of any element type. The Greek letters α, β and γ (type \a, \b, \g) are type variables, which Lean adds as hidden parameters automatically; lesson 5 explains them properly. zipWith matches two lists at once and stops when either runs out; the catch-all _, _ covers both "first list empty" and "second list empty".

The two Fibonacci functions are a lesson in themselves. fibSlow is a direct transcription of the definition, and it is exponentially slow: computing fibSlow 90 would make more calls than there are seconds in the age of the universe. fibPair returns the pair of consecutive Fibonacci numbers (F n, F (n+1)), so each step needs only one recursive call, and fib 90 is instant. Both are structurally recursive, and in lesson 9 we will prove that they compute the same numbers, which is a much stronger statement than testing a few values.

Worked examplesH

Well-founded recursion

Many natural algorithms do not recurse on a structural piece. Euclid's algorithm calls itself on a % b, a number computed by division, not a pattern. Binary search and merge sort split their input in half. For these, Lean uses well-founded recursion: you say which quantity decreases, and Lean proves that it does.

Definition— termination_by and decreasing_by

termination_by e, after a definition, names a measure: an expression, usually a natural number, that must be strictly smaller at every recursive call than at the call that made it. Since natural numbers cannot decrease forever, the recursion must end. For each recursive call Lean generates a proof obligation, "the measure here is smaller than there", and tries to prove it automatically. decreasing_by supplies your own proof when the automatic one fails.

Here is a first attempt at Euclid's algorithm, in a file called euclid.lean:

lean
def gcd (a b : Nat) : Nat :=
  if b = 0 then a else gcd b (a % b)
termination_by b

Lean cannot finish the proof on its own, and it tells you exactly where it is stuck:

text
euclid.lean:2:23: error: failed to prove termination, possible solutions:
  - Use `have`-expressions to prove the remaining goals
  - Use `termination_by` to specify a different well-founded relation
  - Use `decreasing_by` to specify your own tactic for discharging this kind of goal
a b : Nat
h✝ : ¬b = 0
⊢ a % b < b

The last three lines are a proof goal, the format you will meet constantly in lessons 8 to 10. Above the ⊢ (read "prove") are the facts available: a and b are natural numbers, and a hypothesis h✝ says b is not zero (we are in the else branch). Below it is what must be shown: a % b < b. That is true precisely because b ≠ 0, but it needs a library fact about remainders. We supply it:

lean
/-- Euclid's algorithm. -/
def gcd (a b : Nat) : Nat :=
  if b = 0 then a else gcd b (a % b)
termination_by b
decreasing_by exact Nat.mod_lt a (by omega)

/-- The digits of `n` in base 10, most significant first. -/
def digits (n : Nat) : List Nat :=
  if n < 10 then [n] else digits (n / 10) ++ [n % 10]

def merge : List Nat → List Nat → List Nat
  | [], ys => ys
  | xs, [] => xs
  | x :: xs, y :: ys =>
    if x ≤ y then x :: merge xs (y :: ys) else y :: merge (x :: xs) ys

def mergeSort (xs : List Nat) : List Nat :=
  if xs.length < 2 then xs
  else
    let half := xs.length / 2
    merge (mergeSort (xs.take half)) (mergeSort (xs.drop half))
termination_by xs.length

#eval gcd 1071 462
#eval digits 2026
#eval mergeSort [38, 27, 43, 3, 9, 82, 10]
text
21
[2, 0, 2, 6]
[3, 9, 10, 27, 38, 43, 82]

Nat.mod_lt a is the library theorem "if b > 0 then a % b < b", and by omega proves its premise b > 0 from the hypothesis ¬b = 0. (omega is a tactic that proves facts of linear arithmetic over Nat and Int; lesson 8 introduces tactics properly.) You do not need to understand every symbol yet. The point is the workflow: Lean shows you the goal, you supply the missing reason.

The other three functions needed no help at all. For digits, Lean guessed the measure n by itself and proved n / 10 < n from the fact that n ≥ 10 in the recursive branch. For mergeSort, we named the measure, the length of the list, and Lean proved that take and drop of half a list of length at least 2 are shorter. And merge recurses on two lists, sometimes shortening one, sometimes the other; Lean found that on its own too. The automation behind this, decreasing_tactic, tries simplification and arithmetic, and it succeeds on most everyday recursion. When it fails, read the goal it shows you: often the fix is a hypothesis it did not have, which you can provide by writing if h : … then … else … so that the condition is in scope with a name.

What the choice means for proofs

The two kinds of recursion behave differently once you start proving things. A structurally recursive function computes inside the type checker: Lean can check factorial 5 = 120 just by evaluating both sides, which is what the one-word proof rfl (for "reflexivity") asks it to do. A function defined by well-founded recursion is deliberately kept from unfolding on its own, because evaluating it would mean evaluating its termination proof too, which can be very slow. Instead Lean generates equation lemmas that state its defining equation, and you unfold it explicitly, for instance with simp [gcd]:

lean
def factorial : Nat → Nat
  | 0 => 1
  | n + 1 => (n + 1) * factorial n

def gcd (a b : Nat) : Nat :=
  if b = 0 then a else gcd b (a % b)
termination_by b
decreasing_by exact Nat.mod_lt a (by omega)

-- Structural recursion: Lean can compute the answer while checking the proof.
example : factorial 5 = 120 := rfl

-- Well-founded recursion: unfold the definition explicitly instead.
example : gcd 12 8 = 4 := by simp [gcd]

#check gcd.eq_1
text
gcd.eq_1 (a b : Nat) : gcd a b = if b = 0 then a else gcd b (a % b)

An example is a theorem without a name, handy for checks like these; if a proof failed, Lean would report an error and the file would not be accepted. Writing rfl for the gcd example instead fails, with a message that the two sides do not match. None of this affects running the code, which is equally fast either way. It is one more reason experienced Lean programmers prefer structural recursion when it is natural, and reach for termination_by when it is not.

Mutual recursion

Functions that call each other go in a mutual … end block, and the same rules apply: here isEven (n + 1) calls isOdd n, which is structurally smaller.

lean
mutual
  def isEven : Nat → Bool
    | 0 => true
    | n + 1 => isOdd n
  def isOdd : Nat → Bool
    | 0 => false
    | n + 1 => isEven n
end
ComputationC

When termination is unknown: partial and fuel

Take a positive number; if it is even, halve it; if odd, triple it and add one; repeat until you reach 1. The Collatz conjecture says you always reach 1, whatever number you start from. It has been checked by computer for enormous ranges of numbers, but in 2026 it is still unproved. No termination proof exists for Lean to find, and Lean rightly rejects the plain definition, reporting that it cannot show 3 * n + 1 < n. Here are the two honest ways to write it anyway:

lean
/-- Nobody knows whether this terminates for every `n`: that is the Collatz conjecture. -/
partial def collatzSteps (n : Nat) : Nat :=
  if n ≤ 1 then 0
  else if n % 2 == 0 then 1 + collatzSteps (n / 2)
  else 1 + collatzSteps (3 * n + 1)

/-- The same, with a budget of `fuel` steps; `none` means the budget ran out. -/
def collatzFuel (fuel n : Nat) : Option Nat :=
  match fuel with
  | 0 => none
  | fuel + 1 =>
    if n ≤ 1 then some 0
    else
      let next := if n % 2 == 0 then n / 2 else 3 * n + 1
      (collatzFuel fuel next).map (· + 1)

def main : IO Unit := do
  IO.println s!"27 takes {collatzSteps 27} steps"
  IO.println s!"with 200 steps of fuel: {collatzFuel 200 27}"
  IO.println s!"with 100 steps of fuel: {collatzFuel 100 27}"
  let longest := (List.range 10000).foldl
    (fun best n => if collatzSteps n > collatzSteps best then n else best) 1
  IO.println s!"below 10000, {longest} takes longest: {collatzSteps longest} steps"
text
27 takes 111 steps
with 200 steps of fuel: (some 111)
with 100 steps of fuel: none
below 10000, 6171 takes longest: 261 steps

partial def tells Lean: compile this function and let me run it, but do not treat it as an equation. Lean then needs only to know that the result type has some value (here Nat does: 0), so that the function can be given a meaning for logic even if it loops. The price is that a partial function is opaque to proofs: you can run collatzSteps 27, but you cannot prove anything about what collatzSteps returns. Use partial for code you will never reason about formally, such as a main loop that reads commands until the user quits, and keep it out of anything you intend to verify.

Fuel keeps the function total by adding a counter that decreases on every call, so the recursion is structural on fuel. The result becomes an Option, and none honestly reports "I gave up". (Option.map (· + 1) adds one to the count inside a some and leaves none alone.) Fuel is common in interpreters and search procedures, and unlike partial it leaves the function fully available to proofs: you could prove, for instance, that more fuel never changes a some answer.

A third way is decreasing_by sorry, which claims a termination proof without giving one. Never ship it: sorry is an admitted gap in the logic, Lean prints a warning for every use, and Lumenary's tests reject any program containing one.

ExplanationH

Tail recursion and the stack

A recursive call that is the very last thing a function does is a tail call. Lean's compiler turns self tail calls into loops, which run in constant stack space. Calls that are not in tail position each need a stack frame, and on a long enough input they run out.

lean
def sumNaive : List Nat → Nat
  | [] => 0
  | x :: xs => x + sumNaive xs

def sumAcc (acc : Nat) : List Nat → Nat
  | [] => acc
  | x :: xs => sumAcc (acc + x) xs

def main : IO Unit := do
  let xs := List.range 1000000
  IO.println (sumAcc 0 xs)
  IO.println (xs.foldl (· + ·) 0)
  IO.println (sumNaive xs)
text
499999500000
499999500000
499999500000

In sumNaive, the addition happens after the recursive call returns, so a million calls are pending at once. sumAcc carries an accumulator: the running total travels down with the call, and the recursive call is the last thing that happens. List.foldl is the library's packaged version of the same pattern. With a million elements all three succeed. When we ran the same program on ten million elements, the first two lines printed as before, and sumNaive stopped with an error that begins deep recursion was detected.

Two remarks from practice. First, the standard library already does this work for you: List.map, List.foldr and ++ have simple recursive definitions for proofs, and the library contains proved theorems that each equals a tail-recursive implementation, marked with an attribute (@[csimp]) that makes the compiler use the fast version. This is a pattern worth admiring: write the clear version, prove the fast one equal, run the fast one. Lesson 9 shows how to prove such an equation yourself. Second, do not contort every function into accumulator style. Recursion over trees, whose depth is logarithmic when they are balanced, is perfectly safe, and so is recursion over short lists. Save the accumulator for loops over data that may be large.

Common misconceptionsH

Common misconceptions

Misconception

"Termination checking means Lean solves the halting problem." It does not: Lean only checks the argument you give, a structural pattern or a decreasing measure. Some functions terminate but are hard to prove so, and for those you must supply the proof, restructure the function, use fuel or mark it partial.

Misconception

"partial def is the easy way out, so use it whenever termination is annoying." It costs you every future proof about that function, and it is easy to forget that a partial function was never shown to terminate. Prefer a measure; look at the goal Lean shows you. Most failed termination proofs need one hypothesis or one library lemma.

Misconception

"The recursive definition in the library must be slow." Lean separates the definition used for reasoning from the code that runs, and links them with proved equations. List.map is defined recursively but compiled to a tail-recursive loop.

Misconception

"fibSlow and fib are the same function, so they cost the same." They have the same values, which you can prove, but completely different costs: exponential versus linear. Equality of functions in Lean is about what they compute, never how fast.

Exercises

Exercises

Use the definitions from the lesson, and check your answers with #eval.

1. Recursion and termination

Warm-upHuman

Why does Lean reject def bad (n : Nat) : Nat := bad n + 1, which Python would accept?

Choose one

2. Recursion and termination

Warm-upComputational

With fibPair and fib as in the lesson, what is fib 12?

3. Recursion and termination

CoreComputational

What does #eval digits 907 show, with digits from the lesson?

4. Recursion and termination

CoreComputational

Lean accepts this definition without any termination_by. What is halve 100?

def halve (n : Nat) : Nat := if n = 0 then 0 else 1 + halve (n / 2)

5. Recursion and termination

StretchComputational

The Collatz sequence from 6 is 6, 3, 10, 5, 16, 8, 4, 2, 1: eight steps. With collatzFuel from the lesson, what does #eval collatzFuel 8 6 show?

6. Recursion and termination

CoreHuman

A function scan (lo hi : Nat) does nothing if lo ≥ hi and otherwise calls scan (lo + 1) hi. Which termination_by measure works?

Choose one

7. Recursion and termination

StretchHuman

Which of these recursive calls are structural, so that Lean needs no measure for them? List their letters.

  • A: in a match on n + 1, a call on n
  • B: in a match on x :: xs, a call on xs
  • C: a call on n / 2 when n ≠ 0
  • D: in a match on node l k r, a call on l
  • E: a call on xs.drop 1
  • F: a call on a % b when b ≠ 0

Write elements separated by commas. Order and repeats don’t matter — just like in a set!

Further reading and resources