Return Values & Recursion

The return statement allows a function to produce a value and immediately exit, no matter how deeply nested the current execution point is.

Return Statements

fun square(x) {
    return x * x;
}
print square(5);   // outputs: 25

A function without a return (or with a bare return;) returns nil:

fun doStuff() {
    print "done";
}
print doStuff();   // outputs: done, then nil

Implementation Challenge

return must immediately unwind execution from wherever it is — even inside nested blocks, loops, or if statements. In a tree-walk interpreter, the simplest approach is using an exception-like mechanism:

class ReturnValue(Exception):
    def __init__(self, value):
        self.value = value

def executeReturn(stmt):
    value = evaluate(stmt.value) if stmt.value else nil
    raise ReturnValue(value)

def callFunction(fn, args):
    try:
        executeBlock(fn.body, env)
    except ReturnValue as r:
        return r.value
    return nil

This is the approach Crafting Interpreters uses. It is a clever use of the host language's exception system for control flow. In a bytecode VM, we will handle returns more efficiently with a call stack.

Recursion

Functions can call themselves. This enables elegant solutions to problems with self-similar structure:

fun fib(n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}
print fib(10);   // outputs: 55

Each recursive call creates a new environment with its own copy of n. The call stack grows with each call and shrinks as functions return.

Stack Overflow

Deep recursion can exhaust the call stack. fib(10000) would create 10,000+ nested environments. Most languages limit stack depth — Python defaults to 1,000 frames. Our interpreter inherits whatever limit the host language imposes.

Tail call optimization (TCO) can prevent stack overflow for tail-recursive functions. Lua guarantees TCO, and JavaScript specifies it (though only Safari implements it). We will not implement TCO, but it is worth knowing about.

Your Task

Implement the return statement using an exception-like mechanism. Verify that recursion works correctly by testing with fibonacci, factorial, and other recursive functions.