Chapter 13: Calling Yourself

This chapter is optional. Nothing in the rest of this book, including the finished game in chapter 14, depends on anything here. If recursion doesn't click for you today, skip ahead and come back later, your project will be waiting exactly where you left it.

A Function That Calls Itself

Recursion just means a function calling itself. Here's the smallest useful example, a countdown:

function countdown(n)
    if n <= 0 then
        writeln("Liftoff!")
    else
        writeln(n)
        countdown(n - 1)
    end if
end function

countdown(5)

countdown(5) prints 5, then calls countdown(4), which prints 4, then calls countdown(3), and so on, until countdown(0) finally hits the if branch instead of calling itself again, and the whole chain unwinds.

Every Recursive Function Needs a Stopping Point

That if n <= 0 line is called the base case, the condition that stops the function from calling itself again. Without one, a recursive function calls itself forever, the same way a loop without a condition that eventually turns false runs forever.

QF Code has a safety net here too, the same spirit as the iteration limit from chapter 4, just measuring something different. A program is limited to 500 nested function calls at once. Leave out a base case, and you'll hit that limit and get a runtime error, not a frozen program. It's the recursive equivalent of the loop limit you already met, doing the same job: catching a mistake before it costs you a frozen tab.

A Classic Example: Factorial

The traditional first recursive function, useful because it shows the pattern clearly:

function factorial(n)
    if n <= 1 then
        return 1
    end if
    return n * factorial(n - 1)
end function

writeln(factorial(5))   // 120

factorial(5) needs the answer to factorial(4), which needs the answer to factorial(3), all the way down to factorial(1), which is the base case and just returns 1 directly. Then every pending multiplication finishes on the way back up: 1, then 2 * 1, then 3 * 2, then 4 * 6, then 5 * 24, landing on 120.

An Optional Side Puzzle: Nested Boxes

If you want to try recursion somewhere playful, here's a small, self-contained puzzle you can drop into the QF Code IDE on its own, completely separate from your adventure project.

var boxes = ["box", ["box", ["box", "treasure"]]]

function openBox(contents)
    if contents == "treasure" then
        writeln("You found the treasure!")
    else
        writeln("You open a box...")
        openBox(contents[1])
    end if
end function

openBox(boxes)

Each box either holds the treasure directly, or holds another box one layer deeper. openBox doesn't need to know how many layers exist ahead of time, it just keeps calling itself on whatever's inside, until it finally reaches something that isn't a box anymore.

Make It Yours. If this clicked for you, try writing your own small recursive function, counting down by twos, adding up the numbers from 1 to n, anything with a clear base case and a clear way of getting closer to it with each call. If it didn't click yet, that's completely fine too. Move on, and come back to this chapter whenever you want another look.