🎓 A1Learner
🔍
0 of 55 lessons completed

Zig Recursion

Recursion is when a function calls itself to solve a smaller piece of the same problem. Each call works on a smaller input until the problem is small enough to answer directly.

Count down with self-calls

Countdown prints its number, then calls itself with one less. The call with 0 is the base case, so it returns at once.

const std = @import("std");

fn countdown(n: i32) !void {
    if (n == 0) return;
    const out = std.io.getStdOut().writer();
    try out.print("{d}\n", .{n});
    try countdown(n - 1);
}

pub fn main() !void {
    try countdown(3);
}

Add the numbers down to zero

SumTo adds its number to the sum of all smaller numbers. The base case, zero, adds nothing.

const std = @import("std");

fn sumTo(n: i32) i32 {
    if (n == 0) return 0;
    return n + sumTo(n - 1);
}

pub fn main() !void {
    const out = std.io.getStdOut().writer();
    try out.print("{d}\n", .{sumTo(4)});
}

Multiply down to one

A factorial multiplies a number by every smaller whole number. Factorial of 5 works out step by step as the calls return.

const std = @import("std");

fn factorial(n: i32) i32 {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

pub fn main() !void {
    const out = std.io.getStdOut().writer();
    try out.print("{d}\n", .{factorial(5)});
}

Example

const std = @import("std");

fn power(base: i32, exp: i32) i32 {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

pub fn main() !void {
    const out = std.io.getStdOut().writer();
    try out.print("{d} {d}\n", .{ power(2, 5), power(3, 3) });
}

Key points

  • Recursion: a function calling itself inside its own body.
  • Base case: the condition that stops the calls and returns an answer directly.
  • Recursive case: the part where the function calls itself on a smaller input.
  • Smaller input: every call must move closer to the base case, or the calls never stop.
  • Combining: as each call returns, its result joins the work of the call before it.

In this example, power multiplies base by itself exp times by calling itself with exp one smaller each time. An exponent of 0 is the base case and returns 1. So power(2, 5) returns 32 and power(3, 3) returns 27.

Note

recursion needs no special Zig syntax, because a self-call is an ordinary function call.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

What is the base case in a recursive function?