DSA · Lesson 7 of 20 · 4 min
Recursion and Iteration: Problem Solving Paradigms
You will be asked to convert a recursive solution to an iterative one. This lesson is about how to do it and explain the trade-offs.
The Core Trade-off: Call Stack vs. Loop Counter
Recursion and iteration both achieve repetition. The difference is how they manage state.
Recursion uses the call stack. When a function calls itself, the engine pushes a new frame onto the stack with the function's arguments and local variables. This is elegant because the state is managed for you implicitly. The cost is memory. Each stack frame consumes memory, and there's a hard limit. Exceed it, and you get a stack overflow.
Iteration uses a loop. You manage state explicitly with variables (i, len, currentNode). This is more verbose but has minimal memory overhead. You trade the elegance of the call stack for direct control and near-infinite scalability.
In an interview, choosing one over the other isn't about right or wrong. It's about articulating this trade-off: readability and declarative style (recursion) versus memory safety and performance (iteration).
When to Reach for Recursion
Use recursion when the problem itself is recursive. This is common with data structures that have a nested or self-similar shape. Think traversing a file system, a React component tree, or a complex JSON object from an API.
For these problems, a recursive solution often mirrors the structure of the data, making the code shorter and more readable. The function processes a single node and then calls itself for each of its children.
The trap: Don't use recursion for simple linear tasks like iterating over an array to find an element. Using a for loop is clearer, more efficient, and shows you aren't just using a pattern for its own sake.
A classic frontend example is a deep clone function. The structure of the data (an object can contain other objects or arrays) is inherently recursive.
type JSONValue = string | number | boolean | null | { [key: string]: JSONValue } | JSONValue[];
function deepClone(obj: JSONValue): JSONValue {
// Base case: primitives are immutable, return them directly.
if (obj === null || typeof obj !== 'object') {
return obj;
}
// Recursive step for arrays.
if (Array.isArray(obj)) {
// Create a new array and recursively clone each item.
return obj.map(item => deepClone(item));
}
// Recursive step for objects.
const clonedObject: { [key:string]: JSONValue } = {};
for (const key in obj) {
if (Object.prototype.hasOwnProperty.call(obj, key)) {
// Create a new object and recursively clone each value.
clonedObject[key] = deepClone((obj as { [key: string]: JSONValue })[key]);
}
}
return clonedObject;
}
This implementation is clean but incomplete. It doesn't handle
Date,RegExp, functions, or circular references. In an interview, you should mention these edge cases as potential follow-ups. It shows you're thinking beyond the happy path.
How to Convert Recursion to Iteration
The key is to replace the implicit call stack with an explicit stack data structure that you manage yourself. This pattern is crucial for interview problems.
Here’s the process:
- Create a stack (a simple array will do) and push the initial input onto it.
- Start a
whileloop that runs as long as the stack is not empty. - Inside the loop,
popan item. This is your "current" node to process. - Do the work on the current item.
- Instead of making a recursive call for its children,
pushthe children onto the stack.
This transforms a depth-first recursive traversal into a depth-first iterative one. The order of operations is identical. You've just swapped the engine's call stack for a variable in your own function. This technique is how you avoid stack overflows on deeply nested structures.
The Naive Recursion Performance Trap
Some problems have recursive definitions that are computationally disastrous if implemented directly. The classic example is Fibonacci: fib(n) = fib(n-1) + fib(n-2).
// This is an example of what NOT to do.
function fibonacciRecursive(n: number): number {
if (n <= 1) {
return n;
}
// Each call creates two more calls.
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
This function has a time complexity of O(2^n) because it re-computes the same values over and over. fib(5) calls fib(3) twice, fib(2) three times, and so on.
The trap: An interviewer might give you a problem like this to see if you spot the exponential complexity. The fix is not to abandon recursion, but to recognize the "overlapping subproblems" and use memoization. Or, more simply, convert it to an iterative solution that builds from the bottom up. The iterative approach has a time complexity of O(n) and space complexity of O(1).
Visualizing the Call Stack
This is what happens under the hood when you call a simple recursive function like factorial(3). Each call adds a frame. When a function returns, its frame is popped off. Understanding this flow is key to debugging recursion.
The stack grows until it hits a base case (factorial(1)), then it unwinds, passing return values back up the chain. A stack overflow happens when this chain gets too long before it can start unwinding.
Try it
Take the deepClone function from this lesson and rewrite it iteratively. Use an explicit stack to manage the objects and arrays you need to process. Don't worry about cloning every value perfectly; focus on traversing the structure without using recursion. This will take about 20 minutes and solidify the conversion pattern.
Next: We'll apply these paradigms directly in the Introduction to Trees: Binary Trees & BSTs, where recursion is the most natural way to think about traversal.
Lock it in — apply this lesson under interview conditions.