5.07Beginner5 topics20 min

Converting recursion

Recursion is elegant but costs stack space and can overflow. Every recursive algorithm can be rewritten with a loop, using an explicit stack, an accumulator, or by computing results bottom-up, and sometimes caching results turns exponential recursion into linear time.

Learning goals

Replace recursion with an explicit stack
Write an iterative depth-first traversal
Rewrite a recursion bottom-up
Turn tail recursion into a loop and memoize overlapping subproblems

Prerequisites

Recursion mechanicsStack (ArrayDeque)Recursion pitfalls

The JVM call stack is just a stack data structure the runtime manages for you. If you manage a stack yourself, you control its size and are not limited by the thread's stack space.

5.07.1

Explicit stack

The call stack stores, for each pending call, its arguments and where to continue. You can store the same information in your own Deque: push the arguments, loop while the deque is not empty, and pop to process.

Take a recursive method with a single call at the end, push the work for the call instead of calling, and the loop replaces the recursion. The heap holds your stack, so depth is limited by memory, not by the thread stack.

Java

1// recursive: depth = list length
2static long sum(Node n) { return n == null ? 0 : n.val + sum(n.next); }
3
4// iterative: no recursion, no depth limit
5static long sumIter(Node head) {
6    long total = 0;
7    for (Node cur = head; cur != null; cur = cur.next) total += cur.val;
8    return total;
9}

5.07.2

Iterative DFS

Depth-first search is the standard case: recursion visits a node, then its children. The iterative version keeps the nodes still to visit on a stack. Push the root, then repeatedly pop a node, process it, and push its children (right child first if you want left-to-right order).

This avoids StackOverflowError on deep trees and graphs, such as a path graph of a million nodes.

Java

1// recursive pre-order
2static void preorder(TreeNode n) {
3    if (n == null) return;
4    visit(n);
5    preorder(n.left);
6    preorder(n.right);
7}
8
9// iterative pre-order with an explicit stack
10static void preorderIter(TreeNode root) {
11    Deque<TreeNode> stack = new ArrayDeque<>();
12    if (root != null) stack.push(root);
13    while (!stack.isEmpty()) {
14        TreeNode n = stack.pop();
15        visit(n);
16        if (n.right != null) stack.push(n.right);   // pushed first, so popped last
17        if (n.left != null) stack.push(n.left);
18    }
19}

5.07.3

Bottom-up processing

Top-down recursion starts from the big problem and works down to the base cases. Bottom-up starts from the base cases and builds up to the answer in a loop, in an order where every dependency is already computed.

For Fibonacci that means computing fib(2), fib(3), … in order. It uses no stack and, if only the last two values matter, only O(1) memory. It is the basis of dynamic programming.

Java

1static long fibBottomUp(int n) {
2    if (n < 2) return n;
3    long prev = 0, cur = 1;
4    for (int i = 2; i <= n; i++) {
5        long next = prev + cur;
6        prev = cur;
7        cur = next;
8    }
9    return cur;                // O(n) time, O(1) space, no recursion
10}

Worst

O(n)

Space

O(1)

5.07.4

Tail-call transformation

A tail-recursive method can be rewritten as a loop by turning its parameters into variables and the call into an assignment followed by a jump back to the top. Java does not optimise tail calls, so doing this by hand removes the stack growth.

Pattern: introduce an accumulator for the work that was pending, then loop until the base case.

Java

1// tail-recursive with an accumulator
2static long factTail(int n, long acc) {
3    if (n == 0) return acc;
4    return factTail(n - 1, acc * n);
5}
6
7// the same logic as a loop
8static long factLoop(int n) {
9    long acc = 1;
10    while (n != 0) {
11        acc *= n;              // the work that was in the argument
12        n--;                   // the argument that was in the call
13    }
14    return acc;
15}
16
17// Euclid's gcd, iterative
18static int gcdLoop(int a, int b) {
19    while (b != 0) { int t = a % b; a = b; b = t; }
20    return a;
21}

5.07.5

Memoization

Memoization keeps the recursive structure but stores each result the first time it is computed, so repeated subproblems are answered from a table. Naive Fibonacci goes from about 1.6ⁿ calls to 2n - 1, as you saw in the animation: cache hits are the dashed green boxes.

Use an array when the arguments are small integers and a HashMap for general keys. Pick a sentinel that cannot be a real answer (such as -1) to mean not computed yet; using 0 breaks when 0 is a valid answer.

Java

1static long[] memo = new long[91];
2
3static long fib(int n) {
4    if (n < 2) return n;
5    if (memo[n] != 0) return memo[n];            // fib(n) is never 0 for n >= 2, so 0 means "unknown"
6    return memo[n] = fib(n - 1) + fib(n - 2);
7}
8
9// general keys: use get / put, NOT computeIfAbsent with a recursive lambda
10static Map<Integer, Long> cache = new HashMap<>();
11static long fib2(int n) {
12    if (n < 2) return n;
13    Long hit = cache.get(n);
14    if (hit != null) return hit;
15    long value = fib2(n - 1) + fib2(n - 2);
16    cache.put(n, value);
17    return value;
18}

Practice ladder

Now try it yourself

Easy

Rewrite a recursive array sum as a loop
Convert recursive gcd to a loop

Medium

Iterative in-order traversal of a binary tree
Climbing stairs bottom-up with two variables
Memoize a recursive grid path counter

Advanced

Iterative post-order traversal with a single stack
Simulate the call stack of any recursive method with frames holding a program counter
Convert recursive quick sort to an explicit stack that always pushes the larger side first

Key takeaways

An explicit stack or accumulator removes recursion's depth limit.
Bottom-up computes in dependency order and often needs O(1) extra space.
Memoization keeps the recursive form and removes repeated work; use get/put, not recursive computeIfAbsent.