Dennis O'Keeffe

Tail Recursion

Understand what tail recursion with this visual aide and example in Zig.

5 min read

On this page

What is Tail Recursion?

Tail recursion is a memory-optimization technique (using tail call optimization) for the call stack.

Instead of piling on more data onto the stack data structure for recursive calls, tail recursion enables the optimization to deallocate the previous function call's memory prior to making the recursive call.

Not all languages support tail call optimization. Almost all functional languages support it, some systems languages support it, but a number of popular languages such as Python and Ruby do not support it. It's still worth knowing about.

How Can I Visualize Tail Recursion?

Think of a stack of plates.

Stack of plates
Stack of plates

Each plate in the stack represents in a recursive call that is not tail call optimized.

Given enough recursive calls, the stack will build up enough, run out of space and cause a stack overflow that will crash the system.

In the case of tail recursion, you can think of this as one plate being added to the stack, but once it finishes it's run and makes a recursive call, the current "plate" is removed from the stack before the next "plate" is added.

You can think of this as a plate stack with one plate being added and removed for each recursive iteration.

One plate
One plate

This analogy helps to visualize the lifecycle of a call stack and how that data structure works. Regardless of tail recursion, each time you are adding and removing from the stack it is like a stack of plates where you add and remove from the top.

An Example of Tail Recursion

I will make use of Zig to compare an approach with and without tail call optimization being used.

const std = @import("std");
const print = std.debug.print;

// Get approximate stack pointer to measure stack usage
fn getStackPointer() usize {
    var dummy: u8 = 0;
    return @intFromPtr(&dummy);
}

fn measureMaxStackUsage() void {
    var max_stack_used: i64 = 0;
    const initial_sp = getStackPointer();

    const result = tailRecursiveWithMeasurement(1000, 1, initial_sp, &max_stack_used);

    print("=== Maximum Stack Usage Test ===\n", .{});
    print("Result: {}\n", .{result});
    print("Maximum stack used during recursion: {} bytes\n", .{max_stack_used});
}

// Separate function that tracks max usage
fn tailRecursiveWithMeasurement(n: u64, acc: u64, initial: usize, max_used: *i64) u64 {
    const current_sp = getStackPointer();
    const used = @as(i64, @intCast(initial)) - @as(i64, @intCast(current_sp));
    if (used > max_used.*) {
        max_used.* = used;
    }

    // Print occasionally to show progress
    if (n % 100 == 0) {
        print("  n={}, current stack: {} bytes, max so far: {} bytes\n", .{ n, used, max_used.* });
    }

    if (n <= 1) return acc;
    return @call(.always_tail, tailRecursiveWithMeasurement, .{ n - 1, acc + n, initial, max_used });
}

fn compareStackUsage() void {
    var tail_max: i64 = 0;
    var regular_max: i64 = 0;
    const initial_sp = getStackPointer();

    print("Testing tail recursion (1000 calls)...\n", .{});
    _ = tailRecursiveWithMeasurement(1000, 0, initial_sp, &tail_max);

    print("\nTesting regular recursion (20 calls)...\n", .{});
    _ = regularRecursiveWithMeasurement(20, initial_sp, &regular_max);

    print("\n📊 RESULTS:\n", .{});
    print("Tail recursion (1000 calls):    {} bytes max\n", .{tail_max});
    print("Regular recursion (20 calls):   {} bytes max\n", .{regular_max});
    print("Bytes per call - Tail:          {:.1} bytes\n", .{@as(f64, @floatFromInt(tail_max)) / 1000.0});
    print("Bytes per call - Regular:       {:.1} bytes\n", .{@as(f64, @floatFromInt(regular_max)) / 20.0});
}

fn regularRecursiveWithMeasurement(n: u64, initial: usize, max_used: *i64) u64 {
    const current_sp = getStackPointer();
    const used = @as(i64, @intCast(initial)) - @as(i64, @intCast(current_sp));
    if (used > max_used.*) {
        max_used.* = used;
    }

    // Print occasionally to show usage
    if (n % 10 == 0) {
        print("  n={}, current stack: {} bytes, max so far: {} bytes\n", .{ n, used, max_used.* });
    }

    if (n <= 1) return 1;
    return 1 + regularRecursiveWithMeasurement(n - 1, initial, max_used);
}

pub fn main() !void {
    print("\n=== Stack Usage Comparison ===\n", .{});
    compareStackUsage();
}

Running this code results in the following:

$ zig run -O ReleaseFast tail_recursion.zig

=== Stack Usage Comparison ===
Testing tail recursion (1000 calls)...
  n=1000, current stack: -72 bytes, max so far: 0 bytes
  n=900, current stack: -72 bytes, max so far: 0 bytes
  n=800, current stack: -72 bytes, max so far: 0 bytes
  n=700, current stack: -72 bytes, max so far: 0 bytes
  n=600, current stack: -72 bytes, max so far: 0 bytes
  n=500, current stack: -72 bytes, max so far: 0 bytes
  n=400, current stack: -72 bytes, max so far: 0 bytes
  n=300, current stack: -72 bytes, max so far: 0 bytes
  n=200, current stack: -72 bytes, max so far: 0 bytes
  n=100, current stack: -72 bytes, max so far: 0 bytes

Testing regular recursion (20 calls)...
  n=20, current stack: 57 bytes, max so far: 57 bytes
  n=10, current stack: 857 bytes, max so far: 857 bytes

📊 RESULTS:
Tail recursion (1000 calls):    0 bytes max
Regular recursion (20 calls):   1577 bytes max
Bytes per call - Tail:          0.0e0 bytes
Bytes per call - Regular:       7.9e1 bytes

The -72 bytes for the tail recursion is a bit of noise, but you can see in the difference here that 20 calls with regular recursion used up around 8 bytes for invocation, while the tail recursion resulted in no memory buildup.

Photo credit: nervum