Gleam Recursion

Gleam has no while or for loops. Repetition comes from recursion — a function that calls itself with a smaller or simpler version of its input until it reaches a base case. Recursion in Gleam is not an edge case; it is the standard way to process repeated data.

The Anatomy of a Recursive Function

Every recursive function needs two parts:

Recursive Function Structure
──────────────────────────────────────────────────
1. Base case  → when to STOP recursing
2. Recursive case → call self with a smaller input

pub fn countdown(n: Int) -> Nil {
  case n {
    0 -> io.println("Go!")          // base case — stop here
    _ -> {
      io.println(int.to_string(n))  // do something
      countdown(n - 1)              // recursive call — smaller n
    }
  }
}

// countdown(3) prints: 3  2  1  Go!

Call Stack Diagram
──────────────────────────────────────────────────
countdown(3)
  print "3"
  └── countdown(2)
        print "2"
        └── countdown(1)
              print "1"
              └── countdown(0)
                    print "Go!"  ← base case reached

Factorial — Classic Recursion

pub fn factorial(n: Int) -> Int {
  case n {
    0 -> 1             // base case: 0! = 1
    _ -> n * factorial(n - 1)
  }
}

// factorial(5) = 5 × 4 × 3 × 2 × 1 = 120

Factorial Expansion
──────────────────────────────────────────────────
factorial(5)
= 5 × factorial(4)
= 5 × 4 × factorial(3)
= 5 × 4 × 3 × factorial(2)
= 5 × 4 × 3 × 2 × factorial(1)
= 5 × 4 × 3 × 2 × 1 × factorial(0)
= 5 × 4 × 3 × 2 × 1 × 1
= 120

List Recursion

Lists are naturally recursive — they are either empty or a head element plus a tail list:

pub fn my_length(list: List(a)) -> Int {
  case list {
    []           -> 0
    [_, ..rest]  -> 1 + my_length(rest)
  }
}

pub fn my_sum(numbers: List(Int)) -> Int {
  case numbers {
    []           -> 0
    [head, ..tail] -> head + my_sum(tail)
  }
}

my_sum([1, 2, 3])
──────────────────────────────────────────────────
my_sum([1, 2, 3])
= 1 + my_sum([2, 3])
= 1 + 2 + my_sum([3])
= 1 + 2 + 3 + my_sum([])
= 1 + 2 + 3 + 0
= 6

Tail Call Optimization

Deep recursion can overflow the call stack — each call adds a frame and memory is finite. Tail call optimization (TCO) eliminates this problem. A tail-recursive function makes its recursive call as the very last action, with no pending work afterward.

Regular recursion — stack grows:
──────────────────────────────────────────────────
factorial(5)
= 5 × factorial(4)      ← must wait for factorial(4)
= 5 × (4 × factorial(3)) ← stack grows deeper

Tail-recursive — stack stays flat:
──────────────────────────────────────────────────
factorial_tail(5, 1)
  → factorial_tail(4, 5)    acc = 5×1
  → factorial_tail(3, 20)   acc = 5×4
  → factorial_tail(2, 60)   acc = 5×4×3
  → factorial_tail(1, 120)  acc = 5×4×3×2
  → factorial_tail(0, 120)  → 120

pub fn factorial_tail(n: Int, acc: Int) -> Int {
  case n {
    0 -> acc
    _ -> factorial_tail(n - 1, n * acc)
  }
}

// factorial_tail(5, 1) = 120

The Gleam compiler and BEAM both optimize tail calls. A tail-recursive function runs in constant stack space — safe for any input size.

Accumulator Pattern

Tail-recursive list processing uses an accumulator that builds the result as it goes:

pub fn reverse_list(list: List(a)) -> List(a) {
  do_reverse(list, [])
}

fn do_reverse(list: List(a), acc: List(a)) -> List(a) {
  case list {
    []           -> acc
    [head, ..tail] -> do_reverse(tail, [head, ..acc])
  }
}

Reverse [1, 2, 3] Step by Step
──────────────────────────────────────────────────
do_reverse([1, 2, 3], [])
do_reverse([2, 3], [1])
do_reverse([3], [2, 1])
do_reverse([], [3, 2, 1])
→ [3, 2, 1]

Mutual Recursion

Two functions can call each other — this is mutual recursion:

pub fn is_even(n: Int) -> Bool {
  case n {
    0 -> True
    _ -> is_odd(n - 1)
  }
}

pub fn is_odd(n: Int) -> Bool {
  case n {
    0 -> False
    _ -> is_even(n - 1)
  }
}

// is_even(4) → is_odd(3) → is_even(2) → is_odd(1) → is_even(0) → True

Practical Example — Fibonacci

pub fn fib(n: Int) -> Int {
  fib_tail(n, 0, 1)
}

fn fib_tail(n: Int, a: Int, b: Int) -> Int {
  case n {
    0 -> a
    _ -> fib_tail(n - 1, b, a + b)
  }
}

// fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(7)=13

Fibonacci Sequence
──────────────────────────────────────────────────
n:   0  1  2  3  4  5  6   7   8
fib: 0  1  1  2  3  5  8  13  21

Each number = sum of the previous two.

Key Points

Recursion Essentials
──────────────────────────────────────────────────
1. Every recursive function needs a base case
2. Recursive case must move toward the base case
3. Tail recursion — recursive call is the last action
4. Use accumulator pattern for tail-recursive list ops
5. BEAM optimizes tail calls — no stack overflow
6. prefer list module functions (map/filter/fold) for
   simple list processing — they are already optimized
7. Write custom recursion for complex or tree structures

Recursion replaces loops in Gleam. Once you internalize the base-case / recursive-case pattern, reading and writing recursive functions feels as natural as reading a recipe: "if the ingredient list is empty, you're done; otherwise, use the first ingredient and repeat with the rest."