1.2 The Call Stack | Code Scholars Tutoring

How it works

Each pending call occupies a stack frame, so recursion depth costs memory even when the code looks small.

State the recursion depth for a given input to reason about space, not only time.

Common error

Assuming recursion is free. Depth proportional to input size means linear extra space.

Worked example

Java snippets run inside a main method. Add import java.util.*; when collection types are used.

Java

class Solver {
    void visit(int n) {
        if (n == 0) return;
        System.out.print(n + " ");
        visit(n - 1);
        System.out.print(n + " ");
    }
}
new Solver().visit(2);

Output

2 1 1 2

Each call retains its local n while a deeper call runs. Statements before the recursive call execute on descent; statements after it execute while calls return.

Calls descend from visit(2) to visit(1) to visit(0), then return in reverse order. — Each call retains its own local state until its child returns.

Exercises

1.2.1 · Explain

For visit(3) in the example, give the printed sequence.

Show solution

The sequence is 3 2 1 1 2 3. Each call prints before descending and again after its child returns.

1.2.2 · Write code

Write a recursive method that prints 1 through 3 in increasing order by making the recursive call before printing.

Show solution

The deeper call completes the smaller prefix first.

One valid solution

class Solver {
    void up(int n) {
        if (n == 0) return;
        up(n - 1);
        System.out.print(n + " ");
    }
}
new Solver().up(3);

Expected output

1 2 3

Open Java compiler