What you'll learn
Quick Answer
Recursion solves a problem by calling itself on a smaller input, while iteration repeats with a loop. Every recursive solution can be rewritten iteratively and vice versa. Recursion is clearer for naturally nested structures such as trees and graphs, but each pending call consumes stack space, so deep recursion overflows. Iteration uses constant stack space and is generally faster, but can be clumsy for branching problems.
The Same Problem, Both Ways
# Recursive
def factorial(n):
if n <= 1: return 1 # base case
return n * factorial(n - 1) # recursive case
# Iterative
def factorial(n):
result = 1
for i in range(2, n + 1):
result *= i
return resultBoth are correct and both are O(n) time. They differ in memory.
The iterative version uses one stack frame and a couple of variables — O(1) space. The recursive version stacks n frames before any of them return, each holding its own n and return address — O(n) space.
factorial(4)
→ factorial(3) ← all four frames exist simultaneously
→ factorial(2)
→ factorial(1) ← only now does anything return
That hidden space cost is the single most important practical difference, and it is what interviewers are checking when they ask you to compare them.
Every recursive function needs two things: a base case that returns without recursing, and a recursive case that moves toward it. Missing either gives infinite recursion and a stack overflow.
When Recursion Is Clearly Better
Recursion wins when the data or the problem is itself recursive.
Trees and graphs. A tree is defined in terms of subtrees, so recursion mirrors the structure:
def height(node):
if not node: return 0
return 1 + max(height(node.left), height(node.right))The iterative equivalent needs an explicit stack and is noticeably harder to read.
Backtracking. Problems needing you to try a choice, explore, and undo it — N-queens, sudoku, generating permutations. Recursion handles the undo naturally because state unwinds as calls return.
def permute(nums, current, used, out):
if len(current) == len(nums):
out.append(current[:]); return
for i, n in enumerate(nums):
if used[i]: continue
used[i] = True; current.append(n)
permute(nums, current, used, out)
current.pop(); used[i] = False # undo — trivial in recursionDivide and conquer. Merge sort and quicksort split, solve each half, and combine — a shape that reads directly as recursion.
Nested structures of unknown depth: JSON, file systems, nested comments. You cannot write a fixed number of loops for unknown nesting.
When Iteration Is Better
Simple repetition. Summing an array, searching a list, counting. Recursion adds cost and complexity for nothing.
Large inputs. This is the decisive one. Python's default recursion limit is around 1000 frames; JavaScript's is roughly 10,000. Processing a 100,000-element linked list recursively will crash.
RecursionError: maximum recursion depth exceeded # Python
RangeError: Maximum call stack size exceeded # JavaScriptRaising the limit is a workaround, not a fix — the underlying stack is still finite and you may crash the interpreter rather than get a clean error.
Performance-sensitive code. Every call has overhead: pushing a frame, saving state, jumping. In a hot loop that adds up. And unlike some languages, JavaScript and Python engines generally do not perform tail-call optimisation, so writing a tail-recursive version does not save you.
When state is simple. If the problem needs only a running total or an index, a loop is clearer. Recursion earns its complexity when there is genuine branching or backtracking.
Converting Recursion to Iteration
Any recursion can be made iterative, because recursion is a stack. The conversion is mechanical: replace the call stack with an explicit one.
# Recursive DFS — crashes on deep trees
def dfs(node):
if not node: return
visit(node)
dfs(node.left)
dfs(node.right)
# Iterative — bounded by heap memory, not the call stack
def dfs(root):
stack = [root]
while stack:
node = stack.pop()
if not node: continue
visit(node)
stack.append(node.right) # push right first
stack.append(node.left) # so left is processed first
For simple linear recursion, the loop is usually obvious — a running variable replaces the accumulated return values.
For tree recursion the explicit stack version is longer but always possible. Note that the order of pushing is reversed, because a stack pops last-in-first-out. Getting this backwards is the most common conversion bug.
The practical trigger for converting: if the input could make the depth exceed a few thousand, convert. Otherwise keep the recursion, because readability usually matters more than the small overhead.
How This Comes Up in Interviews
"What is the space complexity?" The answer for a recursive solution must include the call stack — O(h) for a tree traversal, O(n) for linear recursion — even when the function allocates nothing. Candidates who say O(1) for a recursive function are usually corrected.
"Can you do it iteratively?" Standard follow-up on tree and linked-list problems. It tests whether you understand that recursion is a stack, so practise the explicit-stack version of tree traversals at least once.
"Why is your recursive Fibonacci slow?" Because it recomputes the same subproblems, giving O(2ⁿ). The fix is memoization, which is the entry point to dynamic programming.
"What happens with a very deep tree?" Stack overflow. Mentioning this before being asked signals real experience — most candidates only consider correctness.
A useful summary to offer: use recursion when the structure is recursive and the depth is bounded; use iteration when the input can be large or the logic is a simple repetition. Then note that you can convert either way, and say which you would choose here and why. That framing answers the question the interviewer is actually asking, which is whether you can reason about trade-offs rather than recite definitions.