# 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

```zig
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:

```text
5
4
3
2
1
Done!
```

The function calls itself repeatedly:

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

The recursion stops at:

```zig
if (n == 0)
```

This is the base case.

## Why the Base Case Matters

Without a base case, recursion never stops.

Bad example:

```zig
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:

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

Also:

```text
5! = 5 × 4!
```

This naturally fits recursion.

Implementation:

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

    return n * factorial(n - 1);
}
```

Calling:

```zig
const result = factorial(5);
```

Result:

```text
120
```

## Understanding Recursive Execution

Let us expand:

```zig
factorial(5)
```

This becomes:

```text
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:

```text
factorial(0) = 1
```

Then execution unwinds:

```text
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:

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

Implementation:

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

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

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

Calling:

```zig
const result = fibonacci(10);
```

Result:

```text
55
```

## Recursive Tree Thinking

Recursion often creates a tree of calls.

For:

```zig
fibonacci(4)
```

the calls look like:

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

Notice repeated work:

```text
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:

```zig
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:

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

A linked list node points to another node.

Trees are also recursive.

Example:

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

Recursive functions are natural for recursive structures.

## Recursive Tree Traversal

Example conceptual traversal:

```zig
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:

```text
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:

```zig
fn recurse() void {
    recurse();
}
```

Eventually:

```text
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:

```zig
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:

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

    return n * factorial(n - 1);
}
```

Iterative factorial:

```zig
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:

```zig
fn parseExpression() void {
    parseTerm();
}
```

Then:

```zig
fn parseTerm() void {
    parseFactor();
}
```

This style is called recursive descent parsing.

It is extremely common in language tooling.

## A Complete Example

```zig
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:

```text
15
```

Execution:

```text
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:

```text
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.