Recursion vs Iteration

Most problems that can be solved with recursion can also be solved with a loop (iteration), and the other way round. So which should you write? Both are correct tools; they differ in readability, speed and memory. Seeing the same problems solved both ways is the quickest way to learn when each one fits.

Factorial Both Ways

public class FactLoop {
    static long factorial(int n) {
        long result = 1;
        for (int i = 2; i <= n; i++) {
            result *= i;
        }
        return result;
    }
 
    public static void main(String[] args) {
        System.out.println(factorial(10));
    }
}

public class FactRec {
    static long factorial(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }
 
    public static void main(String[] args) {
        System.out.println(factorial(10));
    }
}

3628800

Both print 3,628,800. The loop uses one variable; the recursive version uses one stack frame per call (10 here).

Fibonacci: Where Naive Recursion Hurts

public class Fib {
    static long calls = 0;
 
    static long fibRec(int n) {
        calls++;
        if (n < 2) {
            return n;
        }
        return fibRec(n - 1) + fibRec(n - 2);
    }
 
    static long fibLoop(int n) {
        long a = 0, b = 1;
        for (int i = 0; i < n; i++) {
            long next = a + b;
            a = b;
            b = next;
        }
        return a;
    }
 
    public static void main(String[] args) {
        System.out.println("Loop:      " + fibLoop(30));
        long result = fibRec(30);
        System.out.println("Recursive: " + result + " using "
                + calls + " calls");
    }
}

Loop:      832040
Recursive: 832040 using 2692537 calls

How it works

1. fibRec(30) calls fibRec(29) and fibRec(28), and fibRec(29) calls fibRec(28) again, and so on. The same values are recomputed again and again: almost 2.7 million calls.
2. fibLoop(30) computes each value once: 30 rounds.
3. Each extra n roughly multiplies the recursive work by 1.6, so fibRec(50) would take billions of calls.

Try it yourself: print the number of calls for fibRec(20) and fibRec(25). How fast does it grow?

Side by Side

Common Mistakes

Using naive recursion for Fibonacci in real code. Use a loop, or recursion with memoization.

Turning every loop into recursion. For simple counting, it only adds stack frames and risk.

Forgetting stack limits. Recursion 100,000 levels deep can overflow even when the logic is correct. Java doesn't optimize tail calls, so deep chains are safer as loops.

Interview Corner

Practice

1. Easy: Write sumTo(n) both iteratively and recursively, and check they agree for n = 100.
2. Harder: Add a long[] memo array to fibRec so each value is computed only once, and count the calls for n = 30 again.

Key Takeaways