Recursion and iterators

Structural recursion

A function may call itself only on a part of a value it received:

# Structural recursion: each call works on a smaller part of the tree.
kind Tree
    Leaf(v: i64)
    Node(l: Box[Tree], r: Box[Tree])

fn tree_sum(t: &Tree) -> i64
    match t
        Leaf(v: v) -> return v
        Node(l: l, r: r) -> return tree_sum(l) + tree_sum(r)

fn sample() -> i64
    let t = Node(l: Box(Leaf(v: 2)), r: Box(Node(l: Box(Leaf(v: 3)), r: Box(Leaf(v: 4)))))
    return tree_sum(&t)

check sample() == 9

tree_sum calls itself on l and r, which are fields of the Node it matched. Each call gets a smaller tree, so the recursion has to stop. Box[Tree] is needed because a Tree that contains a Tree directly would have no fixed size.

Recursion that does not shrink its input is refused, even when it would in fact stop:

fn countdown(n: u64) -> u64
    if n == 0
        return 0
    return countdown(n - 1)

$ rce check countdown.rce
REFUSED countdown.rce: line 4: W-REC-1 recursion through countdown has no decreasing measure (6.7): no layers of summed measures, each kept by every call not yet done and shrunk by at least one, leave the remaining calls without a cycle, and a cycle of its calls passes through no function declared with `bound`
exit status: 1

Write countdown as a loop instead. Two functions that call each other are refused for the same reason. This rule is part of how RCE keeps its promise that every step finishes.

Iterators

A function whose return type is iter T produces values one at a time with yield:

fn evens(n: u64) -> iter u64
    var i: u64 = 0
    while i < n
        yield i * 2
        i += 1

fn total(n: u64) -> u64
    var s: u64 = 0
    for x in evens(n)
        s += x
    return s

check total(4) == 12
check evens(3).collect() == [0, 2, 4]

A for loop takes the values as they are produced. collect() gathers them into a list. Each yield counts against the loop limit from chapter 3, so an iterator cannot run forever either.

What you learned

• Recursion is allowed on parts of a matched value (rule W-REC-1).
• iter T functions with yield, consumed by for or collect().