Recursive vs Iterative Trade-offs
Convert recursive factorial and Fibonacci to iterative loops and explain when Python's recursion limit and stack size make iteration preferable.
Recursive vs Iterative Trade-offs is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Recursive-Iterative Duality
Every algorithm that can be written recursively can also be written iteratively, and vice versa. The recursive version often mirrors the problem's mathematical definition more closely, while the iterative version gives you explicit control over memory and avoids stack-overflow risks. Choosing between them is a pragmatic decision based on readability, depth limits, and performance requirements.
In interviews, being able to present both versions and explain the trade-offs is a strong signal of mastery.
Factorial: Recursive vs Iterative
Factorial is the canonical example. The recursive version directly encodes the mathematical definition n! = n × (n-1)!. It uses O(n) stack space due to n pending return values. The iterative version loops from 1 to n, using O(1) space. For n = 1000 the recursive version hits Python's default limit; the iterative version handles arbitrarily large n.
def factorial_rec(n):
if n == 0:
return 1
return n * factorial_rec(n - 1) # O(n) stack
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i # O(1) stack
return result
print(factorial_rec(10)) # 3628800
print(factorial_iter(10)) # 3628800
# Large n: iterative works, recursive may overflow
print(factorial_iter(1000) > 0) # True (Python handles big ints)Fibonacci: Exponential vs Linear
Naive recursive Fibonacci is O(2^n) time — disastrously slow for large n. The iterative version is O(n) time and O(1) space. Memoised recursion (next lesson) is also O(n) time but O(n) space due to the memo dict and O(n) stack. For Fibonacci, the iterative approach is optimal on all metrics. For n = 50, naive recursion takes seconds; iterative takes microseconds.
import time
def fib_rec(n):
if n <= 1: return n
return fib_rec(n-1) + fib_rec(n-2) # O(2^n)
def fib_iter(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a # O(n) time, O(1) space
# Timing comparison for n=35
start = time.time()
fib_rec(35)
print(f'Recursive n=35: {time.time()-start:.3f}s')
start = time.time()
fib_iter(35)
print(f'Iterative n=35: {time.time()-start:.6f}s')
print(fib_iter(100)) # handles large nTree Traversal: Recursive vs Iterative
Recursive tree traversal is naturally clean because the tree structure mirrors recursion. But for a deeply skewed tree (essentially a linked list), recursion depth equals tree height = O(n), risking stack overflow. The iterative version using an explicit stack has no depth limit and allows the stack size to grow on the heap rather than the call stack.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val; self.left = left; self.right = right
def preorder_rec(root, result=None):
if result is None: result = []
if root:
result.append(root.val)
preorder_rec(root.left, result)
preorder_rec(root.right, result)
return result
def preorder_iter(root):
if not root: return []
result, stack = [], [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right: stack.append(node.right)
if node.left: stack.append(node.left)
return result
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_rec(root)) # [1, 2, 4, 5, 3]
print(preorder_iter(root)) # [1, 2, 4, 5, 3]Merge Sort: Recursive vs Iterative (Bottom-Up)
Merge sort is naturally recursive (divide, recurse, merge). The iterative bottom-up merge sort avoids recursion entirely: start with sub-arrays of size 1, merge adjacent pairs into size-2 sub-arrays, then size-4, etc., doubling the sub-array size each pass. Bottom-up merge sort is O(n log n) time, O(n) space (for the merge buffer), and O(1) stack space.
def merge_sort_iterative(arr):
n = len(arr)
size = 1
while size < n:
for start in range(0, n, 2 * size):
mid = min(start + size, n)
end = min(start + 2 * size, n)
left = arr[start:mid]
right = arr[mid:end]
# Merge
i = j = 0
for k in range(start, end):
if i < len(left) and (j >= len(right) or left[i] <= right[j]):
arr[k] = left[i]; i += 1
else:
arr[k] = right[j]; j += 1
size *= 2
return arr
print(merge_sort_iterative([5, 2, 4, 6, 1, 3])) # [1,2,3,4,5,6]When Recursion Is Clearly Better
Recursion shines when the problem has a tree-like structure that maps directly to the call graph, when the base cases are natural, and when depth is bounded (O(log n) for balanced trees and divide-and-conquer). Examples: JSON parsing, directory traversal, game trees, and backtracking problems. In these cases the recursive code is shorter, clearer, and easier to prove correct than the equivalent iterative version.
# Recursion is clearest for JSON-like nested structures
def flatten(nested):
result = []
for item in nested:
if isinstance(item, list):
result.extend(flatten(item)) # recurse on sub-list
else:
result.append(item)
return result
print(flatten([1, [2, [3, 4], 5], 6])) # [1, 2, 3, 4, 5, 6]
print(flatten([])) # []
print(flatten([[1, [2]], [3, [4, [5]]]])) # [1, 2, 3, 4, 5]When Iteration Is Clearly Better
Iteration is the right choice when: the depth is O(n) and n is large (more than ~500 in safe Python code), the recursive and iterative versions are equally readable (Fibonacci, factorial), or the problem is fundamentally sequential with no natural sub-problem decomposition. Simple loops processing arrays from left to right — running sums, sliding windows, two pointers — should always be iterative.
# Iterative is clearest for sequential array processing
def running_max(nums):
result = []
curr_max = float('-inf')
for n in nums:
curr_max = max(curr_max, n)
result.append(curr_max)
return result
print(running_max([3, 1, 4, 1, 5, 9, 2, 6])) # [3,3,4,4,5,9,9,9]
# No natural recursion here — iteration is the only sensible choiceConverting DFS Recursion to Iteration
A systematic approach: every recursive DFS becomes iterative by pushing the recursive arguments onto an explicit stack. The key insight is that the recursive call f(args) is equivalent to pushing args and looping. For post-order processing (where you need results from children before the parent) you may need a two-pass approach or a visited flag.
# Post-order iterative using two stacks
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val=val; self.left=left; self.right=right
def postorder_iter(root):
if not root: return []
s1, s2 = [root], []
while s1:
node = s1.pop()
s2.append(node.val)
if node.left: s1.append(node.left)
if node.right: s1.append(node.right)
return s2[::-1] # reverse gives post-order
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(postorder_iter(root)) # [4, 5, 2, 3, 1]Performance Overhead of Recursion
Each recursive call in Python has non-trivial overhead: a new frame is created (allocating memory on the heap), local variables are initialised, and a return-address pointer is stored. Benchmarks show that function call overhead in Python is roughly 100–200 nanoseconds per call. For a recursion depth of 10^6 this adds up to 0.1–0.2 seconds of pure overhead, independent of the algorithm's work. Iterative loops avoid this overhead entirely.
import time
def rec_sum(n):
if n == 0: return 0
return n + rec_sum(n - 1)
def iter_sum(n):
total = 0
for i in range(n + 1):
total += i
return total
import sys; sys.setrecursionlimit(10000)
n = 5000
start = time.time()
for _ in range(100): rec_sum(n)
print(f'Recursive sum({n}) x100: {(time.time()-start)*1000:.2f}ms')
start = time.time()
for _ in range(100): iter_sum(n)
print(f'Iterative sum({n}) x100: {(time.time()-start)*1000:.2f}ms')Deciding in an Interview
In a coding interview, if you have a choice, ask: 'Is the recursion depth bounded by O(log n)?' If yes, recursion is fine. 'Is the recursion depth O(n)?' — prefer iteration or mention that you would convert to iterative for production. 'Is the problem naturally tree-shaped or divide-and-conquer?' — lean recursive. 'Is the problem a sequential scan?' — use iteration.
Always state your reasoning: 'I'll use recursion here because the depth is O(log n) for a balanced BST, so the O(log n) stack space is acceptable.'
Summary: Trade-Off Table
Summarising the trade-offs: recursive code is often shorter and mirrors problem structure, but costs O(depth) stack space and has function-call overhead. Iterative code is longer but uses O(1) stack space and avoids recursion limits. Memoised recursion (next lesson) is a middle ground: preserve the clarity of recursion while eliminating redundant recomputation. Always be explicit about space complexity including call-stack space when analysing your solution.
rows = [
('Factorial', 'O(n) / O(1)', 'O(n) / O(1)', 'Same time; iter wins on space'),
('Fibonacci', 'O(2^n) / O(n)', 'O(n) / O(1)', 'Iter massively wins'),
('Binary search','O(log n) / O(log n)', 'O(log n) / O(1)', 'Iter wins on space'),
('Tree DFS', 'O(n) / O(h)', 'O(n) / O(h)', 'Equal; rec cleaner'),
('Merge sort', 'O(n log n) / O(log n)', 'O(n log n) / O(1)', 'BU-iter wins on stack'),
]
for name, rec, it, note in rows:
print(f'{name:<15} rec={rec:<22} iter={it:<22} {note}')Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: recursion is preferred when depth is O(log n) or the problem is naturally tree-shaped; iteration when depth is O(n) or the problem is sequential, naive recursive Fibonacci is O(2^n) — the iterative version is O(n) time and O(1) space, and any recursive DFS converts to iterative by managing an explicit stack on the heap. Next up we apply memoisation to eliminate redundant recursive calls.
Frequently asked questions
Is the “Recursive vs Iterative Trade-offs” lesson free?
Yes — the full text of “Recursive vs Iterative Trade-offs” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Recursive vs Iterative Trade-offs”?
Convert recursive factorial and Fibonacci to iterative loops and explain when Python's recursion limit and stack size make iteration preferable. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Recursive vs Iterative Trade-offs” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Recursion Framework: Base Case, Trust, Build
- Visualising the Call Stack
- Recursive vs Iterative Trade-offs
- Memoisation: Caching Recursive Results