Recursive functions

We'll study functions in much more detail in the dedicated chapter. Here, I just want to talk about one specific concept: functions that call themselves again.

These consecutive calls solve problems progressively and are made by changing one of the parameters, because if nothing changes between calls, you'll fall into infinite recursion. In the following example, we consider a player under a burst of consecutive attacks from multiple enemies.

Before even thinking about the character’s defense, we need to know how much total damage they would take from that combined action.

recursive_damage.zig

const std = @import("std");

const print = std.debug.print;

fn dmg_accumulation(z_x: []const u8, n_acc: u16) u16 {

print("\nCurrent sum: {}, Incoming attacks: {any}", .{n_acc, z_x});

return if (z_x.len > 0)

dmg_accumulation(z_x[1..], n_acc + z_x[0])

else

n_acc;

}

pub fn main() void {

// series of attacks on the player

const a_attacks = [_]u8{

1, 3, 11,

4, 5,

};

const n_total_damage = dmg_accumulation(a_attacks[0..], 0);

print("\nTotal damage: {}\n", .{n_total_damage});

}

$ zig run recursive_damage.zig

Current sum: 0, Incoming attacks: { 1, 3, 11, 4, 5 }

Current sum: 1, Incoming attacks: { 3, 11, 4, 5 }

Current sum: 4, Incoming attacks: { 11, 4, 5 }

Current sum: 15, Incoming attacks: { 4, 5 }

Current sum: 19, Incoming attacks: { 5 }

Current sum: 24, Incoming attacks: { }

Total damage: 24

The function dmg_accumulation receives the following parameters:

z_x - a slice representing the remaining attacks to process,
n_acc - an accumulator (a number holding the running sum) of the total damage we’ve been accumulating in each call.

In the first call:

dmg_accumulation(a_attacks[0..], 0);

The slice z_x contains all positions of the attack array, and n_acc is 0, which is the initial value before any sum is done. This is what we call the “initial state”.

To solve a problem using recursion, we divide it into two parts:

The base case, and
The recursive case.

The base case is the smallest problem we know how to solve, and that stops the recursion. In our case, the smallest problem happens when there are no more elements left in the slice z_x: we don't add anything else and return the accumulator n_acc:

return n_acc;

The recursive case is when there are still elements left to process, and we divide the problem into smaller subproblems. We add the value of the first element to the accumulator and return the result of calling the function again with the remaining elements and the new accumulator:

n_acc += z_slice[0] ;

return dmg_accumulation(z_slice[1..], n_acc);

This way of solving problems using recursion is something some people remember best as the classic “divide and conquer”.

Tail recursion

In the recursive_damage.zig example, each time the function calls itself, the parameters it sends are not the same as the ones it received. We can visualize the slice as being made of two parts: the “head” (the first element) and the “tail” (the rest).

The first parameter is a slice z_x without the “head”: z_x[1..] - that’s the “tail”.
The second parameter is the current value of n_acc plus the first element of z_x: n_acc + z_x[0].

If there are no more values left in z_x, the function ends by returning the accumulator:

else

n_acc;

This pattern, called Tail Recursion, is very common in functional programming.

As you can see, instead of keeping a variable mutating inside a loop, as we'll soon see with for and while loops, here we pass the state (n_acc, the accumulator) in each call. Notice that both z_x and n_acc are constants. In each call, we create a new state that isn’t mutable, and finally return the accumulated result as the function’s output.

Non-tail recursion

As we just saw, in Tail Recursion, we first add the “head” to the accumulator and pass the “tail” and the updated accumulator to the next call.

In a non-tail recursion, in the base case - when there are no more elements to process - we return 0 (not the accumulator), and in the recursive case, we return the “head” added to the recursive call with the tail.

In this case, the recursive call is not the last thing done. In each call, the function has to wait for the next call to finish before performing the sum with its result. This kind of recursion cannot be optimized - it needs to maintain a call stack.

To visualize how it works, here's an example:

recursive_no_tail.zig

const std = @import("std");

const print = std.debug.print;

fn dmg_accumulation_ntc(z_x: []const u8) u16 {

if (z_x.len == 0) {

print("\nFinal case: we return 0\n", .{});

return 0;

}

print("\nRecursive case: we return {} + recursion({any}) \n", .{ z_x[0], z_x[1..] });

return z_x[0] + dmg_accumulation_ntc(z_x[1..]);

}

pub fn main() void {

// series of attacks on the player

const a_attacks = [_]u8{

1, 3, 11,

4, 5,

};

const n_total_damage = dmg_accumulation_ntc(a_attacks[0..]);

print("\nTotal damage: {}\n", .{n_total_damage});

}

$ zig run recursive_no_tail.zig

Recursive case: we return 1 + recursion({ 3, 11, 4, 5 })

Recursive case: we return 3 + recursion({ 11, 4, 5 })

Recursive case: we return 11 + recursion({ 4, 5 })

Recursive case: we return 4 + recursion({ 5 })

Recursive case: we return 5 + recursion({ })

Final case: we return 0

Total damage: 24

For this reason, if you come across a similar case and decide to solve it with recursive functions, always try to use tail recursion: it's more efficient and even easier to transform into a loop if needed.

Infinite recursive function

A recursive function makes a copy of itself in memory every time a call is made. If there are too many of these calls, or worse, there’s no condition to stop the loop, we end up overflowing the memory space that the operating system has reserved for our program, as in the following example:

recursive_infinite.zig

// const std = @import("std");

// const print = std.debug.print;

fn infinite_loop() void {

infinite_loop();

}

pub fn main() void {

infinite_loop();

}

$ zig run recursive_infinite.zig

Segmentation fault (core dumped)

As you can see, if there's no condition to stop the recursion, the infinite_loop function keeps calling itself over and over, with no limit. Since each call takes up a small amount of space on the execution stack, after thousands of calls, that space runs out, and the operating system kills the process, showing a Segmentation fault message. This type of error usually occurs when the program attempts to access a memory area it doesn’t have permission to access.

Remember how we triggered this error, because we’re about to see something interesting next.

But first, if you want to practice, try adding an exit condition to the infinite_loop function in the recursive_infinite.zig code.