Lesson 12.4 · Recursion

From Recursion to Loops

Java doesn't optimise tail calls, so deep linear recursion should become a loop or use an explicit stack.

10 min

Think of it like this

Instead of asking the person in front of you, who asks the person in front of them, you walk to the front of the queue yourself and count your way back. Same answer, no chain of waiting people.

1.Tail recursion

A call is a tail call when it's the very last thing the function does (nothing to combine afterwards). Some languages reuse the frame for tail calls; Java doesn't. So a tail-recursive function still uses O(n) stack in Java, but it converts mechanically into a loop: the parameters become loop variables.

For branching recursion (trees, DFS), an explicit Deque used as a stack replaces the call stack and avoids overflow on deep inputs.

Loop.java

public class Main {
    static long factTail(int n, long acc) {            // tail-recursive
        if (n <= 1) return acc;
        return factTail(n - 1, acc * n);
    }
    static long factLoop(int n) {                      // the same thing as a loop
        long acc = 1;
        while (n > 1) { acc *= n; n--; }
        return acc;
    }
    public static void main(String[] args) {
        System.out.println(factTail(10, 1) + " " + factLoop(10));
    }
}

Output

3628800 3628800

Remember

Java has no tail-call optimisation.
Tail recursion → loop with accumulator variables.
Branching recursion → explicit stack when depth can be large.

Common mistakes

Assuming tail recursion avoids StackOverflowError in Java.

Command Palette

From Recursion to Loops

1.Tail recursion