The one picture you need
How recursion actually runs
A recursive call is not magic. The machine keeps a stack of frames. Each frame holds one call's variables and the line it has to come back to. Calling pushes a frame. Returning pops it. That is the whole idea.
fact(4) at its deepest moment. Five frames are alive at once.
+------------------+ <- top: running right now
| fact(0) n = 0 | base case, returns 1
+------------------+
| fact(1) n = 1 | frozen, waiting for fact(0)
+------------------+
| fact(2) n = 2 | frozen, waiting for fact(1)
+------------------+
| fact(3) n = 3 | frozen, waiting for fact(2)
+------------------+
| fact(4) n = 4 | frozen, waiting for fact(3)
+------------------+ <- bottom: the call you made
push fact(4) n=4 needs fact(3)
push fact(3) n=3 needs fact(2)
push fact(2) n=2 needs fact(1)
push fact(1) n=1 needs fact(0)
push fact(0) n=0 base case reached
pop fact(0) returns 1
pop fact(1) returns 1 * 1 = 1
pop fact(2) returns 2 * 1 = 2
pop fact(3) returns 3 * 2 = 6
pop fact(4) returns 4 * 6 = 24
Converting to a loop means one thing: keep the same work, stop keeping the frames.
Conversion 1 of 8
Factorial
Why convert: the recursion goes one way and never branches, so a loop does the same multiplications with one frame instead of n. This is the simplest shape there is: linear recursion with an accumulator.
Python
# recursive: n frames stacked up
def fact(n):
if n == 0:
return 1
return n * fact(n - 1)
# iterative: one frame, one loop
def fact(n):
result = 1
for i in range(2, n + 1):
result *= i
return result
# fact(5) -> 120 fact(0) -> 1
Java
// recursive
static long factRec(int n) {
if (n == 0) return 1;
return n * factRec(n - 1);
}
// iterative
static long factIter(int n) {
long result = 1;
for (int i = 2; i <= n; i++)
result *= i;
return result;
}
// factIter(5) -> 120
The rule you just used. Whatever the recursion multiplied on the way back, the loop multiplies on the way forward. Start the accumulator at the base case's answer (here 1) and walk the same range.
Conversion 2 of 8
Fibonacci: naive, memo, loop
Why convert: the naive version calls itself twice, so it works out the same values millions of times. Memoising fixes the time. The loop also fixes the memory.
Python
# 1 naive: recomputes everything
def fib(n):
if n < 2: return n
return fib(n - 1) + fib(n - 2)
# 2 memo: work each one out once
def fib(n, memo=None):
if memo is None: memo = {}
if n < 2: return n
if n in memo: return memo[n]
memo[n] = fib(n-1, memo)+fib(n-2, memo)
return memo[n]
Java
// 1 naive
static long fib(int n) {
if (n < 2) return n;
return fib(n-1) + fib(n-2);
}
// 2 memo: pass new long[n + 1]
static long fibM(int n, long[] memo) {
if (n < 2) return n;
if (memo[n] != 0) return memo[n];
memo[n] = fibM(n-1,memo)+fibM(n-2,memo);
return memo[n];
}
# 3 loop: two variables, no stack
def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
// 3 loop
static long fib3(int n) {
long a = 0, b = 1;
for (int i = 0; i < n; i++) {
long t = a + b; a = b; b = t;
}
return a;
}
Conversions 3 and 4 of 8
Sum a list. Reverse a string.
Why convert (sum): a list of 10,000 numbers means 10,000 frames, and Python gives up at about a thousand. The loop has no such limit.
Python
# recursive: walk with an index
def total(a, i=0):
if i == len(a): return 0
return a[i] + total(a, i + 1)
# iterative: one accumulator
def total(a):
s = 0
for x in a: s += x
return s
# [4,8,15,16,23,42] -> 108
Java
static int total(int[] a, int i) {
if (i == a.length) return 0;
return a[i] + total(a, i + 1);
}
static int total(int[] a) {
int s = 0;
for (int x : a) s += x;
return s;
}
Why convert (reverse): the recursive version builds a brand new string at every level, so it costs O(n²) time and O(n) space. Two pointers swapping in place cost O(n) time and no extra space.
# recursive: a new string each level
def rev(s):
if len(s) <= 1: return s
return rev(s[1:]) + s[0]
# iterative: swap the two ends
def rev(s):
ch = list(s)
i, j = 0, len(ch) - 1
while i < j:
ch[i], ch[j] = ch[j], ch[i]
i += 1; j -= 1
return "".join(ch)
# "placement" -> "tnemecalp"
static String rev(String s) {
if (s.length() <= 1) return s;
return rev(s.substring(1)) + s.charAt(0);
}
static String revLoop(String s) {
char[] ch = s.toCharArray();
int i = 0, j = ch.length - 1;
while (i < j) {
char t = ch[i];
ch[i] = ch[j]; ch[j] = t;
i++; j--;
}
return new String(ch);
}
Conversion 5 of 8
Binary search
Why convert: this is tail recursion — the recursive call is the last thing that happens, so no frame is waiting on the way back. Neither Python nor Java removes those frames for you, so the loop is a free win: O(1) space instead of O(log n).
Python
# recursive: pass the window down
def bs(a, t, lo, hi):
if lo > hi: return -1
mid = lo + (hi - lo) // 2
if a[mid] == t: return mid
if a[mid] < t:
return bs(a, t, mid + 1, hi)
return bs(a, t, lo, mid - 1)
# iterative: move the window here
def bs(a, t):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if a[mid] == t: return mid
if a[mid] < t: lo = mid + 1
else: hi = mid - 1
return -1
Java
static int bs(int[] a, int t,
int lo, int hi) {
if (lo > hi) return -1;
int mid = lo + (hi - lo) / 2;
if (a[mid] == t) return mid;
if (a[mid] < t)
return bs(a, t, mid + 1, hi);
return bs(a, t, lo, mid - 1);
}
static int bs(int[] a, int t) {
int lo = 0, hi = a.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == t) return mid;
if (a[mid] < t) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
Checked on [2,5,8,12,16,23,38,56,72,91]: searching for 2 gives 0, for 23 gives 5, for 91 gives 9, for 40 gives -1. Both versions agree. Note the midpoint, lo + (hi - lo) / 2 and not (lo + hi) / 2. In Java lo + hi can overflow an int on a huge array. Python integers never overflow, but keep the same line so the habit carries across.
Conversion 6 of 8
In-order, with your own stack
Why convert: a skewed tree of 100,000 nodes is 100,000 frames deep and crashes. Holding the stack yourself moves it off the call stack and onto the heap, which is far bigger.
Python
# recursive: Python holds the stack
def inorder(node, out):
if node is None: return
inorder(node.left, out)
out.append(node.val)
inorder(node.right, out)
# iterative: you hold the stack
def inorder(root):
out, stack, node = [], [], root
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
out.append(node.val)
node = node.right
return out
Java
static void inorder(Node n,
List<Integer> out) {
if (n == null) return;
inorder(n.left, out);
out.add(n.val);
inorder(n.right, out);
}
static List<Integer> inorder(Node root) {
List<Integer> out =
new ArrayList<>();
Deque<Node> st = new ArrayDeque<>();
Node n = root;
while (n != null || !st.isEmpty()) {
while (n != null) {
st.push(n); n = n.left;
}
n = st.pop();
out.add(n.val);
n = n.right;
}
return out;
}
8 in-order -> 1 3 6 8 10 14
/ \
3 10 The inner while walks left as far as it
/ \ \ can, pushing as it goes. The pop is the
1 6 14 visit. Then step right and repeat.
Conversion 7 of 8
Level-order: the one you never convert
Why there is nothing to convert: level-order visits nodes in the order they were discovered, not in the order they were called. That is a queue, and the call stack cannot give you a queue. So this one is born iterative.
Python
from collections import deque
def levels(root):
if not root: return []
out, q = [], deque([root])
while q:
row = []
for _ in range(len(q)):
x = q.popleft()
row.append(x.val)
if x.left: q.append(x.left)
if x.right: q.append(x.right)
out.append(row)
return out
# -> [[8], [3, 10], [1, 6, 14]]
Java
static List<List<Integer>> levels(Node r) {
List<List<Integer>> out =
new ArrayList<>();
if (r == null) return out;
Queue<Node> q = new LinkedList<>();
q.add(r);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> row = new ArrayList<>();
for (int i = 0; i < size; i++) {
Node x = q.poll();
row.add(x.val);
if (x.left != null) q.add(x.left);
if (x.right != null) q.add(x.right);
}
out.add(row);
}
return out;
}
Say this in the interview. "Depth-first can be recursive, because the call stack is a stack. Breadth-first cannot, because I need a queue, so I write the loop." The for _ in range(len(q)) line is what splits the output into levels; drop it and you get one flat list.
Conversion 8 of 8
Flood fill on a grid
Why convert: a 1000 × 1000 grid of all land is a million frames deep. This is the most common cause of a "runtime error" verdict on Number of Islands. Your own stack has no such limit.
Python
# '1' = land, '0' = water
def bad(g, r, c):
if r < 0 or r >= len(g): return True
if c < 0 or c >= len(g[0]): return True
return g[r][c] != '1'
# recursive: four calls per cell
def sink(g, r, c):
if bad(g, r, c): return
g[r][c] = '0'
sink(g, r + 1, c); sink(g, r - 1, c)
sink(g, r, c + 1); sink(g, r, c - 1)
# iterative: your own stack
def sink2(g, r, c):
stack = [(r, c)]
while stack:
r, c = stack.pop()
if bad(g, r, c): continue
g[r][c] = '0'
stack.append((r + 1, c))
stack.append((r - 1, c))
stack.append((r, c + 1))
stack.append((r, c - 1))
Java
static boolean bad(char[][] g, int r, int c) {
if (r < 0 || r >= g.length) return true;
if (c < 0 || c >= g[0].length) return true;
return g[r][c] != '1';
}
static void sink(char[][] g, int r, int c) {
if (bad(g, r, c)) return;
g[r][c] = '0';
sink(g, r + 1, c); sink(g, r - 1, c);
sink(g, r, c + 1); sink(g, r, c - 1);
}
static void sink2(char[][] g, int r, int c) {
Deque<int[]> st = new ArrayDeque<>();
st.push(new int[]{r, c});
while (!st.isEmpty()) {
int[] p = st.pop();
r = p[0]; c = p[1];
if (bad(g, r, c)) continue;
g[r][c] = '0';
st.push(new int[]{r + 1, c});
st.push(new int[]{r - 1, c});
st.push(new int[]{r, c + 1});
st.push(new int[]{r, c - 1});
}
}
11000 Both versions count 3 islands here. Sinking from (0,0)
11000 clears the whole top-left block in one pass; the outer
00100 scan then finds the next '1' at (2,2), and the last
00011 one at (3,3).
Judgement
When NOT to convert
Converting is not automatically better. In an interview a clear recursive answer beats a tangled loop every time. Convert when one of two things is true: the depth can get large, or the interviewer asks you to.
Keep the recursionTree walks where the depth is about log n. A balanced tree of a million nodes is only 20 frames deep.
Divide and conquer: merge sort, quick sort. The loop version needs an explicit stack and reads far worse.
Backtracking: N-Queens, permutations, sudoku. The undo step after the call is exactly what the stack gives you free.
Anything you can write correctly in four lines.
Convert to a loopLinear recursion over n items, where n can be 100,000 and every item is a frame.
Grid or graph DFS: a full grid is rows × cols frames deep.
Tail recursion, like binary search: the loop is shorter anyway.
Anything that produced a "runtime error" verdict on a large hidden test case.
The honest test. Write the recursion first, because it is easier to get right. Then ask one question: how deep can this go on the worst input allowed by the constraints? If the answer is a few thousand, ship the recursion. If it is 100,000, convert.
Stack overflow
How deep can you actually go
😱
Aarav's Number of Islands solution passes 40 test cases and fails number 41 with RecursionError. He had changed nothing. Test 41 was simply a 300 × 300 grid of all land: 90,000 frames. Python stops at about a thousand.
You can raise Python's limit with sys.setrecursionlimit(30000)Verified: with the limit at 30000, a depth of 20,000 runs fine. But the real operating-system stack can still run out and kill the whole process, so treat this as a patch, not a fix.
You can raise Java's stack by running with -Xss8mMost online judges do not let you pass JVM flags, so on LeetCode or HackerRank this option is not available to you.
Safe depth in a coding test: under 1,000 in Python, under 5,000 in JavaIf the constraints say n can be 100,000 and your recursion uses one frame per item, convert before you submit. Do not wait for test 41.
Before you submit
Five mistakes, and the fix
- 1
No base case, or one the input can step straight pastThe classic is if n == 0 when something passes -1. Write the base case first, before the recursive call, and make it a range test: if n <= 0.
- 2
The base case sits after the recursive callThen it is never reached. def f(n): f(n-1); if n == 0: return recurses forever; run it and you get RecursionError immediately. Everything above the recursive call is a guard. Everything below it runs on the way back.
- 3
Recomputing instead of memoisingAny time the same argument can arrive twice, cache it. fib(30) went from 2,692,537 calls to 59 with a five-line memo. If the body calls itself more than once, ask this question before you write anything else.
- 4
Passing mutable state by reference, or as a default argumentdef f(n, acc=[]) reuses the same list on every call. Calling it twice returned [3, 2, 1] and then [3, 2, 1, 3, 2, 1]. Use acc=None and build the list inside the function.
- 5
Converting to a loop but keeping O(n) spaceTurning fib into a loop with a full dp array is still O(n) memory. If step i only needs steps i-1 and i-2, two variables are enough. Half the point of converting is the memory. Do not give it back.