Recursion

What Is Recursion?

Recursion is when a function solves a problem by calling itself with a smaller version of the same problem. Each call makes progress until the problem is small enough to solve directly — and then the chain of calls unwinds, combining all the partial answers into a final result.

Real life is full of recursive thinking. A Russian nesting doll contains a smaller version of itself, which contains a smaller version of itself, until you reach the tiny solid doll at the centre. A directory on your computer can hold files and other directories — each of which can hold more files and more directories, on and on until you reach empty folders. Recursion describes both naturally.

The Three Rules of Recursion

Every correct recursive function has three parts. Missing any one of them causes either a wrong answer or an infinite loop that crashes your program.

A Simple Example — Countdown

Before diving into our project code, let’s look at the simplest possible recursion: printing a countdown from n to zero.

// Recursive countdown
function countdown(n) {
    // Rule 1 — base case: stop when we reach zero
    if (n < 0) return;

    console.log(n);

    // Rule 2 & 3 — recursive case: call with a smaller n
    countdown(n - 1);
}

countdown(3);
// Output:  3  2  1  0

Trace through it mentally. countdown(3) prints 3, then calls countdown(2). That prints 2 and calls countdown(1). That prints 1 and calls countdown(0). That prints 0 and calls countdown(-1). -1 < 0 is true → the function returns immediately. Done.

Classic: Factorial

Factorial is the textbook recursion example. 5! = 5 × 4 × 3 × 2 × 1. Notice that 5! = 5 × 4! — it’s defined in terms of itself.

function factorial(n) {
    if (n <= 1) return 1;          // base case
    return n * factorial(n - 1);  // recursive case — smaller n each time
}

console.log(factorial(5)); // 120

Recursion vs. a Loop

Any recursion can be rewritten as a loop, and any loop can be rewritten as recursion. So why choose one over the other? It comes down to what makes the solution clearest.

Recursion in Our Code — revealNextLetter()

In every Beale Cipher sketch (BC3, BC4, BC5, and the Generalized version), once all the digit particles have flown home, the word needs to reveal itself one letter at a time — each letter popping in with a brief scale-burst, then the next letter, then the next, until the full word is visible.

We needed timed gaps between letter reveals so the student can watch each one materialise. That ruled out a simple for loop (which would reveal all letters instantly with no visible pause). We used recursive setTimeout instead.

Here is the actual function, exactly as it appears in the sketches:

/**
 * revealNextLetter — cascaded reveal: each letter pops in sequence.
 * Spawn the next reveal after a short delay, giving each one time to pop.
 */
function revealNextLetter(startIdx) {

    // Scan from startIdx forward to find the next letter to reveal
    for (let i = startIdx; i < chars.length; i++) {
        const s = chars[i];
        if (s.origLetter === ' ') continue;  // skip spaces
        if (s.cipherNum === null) continue;  // skip unencodeable chars
        if (s.revealed) continue;            // skip already-revealed

        // ── Materialise this letter ──────────────────────────────────────
        s.alpha    = 100;
        s.revealed = true;
        s.popTimer = POP_DUR;          // starts the scale-pop animation
        s.popScale = POP_SCALE_PEAK;

        spotlightWord(s.cipherNum, 185);  // highlight word in ticker

        // ── Recursive call — scheduled 220ms in the future ───────────────
        setTimeout(() => revealNextLetter(i + 1), 220);
        return;   // ← critically: stop this call here, yield to browser
    }

    // ── Base case: no more letters to reveal ─────────────────────────────
    setTimeout(() => {
        animState = 'done';
        if (assembleBtn) assembleBtn.disabled = true;
    }, 400);
}

Identifying the Three Rules

Why return after scheduling the next call?

Notice the bare return; immediately after the setTimeout line. This is essential. Without it, the loop would continue and reveal the next letter in the same call — skipping the 220 ms pause entirely. The return hands control back to the browser, which draws the current frame, runs any queued animations, and then — 220 ms later — fires the next recursive call.

Call-by-Call Trace

Let’s walk through a concrete example. Suppose the word is CAT (3 letters, indices 0, 1, 2). All digits have just landed home. revealNextLetter(0) is called.

Total visible time: 3 letters × 220 ms = 660 ms of animated cascade, plus the final 400 ms settling delay. Try counting along next time you press Assemble in a Beale Cipher app!

Why Recursion? — The Rationale & Benefits

Why we chose recursion here

The broader benefits of recursion as a technique

Where to Go Next

You have just seen a real-world recursive function shipping in a polished animation app. Here are the best ways to deepen your understanding:

Practice problems to try

1. Sum of a list. Write sumList([3, 1, 4, 1, 5]) recursively — the sum of a list is the first element plus the sum of the rest.
2. Reverse a string. Write reverseStr("hello") recursively — the reverse of a string is its last character followed by the reverse of everything before it.
3. Flatten nested arrays. Write flatten([1, [2, [3, 4]], 5]) that returns [1, 2, 3, 4, 5]. Each element is either a number (base case) or an array (recurse into it).
4. Modify our code. Open Beale Cipher (Generalized) and find revealNextLetter in swGenBealeCipher1Sketch.js. Change the delay from 220 to 600 and watch the cascade slow down dramatically. Then try 0 — what happens, and why?

Related pages in this project

• Assemble Algorithm — a deep-dive into the digit-particle homing physics that runs just before revealNextLetter is called.
• Destination: Recursion — a broader retrospective on recursion patterns across the entire SWIsland Saga, with pros, cons, and stage-by-stage examples.

External resources

• W3Schools — JavaScript Recursion — short intro with simple examples.
• Eloquent JavaScript, Chapter 3 (Functions) — free online book; the recursion section is outstanding.
• Khan Academy — Recursive Algorithms — visual, interactive, great for beginners.