A First Example

Recursion

Recursion is a technique where a function calls itself.

Instead of solving a problem all at once, the function solves a smaller version of the same problem repeatedly.

A recursive function usually has two parts:

a base case
a recursive case

The base case stops the recursion.

The recursive case calls the function again with a smaller problem.

A First Example

const std = @import("std");

fn countdown(n: u32) void {
    if (n == 0) {
        std.debug.print("Done!\n", .{});
        return;
    }

    std.debug.print("{}\n", .{n});

    countdown(n - 1);
}

pub fn main() void {
    countdown(5);
}

Output:

5
4
3
2
1
Done!

The function calls itself repeatedly:

countdown(5)
countdown(4)
countdown(3)
countdown(2)
countdown(1)
countdown(0)

The recursion stops at:

if (n == 0)

This is the base case.

Why the Base Case Matters

Without a base case, recursion never stops.

Bad example:

fn broken() void {
    broken();
}

This causes infinite recursion.

The program keeps creating function calls until the stack overflows.

Eventually the program crashes.

Every recursive function must move toward a stopping condition.

Recursive Factorial

A classic recursion example is factorial.

Mathematically:

5! = 5 × 4 × 3 × 2 × 1

Also:

5! = 5 × 4!

This naturally fits recursion.

Implementation:

fn factorial(n: u32) u32 {
    if (n == 0) {
        return 1;
    }

    return n * factorial(n - 1);
}

Calling:

const result = factorial(5);

Result:

Understanding Recursive Execution

Let us expand:

factorial(5)

This becomes:

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)))))

Base case:

factorial(0) = 1

Then execution unwinds:

1 * 1 = 1
2 * 1 = 2
3 * 2 = 6
4 * 6 = 24
5 * 24 = 120

This “unwinding” process is very important in recursion.

Recursive Fibonacci

Another classic example is Fibonacci numbers.

Definition:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

Implementation:

fn fibonacci(n: u32) u32 {
    if (n == 0) {
        return 0;
    }

    if (n == 1) {
        return 1;
    }

    return fibonacci(n - 1) + fibonacci(n - 2);
}

Calling:

const result = fibonacci(10);

Result:

Recursive Tree Thinking

Recursion often creates a tree of calls.

For:

fibonacci(4)

the calls look like:

fibonacci(4)
├── fibonacci(3)
│   ├── fibonacci(2)
│   │   ├── fibonacci(1)
│   │   └── fibonacci(0)
│   └── fibonacci(1)
└── fibonacci(2)
    ├── fibonacci(1)
    └── fibonacci(0)

Notice repeated work:

fibonacci(2)

is computed multiple times.

This makes naive Fibonacci recursion slow.

Recursive Directory Traversal

Recursion is common in file systems.

Folders contain folders.

A recursive algorithm naturally matches this structure.

Conceptually:

fn visitDirectory(path: []const u8) void {
    // process files

    // recursively visit subdirectories
}

The function processes one directory, then recursively processes children.

Recursive Data Structures

Some data structures are recursive themselves.

Example:

const Node = struct {
    value: i32,
    next: ?*Node,
};

A linked list node points to another node.

Trees are also recursive.

Example:

const TreeNode = struct {
    value: i32,
    left: ?*TreeNode,
    right: ?*TreeNode,
};

Recursive functions are natural for recursive structures.

Recursive Tree Traversal

Example conceptual traversal:

fn visit(node: ?*TreeNode) void {
    if (node == null) {
        return;
    }

    visit(node.?.left);

    // process node

    visit(node.?.right);
}

This pattern appears everywhere in compilers, parsers, databases, and game engines.

Stack Frames

Every function call creates a stack frame.

A stack frame stores:

local variables
parameters
return information

Recursive calls create many stack frames.

Example:

factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)
factorial(0)

Each call consumes stack memory.

Too many recursive calls can overflow the stack.

Stack Overflow

Dangerous recursion:

fn recurse() void {
    recurse();
}

Eventually:

stack overflow

This is why recursive algorithms must reduce the problem size.

Tail Recursion

Tail recursion happens when the recursive call is the final operation.

Example:

fn countdown(n: u32) void {
    if (n == 0) {
        return;
    }

    return countdown(n - 1);
}

Some compilers optimize this into loops.

This is called tail-call optimization.

Whether optimization occurs depends on compiler behavior and circumstances.

Recursion vs Loops

Many recursive algorithms can also be written with loops.

Recursive factorial:

fn factorial(n: u32) u32 {
    if (n == 0) {
        return 1;
    }

    return n * factorial(n - 1);
}

Iterative factorial:

fn factorialIterative(n: u32) u32 {
    var result: u32 = 1;
    var i: u32 = 1;

    while (i <= n) : (i += 1) {
        result *= i;
    }

    return result;
}

Both compute the same result.

Loops are often more memory-efficient.

Recursion is often more elegant for tree-like problems.

When Recursion Is Useful

Recursion works especially well for:

trees
graphs
parsers
file systems
divide-and-conquer algorithms
mathematical definitions

Examples:

quicksort
mergesort
expression parsing
JSON traversal
AST walking
game search algorithms

When Recursion Is Dangerous

Recursion can become problematic when:

recursion depth becomes very large
stack usage becomes excessive
repeated work makes algorithms slow
termination conditions are unclear

Naive Fibonacci is a classic inefficient recursion example.

Recursive Parsing

Compilers frequently use recursion.

Expression grammars naturally become recursive functions.

Conceptual parser:

fn parseExpression() void {
    parseTerm();
}

Then:

fn parseTerm() void {
    parseFactor();
}

This style is called recursive descent parsing.

It is extremely common in language tooling.

A Complete Example

const std = @import("std");

fn sum(values: []const i32) i32 {
    if (values.len == 0) {
        return 0;
    }

    return values[0] + sum(values[1..]);
}

pub fn main() void {
    const numbers = [_]i32{ 1, 2, 3, 4, 5 };

    const result = sum(&numbers);

    std.debug.print("{}\n", .{result});
}

Output:

Execution:

1 + sum([2,3,4,5])
2 + sum([3,4,5])
3 + sum([4,5])
4 + sum([5])
5 + sum([])
0

Then the results combine while unwinding.

Mental Model

Recursion means:

solve a problem using smaller versions of the same problem

A recursive function repeatedly reduces the problem until reaching a simple stopping case.

The essential ingredients are:

Part	Purpose
Base case	stops recursion
Recursive case	reduces the problem
Progress	moves toward termination

Without all three, recursion fails.

Recursion is one of the most important ideas in computer science because many real-world structures are naturally recursive.