SyntaxPilot
Courses/Python Coding Questions/Lesson 21
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python Coding Questions · Lesson 21 of 30

Recursion questions

power and sum of digits recursivelyall permutations of a stringall subsets; RecursionError and sys.getrecursionlimit

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)

  • n even: x ** n = half * half, where half = x ** (n // 2)
  • n odd: 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, take s[i] first and put it in front of every permutation of rest = 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

  1. 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.
  2. 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.
  3. 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.
  4. What is the call stack? The list of function calls still waiting to finish; each is a frame with its own local variables.
  5. How does fast power work, and what is its complexity? x ** n = (x ** (n // 2)) ** 2, times x if n is odd; O(log n) multiplications.
  6. How many permutations does a string of n distinct letters have? Subsets of n items? n! and 2ⁿ.
  7. How do you avoid duplicate permutations? Skip a letter already used at the current position (a set per level), or deduplicate with set().
  8. Should you use sys.setrecursionlimit to fix deep recursion? Usually no: frames use real stack memory and Python can crash. Rewrite as a loop or with an explicit stack.
  9. Does Python optimise tail recursion? No. Every call keeps its frame, even if the recursive call is the last thing the function does.
  10. 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 halves n: O(log n)) or with a loop, not by raising the limit.
  • Watch for arguments that never reach the base case: -1 // 10 is -1, so take abs(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.