Converting Recursion to Iteration
What you'll learn: How to transform a recursive method into a loop-based solution to avoid stack overflow and improve performance.
Why Convert Recursion to Iteration?
While recursion elegantly solves many problems by breaking them into smaller pieces, it comes with a cost: each recursive call adds a frame to the call stack. Deep recursion can trigger a StackOverflowError. Additionally, iterative solutions often run faster because they avoid the overhead of repeated method calls.
The good news? Many recursive algorithms can be rewritten using loops.
The Core Idea
Recursion uses the call stack to remember "where we are" in the problem. Iteration uses loop control variables to track progress instead. You replace:
- The base case with a loop condition
- The recursive call with an update to loop variables
Example: Factorial
Recursive version (from lesson 227):
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
Iterative version:
int factorial(int n) {
int result = 1;
while (n > 1) {
result = result * n;
n = n - 1;
}
return result;
}
Here, the loop replaces the recursive calls. The variable result accumulates the answer, and n decrements until the base condition is met.
When to Convert
Not every recursive method needs conversion, but iteration is preferable when:
- The recursion depth could grow large
- Performance is critical
- The recursive pattern is simple (like counting or accumulating)
Key Takeaway: Recursion can often be rewritten as a loop using variables to track state, avoiding stack overflow and improving efficiency without changing the algorithm's logic.