These are the notes for Python Coding Questions, episode 21: recursion questions. Recursion means a function that solves a problem by calling itself on a smaller copy of the same problem. We make it crash first, see exactly why, and then use it for three interview classics: power and sum of digits, all permutations of a string, and all subsets of a list.
Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real. Recursion tracebacks are about 3,000 lines long; we show the top, ..., and the last two lines, exactly as Python ends them.
Q1: The base case, power and sum of digits
Real-life example: you are in a long queue at the ration shop and want to know how many people are ahead of you. You can't see the front, so you ask the person ahead of you. They don't know either, so they ask the person ahead of them: the same question for a shorter queue. The person at the counter answers without asking anyone: "zero". Then the answers travel back, each person adding one.
Attempt 1: no base case
def people_ahead(n):
# ask the person ahead: "how many are ahead of you?"
return 1 + people_ahead(n - 1)
print(people_ahead(4))
Output:
Traceback (most recent call last):
File "main.py", line 5, in <module>
print(people_ahead(4))
~~~~~~~~~~~~^^^
File "main.py", line 3, in people_ahead
return 1 + people_ahead(n - 1)
~~~~~~~~~~~~^^^^^^^
File "main.py", line 3, in people_ahead
return 1 + people_ahead(n - 1)
~~~~~~~~~~~~^^^^^^^
File "main.py", line 3, in people_ahead
return 1 + people_ahead(n - 1)
~~~~~~~~~~~~^^^^^^^
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
Why it fails: nobody ever answers "zero". people_ahead(4) calls people_ahead(3), then 2, 1, 0, -1, -2... forever. Python stops it after about 1,000 calls with RecursionError: maximum recursion depth exceeded.
The fix: a base case
Every recursive function has two parts:
- the base case: an answer you know without calling yourself (the person at the counter says 0);
- the recursive case: call yourself on a smaller problem that is one step closer to the base case.
def people_ahead(n):
if n == 1: # base case: I'm at the counter
return 0
return 1 + people_ahead(n - 1)
print(people_ahead(4))
print(people_ahead(50))
Output:
3
49
The call stack
While people_ahead(4) waits for people_ahead(3), Python keeps it on the call stack. Each waiting call is a frame: its own copy of n and the place to continue.
people_ahead(4) waits for people_ahead(3)
people_ahead(3) waits for people_ahead(2)
people_ahead(2) waits for people_ahead(1)
people_ahead(1) returns 0 (the base case)
people_ahead(2) returns 1 + 0 = 1
people_ahead(3) returns 1 + 1 = 2
people_ahead(4) returns 1 + 2 = 3
Python allows about 1,000 frames by default (sys.getrecursionlimit()), so a runaway recursion stops with a clear error instead of using all the memory.
Power, the obvious way
Question: compute x ** n recursively, without **. The rule: x ** n = x * x ** (n - 1), and x ** 0 = 1.
def power(x, n):
if n == 0:
return 1
return x * power(x, n - 1)
print(power(2, 10))
print(power(3, 5))
print(len(str(power(2, 900))), "digits")
print(power(2, 5000))
Output:
1024
243
271 digits
Traceback (most recent call last):
File "main.py", line 9, in <module>
print(power(2, 5000))
~~~~~^^^^^^^^^
...
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
The base case is correct this time, and Python integers have no overflow (2 ** 900 has 271 digits). But n goes down by 1 per call, so power(2, 5000) needs 5,000 waiting frames, and the limit is about 1,000.
Fast power (exponentiation by squaring)
neven:x ** n = half * half, wherehalf = x ** (n // 2)nodd:x ** n = half * half * x
n halves every call: 5000, 2500, 1250, ..., 1, 0. That is about log₂ n calls (the number of times you can halve n), so the time is O(log n) multiplications and the stack stays tiny.
import sys
print(sys.getrecursionlimit())
calls = 0
def fast_power(x, n):
global calls
calls += 1
if n == 0:
return 1
half = fast_power(x, n // 2)
if n % 2 == 0:
return half * half
return half * half * x
print(fast_power(2, 10), fast_power(3, 5))
calls = 0
big = fast_power(2, 5000)
print(len(str(big)), "digits in", calls, "calls")
print(big == pow(2, 5000) == 2 ** 5000)
Output:
1000
1024 243
1506 digits in 14 calls
True
In real code use pow(x, n) or x ** n (they do the same squaring trick in C). pow(x, n, m) also does it modulo m.
Raising the limit is not the fix. sys.setrecursionlimit(10**6) lets the recursion go deeper, but every frame uses real memory on the C stack, and Python itself can crash (a "segmentation fault", no Python error at all). If the depth grows with the input size, write a loop.
Sum of digits, and the negative number trap
Question: the sum of the digits of n, recursively. The last digit is n % 10, the rest is n // 10.
def digit_sum(n):
if n == 0:
return 0
return n % 10 + digit_sum(n // 10)
print(digit_sum(1234))
print(digit_sum(9045))
print(digit_sum(-123))
Output:
10
18
Traceback (most recent call last):
File "main.py", line 8, in <module>
print(digit_sum(-123))
~~~~~~~~~^^^^^^
File "main.py", line 4, in digit_sum
...
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
Why it fails for -123: // is floor division: it rounds down, towards minus infinity (episode 1). So -123 // 10 is -13, not -12, and -1 // 10 is -1 again. The recursion never reaches 0.
Fix: use abs(n) first, and stop when one digit is left.
def digit_sum(n):
n = abs(n) # -123 -> 123
if n < 10: # one digit left
return n
return n % 10 + digit_sum(n // 10)
for n in [1234, 9045, -123, 0, 7]:
print(n, "->", digit_sum(n))
print(-123 // 10, -123 % 10)
Output:
1234 -> 10
9045 -> 18
-123 -> 6
0 -> 0
7 -> 7
-13 7
Complexity: one call per digit, so O(d) time and O(d) stack frames, where d is the number of digits (about log₁₀ n). Small, so recursion is safe here.
Q2: All permutations of a string
Real-life example: seating three friends, A, B and C, in a row for a group photo. A permutation is one ordering of all the items. Pick who sits in seat 1 (any of the three), then seat the rest the same way: the same problem with one friend fewer.
Attempt 1: nested loops
friends = "ABC"
for a in friends:
for b in friends:
for c in friends:
if a != b and b != c and a != c:
print(a + b + c, end=" ")
print()
friends = "ABCD" # one more friend joins
photos = []
for a in friends:
for b in friends:
for c in friends:
if a != b and b != c and a != c:
photos.append(a + b + c)
print(len(photos), photos[:4])
Output:
ABC ACB BAC BCA CAB CBA
24 ['ABC', 'ABD', 'ACB', 'ACD']
For "ABC" it is right. For "ABCD" we still get 24 results, but each photo has three people: friend number four is missing. Why: the number of loops is fixed when you write the code. Four letters need four loops, ten need ten. You can't write one loop per letter when you don't know the length.
The fix: choose one, then permute the rest
"ABC" -> "A" + perm("BC") = ABC, ACB
-> "B" + perm("AC") = BAC, BCA
-> "C" + perm("AB") = CAB, CBA
- Base case: a string of 0 or 1 letters has exactly one arrangement, itself.
- Recursive case: for each position
i, takes[i]first and put it in front of every permutation ofrest = s[:i] + s[i + 1:].
def permutations(s):
if len(s) <= 1: # 0 or 1 letters: one way
return [s]
result = []
for i in range(len(s)):
first = s[i]
rest = s[:i] + s[i + 1:] # all but seat 1
for p in permutations(rest):
result.append(first + p)
return result
print(permutations("ABC"))
print(len(permutations("ABCD")))
print(permutations("AAB"))
Output:
['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']
24
['AAB', 'ABA', 'AAB', 'ABA', 'BAA', 'BAA']
How many? n choices for seat 1, n - 1 for seat 2, ..., 1: that is n! ("n factorial"). 3! = 6, 4! = 24, 10! = 3,628,800.
The "AAB" problem: the two A's sit at different positions, so the code treats them as different friends, and swapping them gives the same string. Every result appears twice.
Unique permutations, and itertools
In each seat, remember the letters already tried (a set) and skip a repeat. itertools.permutations gives the same orderings as tuples; it also treats positions as different, so use set() when letters repeat.
def unique_perms(s):
if len(s) <= 1:
return [s]
result = []
used = set() # letters tried in this seat
for i in range(len(s)):
if s[i] in used:
continue
used.add(s[i])
for p in unique_perms(s[:i] + s[i + 1:]):
result.append(s[i] + p)
return result
print(unique_perms("AAB"))
print(len(unique_perms("AABB")))
from itertools import permutations
print(["".join(p) for p in permutations("ABC")])
print(len(set(permutations("AAB"))))
Output:
['AAB', 'ABA', 'BAA']
6
['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']
3
Complexity: n! results of n letters each, so O(n · n!) time and memory for the result list. The recursion is only n frames deep. 10 letters is fine; 15 letters is over a trillion results.
Q3: All subsets
Real-life example: a thali counter with dal, paneer and raita. A subset is any selection of the items, from none of them (the empty plate) to all of them. For each dish you make one decision: take it or leave it. Two choices, three times: 2 × 2 × 2 = 8 plates.
Attempt 1: a loop per size
items = ["dal", "paneer", "raita"]
plates = [[]]
for x in items: # one dish
plates.append([x])
for i in range(len(items)): # two dishes
for j in range(i + 1, len(items)):
plates.append([items[i], items[j]])
print(len(plates), "plates")
print(["dal", "paneer", "raita"] in plates)
Output:
7 plates
False
Seven plates, and the full thali is missing. One more loop for triples would fix three dishes, but every size needs its own loop, and the menu can have any number of dishes: the same problem as the photo.
The fix: take it or leave it
- Base case: no dishes left to decide: exactly one plate, the empty one,
[[]]. - Recursive case:
without= every subset of the rest (plates without the first dish);with_it= the first dish added to a copy of each of those (plates with it). Return both.
def subsets(items):
if not items: # nothing left to decide
return [[]]
first, rest = items[0], items[1:]
without = subsets(rest) # leave the first dish
with_it = [[first] + s for s in without] # or take it
return without + with_it
plates = subsets(["dal", "paneer", "raita"])
print(len(plates))
for p in plates:
print(p)
print(len(subsets(list(range(10)))))
Output:
8
[]
['raita']
['paneer']
['paneer', 'raita']
['dal']
['dal', 'raita']
['dal', 'paneer']
['dal', 'paneer', 'raita']
1024
Without recursion: a bitmask
Count from 0 to 2ⁿ - 1 in binary. Bit i says whether dish i is taken. mask >> i & 1 reads bit number i. This is called a bitmask.
items = ["dal", "paneer", "raita"]
n = len(items)
for mask in range(2 ** n): # 0 to 7
plate = [items[i] for i in range(n) if mask >> i & 1]
print(format(mask, "03b"), plate)
Output:
000 []
001 ['dal']
010 ['paneer']
011 ['dal', 'paneer']
100 ['raita']
101 ['dal', 'raita']
110 ['paneer', 'raita']
111 ['dal', 'paneer', 'raita']
Complexity: 2ⁿ subsets, each up to n items: O(n · 2ⁿ) time and memory. 20 items is about a million subsets; 30 items is over a billion, so this is only for small inputs. The recursion depth is only n.
When recursion is the wrong tool
A recursive total() that adds the first number to the total of the rest is correct, but its depth equals the list's length:
import sys
def total(nums):
if not nums:
return 0
return nums[0] + total(nums[1:])
print(total([5, 10, 20]))
print(sys.getrecursionlimit())
print(total(list(range(5000))))
Output:
35
1000
Traceback (most recent call last):
File "main.py", line 10, in <module>
print(total(list(range(5000))))
~~~~~^^^^^^^^^^^^^^^^^^^
File "main.py", line 6, in total
...
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
It also copies the list (nums[1:]) on every call: O(n²) work for a sum. A loop has no depth limit:
def total_loop(nums):
s = 0
for x in nums:
s += x
return s
print(total_loop(list(range(5000))))
print(total_loop(list(range(1_000_000))))
print(sum(range(1_000_000)))
Output:
12497500
499999500000
499999500000
Rule of thumb: if the depth stays small (log n, the length of a short word, the number of digits, the height of a balanced tree), recursion is often the clearest code. If the depth grows with the input size, use a loop. Python does not optimise tail calls away.
Common mistakes (and what you really see)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| no base case | RecursionError: maximum recursion depth exceeded |
the calls never stop | return a known answer first |
the call isn't smaller (f(n) calls f(n)) |
RecursionError |
it never gets closer to the base | change the argument every call |
power(x, n - 1) for big n |
RecursionError at n ≈ 1000 |
one frame per step | fast power: halve n |
digit_sum(-123) with n // 10 |
RecursionError |
-1 // 10 is -1 |
abs(n) first |
| nested loops for permutations | 3-letter results for "ABCD" | loops are fixed in number | choose one + recurse |
permutations("AAB") |
every result twice | equal letters at different positions | skip used letters / set() |
| a loop per subset size | the full set is missing | sizes need their own loops | take or leave, or a bitmask |
| forgetting to return the recursive result | None comes back |
the value is computed and dropped | return f(...) |
sys.setrecursionlimit(10**6) |
Python can crash with no error | frames use real stack memory | a loop |
Your turn: phone keypad words (solution)
Question: on an old phone keypad, 2 is abc, 3 is def, and so on. Write words(digits) that returns every letter combination a digit string can spell. words("23") gives 9 words.
Idea: the letters of the first digit, each put in front of every word of the rest. Base case: no digits left gives one empty word.
KEYS = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
def words(digits):
if not digits:
return [""]
rest = words(digits[1:])
return [ch + w for ch in KEYS[digits[0]] for w in rest]
print(words("23"))
print(len(words("79")), words("79")[:5])
print(words(""))
Output:
['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
16 ['pw', 'px', 'py', 'pz', 'qw']
['']
Complexity: up to 4ⁿ words of n letters: O(n · 4ⁿ). Note words("") returns [""] (one empty word); if the question says an empty input should give [], check for it before recursing.
Mini project: a thali combo menu
A canteen lists every possible combo of its side dishes with its price, cheapest first, and only shows combos under a budget. This uses the subsets function and a sort.
def subsets(items):
if not items:
return [[]]
rest = subsets(items[1:])
return rest + [[items[0]] + s for s in rest]
prices = {"dal": 40, "paneer": 90, "raita": 25, "papad": 10}
budget = 100
combos = []
for combo in subsets(list(prices)):
if combo: # skip the empty plate
cost = sum(prices[d] for d in combo)
if cost <= budget:
combos.append((cost, combo))
combos.sort() # cheapest first
for cost, combo in combos:
print(f"Rs {cost:>3} " + " + ".join(combo))
print(len(combos), "combos under Rs", budget)
Output:
Rs 10 papad
Rs 25 raita
Rs 35 raita + papad
Rs 40 dal
Rs 50 dal + papad
Rs 65 dal + raita
Rs 75 dal + raita + papad
Rs 90 paneer
Rs 100 paneer + papad
9 combos under Rs 100
Practice questions (with solutions)
1. Reverse a string recursively.
Solution
The reverse of s is the reverse of s[1:] followed by s[0]. Base case: an empty string.
def rev(s):
if s == "":
return ""
return rev(s[1:]) + s[0]
print(rev("chai"), rev("a"), repr(rev("")))
Output:
iahc a ''
O(n²) because of the slices; in real code use s[::-1].
2. Subsets that add up to a target. Print every subset of [2, 3, 5, 7] whose sum is 10.
Solution
Take or leave each number, carrying the remaining target. Stop early when the remaining target goes below 0 (all numbers are positive): this is called pruning.
def target_subsets(nums, target, chosen=()):
if target == 0:
print(list(chosen))
return
if target < 0 or not nums:
return
target_subsets(nums[1:], target - nums[0], chosen + (nums[0],)) # take
target_subsets(nums[1:], target, chosen) # leave
target_subsets([2, 3, 5, 7], 10)
Output:
[2, 3, 5]
[3, 7]
3. Tower of Hanoi for 3 discs. Move all discs from peg A to peg C, one at a time, never a big disc on a small one.
Solution
To move n discs from A to C: move n - 1 discs to B, move the biggest to C, move the n - 1 discs from B to C. 2ⁿ - 1 moves.
def hanoi(n, src, dst, via):
if n == 0:
return 0
moves = hanoi(n - 1, src, via, dst)
print(f"disc {n}: {src} -> {dst}")
return moves + 1 + hanoi(n - 1, via, dst, src)
print(hanoi(3, "A", "C", "B"), "moves")
Output:
disc 1: A -> C
disc 2: A -> B
disc 1: C -> B
disc 3: A -> C
disc 1: B -> A
disc 2: B -> C
disc 1: A -> C
7 moves
4. Count the digits of a number recursively (0 has 1 digit, negatives allowed).
Solution
def count_digits(n):
n = abs(n)
if n < 10:
return 1
return 1 + count_digits(n // 10)
print([count_digits(x) for x in [0, 7, 42, -12345, 10**20]])
Output:
[1, 1, 2, 5, 21]
5. Flatten a nested list recursively ([1, [2, [3, 4]], 5] gives [1, 2, 3, 4, 5]).
Solution
def flatten(x):
out = []
for item in x:
if isinstance(item, list):
out.extend(flatten(item)) # a list: flatten it too
else:
out.append(item)
return out
print(flatten([1, [2, [3, 4]], 5, []]))
Output:
[1, 2, 3, 4, 5]
The depth is the nesting depth, which is small for real data (episode 10 showed a stack version for very deep nesting).
Quick quiz
What does this print?
def f(n):
if n == 0:
return ""
return f(n // 2) + str(n % 2)
print(f(6))
(A) 011 (B) 110 (C) 6 (D) RecursionError
Answer
(B). f(6) = f(3) + "0", f(3) = f(1) + "1", f(1) = f(0) + "1", f(0) = "". Building back: "1" + "1" + "0" = "110", which is 6 in binary. The deepest call finishes first, so the last remainder computed comes out first.
def f(n):
if n == 0:
return ""
return f(n // 2) + str(n % 2)
print(f(6), f(13), bin(13))
Output:
110 1101 0b1101
Interview questions
- What is recursion? A function that calls itself on a smaller version of the same problem until it reaches a base case it can answer directly.
- What are the two parts of every recursive function? A base case (no recursive call) and a recursive case that moves closer to the base case.
- What causes
RecursionError? More nested calls than the recursion limit (about 1,000 by default): usually a missing or unreachable base case, or a depth that grows with the input. - What is the call stack? The list of function calls still waiting to finish; each is a frame with its own local variables.
- How does fast power work, and what is its complexity?
x ** n = (x ** (n // 2)) ** 2, timesxifnis odd; O(log n) multiplications. - How many permutations does a string of n distinct letters have? Subsets of n items? n! and 2ⁿ.
- How do you avoid duplicate permutations? Skip a letter already used at the current position (a set per level), or deduplicate with
set(). - Should you use
sys.setrecursionlimitto fix deep recursion? Usually no: frames use real stack memory and Python can crash. Rewrite as a loop or with an explicit stack. - Does Python optimise tail recursion? No. Every call keeps its frame, even if the recursive call is the last thing the function does.
- When is recursion a good choice? When the problem is naturally recursive (trees, nested data, permutations, subsets, divide and conquer) and the depth stays small.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Recursion | A function calling itself on a smaller problem | people_ahead(n - 1) |
| Recursive function | A function that uses recursion | power(x, n) |
| Base case | An answer known without calling yourself | if n == 0: return 1 |
| Recursive case | The part that calls itself on a smaller input | x * power(x, n - 1) |
| Call stack | The calls still waiting to finish | ahead(4) waits for ahead(3) |
| Frame | One waiting call: its locals and where to continue | n = 3 in ahead(3) |
RecursionError |
Raised when the call stack is deeper than the limit | maximum recursion depth exceeded |
| Recursion limit | The maximum depth Python allows (about 1,000) | sys.getrecursionlimit() |
sys.setrecursionlimit |
Changes the limit (risky) | sys.setrecursionlimit(5000) |
| Traceback | The error report showing the chain of calls | [Previous line repeated 996 more times] |
| Fast power | Squaring the half power: O(log n) | half * half * x |
| Exponentiation by squaring | Another name for fast power | pow(2, 5000) |
| log₂ n | How many times you can halve n to reach 1 | log₂ 1024 = 10 |
| Floor division | //, rounds down towards minus infinity |
-123 // 10 is -13 |
| Modulo | %, the remainder |
1234 % 10 is 4 |
abs() |
The absolute value (drops the minus sign) | abs(-123) is 123 |
| Permutation | One ordering of all the items | "BCA" |
| Factorial (n!) | 1 × 2 × ... × n, the number of permutations | 4! = 24 |
itertools.permutations |
Library function giving every ordering as tuples | permutations("ABC") |
| Subset | Any selection of items, from none to all | ["dal", "raita"] |
| Power set | The set of all subsets (2ⁿ of them) | 8 plates from 3 dishes |
| Bitmask | An integer whose bits mark which items are chosen | 0b101 = dal and raita |
>> and & |
Shift bits right / bitwise and | mask >> i & 1 |
| Pruning | Stopping a branch early when it can't succeed | if target < 0: return |
| Tail call | A recursive call that is the very last step (not optimised in Python) | return f(n - 1) |
| Divide and conquer | Split a problem, solve the parts, combine | merge sort (next episode) |
Summary
- Recursion solves a problem by calling itself on a smaller copy. It needs a base case and a recursive case that gets closer to it, or you get
RecursionError: maximum recursion depth exceeded. - Each waiting call is a frame on the call stack, and Python allows about 1,000 (
sys.getrecursionlimit()). Fix deep recursion by reducing the depth (fast power halvesn: O(log n)) or with a loop, not by raising the limit. - Watch for arguments that never reach the base case:
-1 // 10is-1, so takeabs(n)before digit tricks. - Permutations: choose each letter first and permute the rest; n! results, O(n · n!); skip repeated letters for unique ones;
itertools.permutations. - Subsets: take or leave each item; 2ⁿ results, O(n · 2ⁿ); or count through a bitmask.
- Next episode: searching and sorting questions: binary search for the first and last occurrence (and
bisect), merge sort, and sorting records by two keys.