Recursion

Recursion in Goose is opt-in. A function that is part of a recursive cycle must be declared recursive fn, as Chapter 5 showed, and recursive code lives under one extra rule. This chapter explains that rule, why the memory model needs it, and the three patterns that make recursive code easy to write within it.

#The rule17.1

No function in a recursive cycle may call back into the cycle while one of its non-fixed locals is in scope.

In other words, a recursive function can own scalars, structs, fixed arrays, references and slices across its recursive calls. It cannot keep a growable array, a string builder, or any other variable-size or resizable value alive across one.

Here is the rule being broken:

recursive fn count_down(n: i64) {
    var trail: u8[>..] = [];
    format(trail, "at ", n);
    if n > 0 { count_down(n - 1); }
    print(trail);
}

fn main() { count_down(2); }

error: count_down calls into its recursive cycle while non-fixed-size local trail (declared at main.goose:2) is in scope (§7.8): end its scope before the call

#Why17.1.1

Remember the rule from Chapter 6: a growable value is always the topmost thing on its data stack, so that it can grow without moving. Each call of count_down creates a new trail. The compiler works out the number of data stacks at compile time, so the program has a fixed number of them. If every level of the recursion kept its own trail alive, each new trail would land on top of the previous one, and the previous one could no longer grow:

With the rule in place, each level of recursion costs only native stack space, which is the same as in C. A recursion that runs too deep stops the program with a clean error rather than corrupting anything:

recursive fn depth(n: i64) -> i64 { if n == 0 { 0 } else { 1 + depth(n - 1) } }

fn main() { print(depth(100000000)); }

goose runtime error: native call stack overflow

The compiler's message already suggests the first way to live with the rule.

#Pattern 1: finish with the scratch before recursing17.2

A recursive function may own growable data, as long as its scope ends before the recursive call. Wrapping the scratch work in a block is often all it takes:

recursive fn count_down(n: i64) {
    {
        var trail: u8[>..] = [];
        format(trail, "at ", n);
        print(trail);
    }                                  // trail is gone before the call
    if n > 0 { count_down(n - 1); }
}

fn main() { count_down(2); }

at 2
at 1
at 0

The same rule applies to temporaries in the calling statement. You cannot pass str(…) straight into a recursive call, because the new string would be alive during the call:

recursive fn echo(s: u8[:], n: i64) {
    print(s);
    if n > 0 { echo(str("level ", n), n - 1); }
}

fn main() { echo("start", 2); }

error: echo calls into its recursive cycle with the non-fixed-size temporary str("level ", n) as an argument (§7.8): pass it in from outside the cycle

#Pattern 2: pass the output in17.3

Most recursive functions that build something can build it into an array that belongs to their caller. The array is owned outside the cycle, so it is not affected by the rule, and every level of the recursion pushes into the same array:

recursive fn hanoi(n: i64, from: u8, to: u8, via: u8, moves: u8[>..]&) {
    if n == 0 { return; }
    hanoi(n - 1, from, via, to, moves);
    moves.push(from);
    moves.push('>');
    moves.push(to);
    moves.push(' ');
    hanoi(n - 1, via, to, from, moves);
}

fn main() {
    var moves: u8[>..] = [];
    hanoi(3, 'A', 'C', 'B', moves);
    print(moves);
}

A>C A>B C>B A>C B>A B>C A>C

You already saw this shape in Chapter 13, where in_order walked a tree and wrote names into a builder it was given.

#Pattern 3: a context of references17.4

A larger recursive algorithm, such as a parser or a compiler pass, often works on several tables at once: the input, a list of nodes, an output buffer. Make each table a local of a non-recursive driver function, and hand the recursion a single struct of references to them. A struct of references is fixed-size, so the recursion may hold it across its calls:

struct Place { name: u8[..8], inside: i64[..4] }
struct Ctx { places: Place[>..]&, out: u8[>..]& }

recursive fn draw(c: Ctx&, i: i64, depth: i64) {
    for d in depth { c.out.append("  "); }
    format(c.out, c.places[i].name, "\n");
    for k in c.places[i].inside { draw(c, k, depth + 1); }
}

fn main() {
    var places: Place[>..] = [];
    for n in ["farm", "pond", "barn", "Ada", "Bea"] { places.push(Place { name: n, inside: [] }); }
    places[0].inside.push(1);
    places[0].inside.push(2);
    places[1].inside.push(3);
    places[2].inside.push(4);
    var out: u8[>..] = [];
    var c = Ctx { places: places, out: out };
    draw(c, 0, 0);
    print(out);
}

farm
  pond
    Ada
  barn
    Bea

There is a variant of this pattern that needs no struct at all: declare the recursive functions as nested functions inside the driver, where they can reach the driver's tables as free variables. The calculator in Chapter 25 is written that way.

#Sharing a scratch stack17.4.1

Sometimes each level of a recursion needs scratch space of its own that lives across its recursive calls. Give the whole recursion one grow-shrink array, owned outside the cycle. Each activation records where the stack top was, pushes its own entries, and truncates back before it returns:

recursive fn depth_sum(scratch: i64[>..<]&, depth: i64) -> i64 {
    let mark = scratch.len;
    scratch.push(depth * 10);             // this level's own entries
    let mine = scratch[mark..];
    var total = mine[0];
    if depth < 3 { total += depth_sum(scratch, depth + 1); }
    scratch.resize(mark);                 // gone again before returning
    return total;
}

fn main() {
    var scratch: i64[>..<] = [];
    print(depth_sum(scratch, 0), " ", scratch.len);
}

60 0

Note that mine, a slice into scratch, is used after the recursive call. That is normally forbidden, because scratch can shrink. It is allowed here because the compiler sees that the recursive call is balanced: it leaves the array at least as long as it found it, so nothing below mark is ever freed during the call.

#Mutual recursion17.5

When several functions call each other, only the entry of the cycle, the function the outside world calls first, needs recursive. Every function in the cycle must have fully written-out parameter and result types, because the compiler cannot infer types around a loop:

recursive fn is_even(n: i64) -> bool { if n == 0 { true } else { is_odd(n - 1) } }
fn is_odd(n: i64) -> bool { if n == 0 { false } else { is_even(n - 1) } }

fn main() { print(is_even(10), " ", is_odd(7)); }

true true

recursive fn is_even(n: i64) -> bool { if n == 0 { true } else { is_odd(n - 1) } }
fn is_odd(n) { if n == 0 { false } else { is_even(n - 1) } }

fn main() { print(is_even(10)); }

error: function is_odd is in a recursive cycle and needs fully explicit parameter types

#Design note: why recursion is marked17.6

Most languages let any function call itself without ceremony, and so does Goose's type checker in principle. The keyword is there for the memory model. The compiler sizes the data stacks by walking the call graph, and a cycle in that graph would make the walk unbounded, unless the functions in the cycle are known not to hold any stack across their recursive calls. Marking the entry of each cycle makes the cycles explicit, both to the compiler and to the reader, and it is the place where the compiler checks the rule. It also tells the person reading the code that this is where the native stack can grow without bound.

#Exercises17.7

1. Write a recursive fn binary(n: i64, out: u8[>..]&) that appends the binary digits of a non-negative number, most significant first.

2. Write a recursive function that sums an i64[:] by splitting it in half, summing each half, and adding the results. Is the slice a problem for the rule? Why or why not?

3. Change draw so that it also prints how many places each place contains in total, including nested ones. Where does the count come from?