Recursion in Depth Checkpoint
25 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Fix the mistakes
The slips that cost marks in this module. Spot each one, then check the fix.
This checkpoint mixes the whole module: base cases, the call stack, the recursion limit, halving and caching. For each task, decide first whether plain recursion, a cache, halving or a loop fits, then write it.
Check the base case first
Most recursion bugs are a missing or skipped base case. A bonus ladder pays 5 percent more each level, and level 0 is the start.
def bonus(base, level): if level <= 0: return base return bonus(base * 1.05, level - 1)
print(round(bonus(1000, 3), 2))print(bonus(1000, -2))Example 1 · Choosing a fix
def classify(depth, repeated): if repeated: return "cache it" if depth > 900: return "use a loop" return "plain recursion is fine"
print(classify(30, True))print(classify(5000, False))print(classify(20, False))cache it use a loop plain recursion is fine
What this code does
- Repeated sub-questions point to a cache.
- A depth above the limit points to a loop.
level <= 0 covers negative input too. With level == 0 the second call would never stop.
Know the depth
Depth decides if recursion is safe. A halving recursion stays near log n, while one call per item grows with n and hits the limit at 1000.
def count_down(n): if n == 0: return 0 return 1 + count_down(n - 1)
try: print(count_down(2000))except RecursionError: print("use a loop for depth 2000")Example 2 · Merge sort depth
def depth(n): if n <= 1: return 1 return 1 + depth(n - n // 2)
for size in (10, 1000, 1_000_000): print(size, depth(size))10 5 1000 11 1000000 21
What this code does
- Each call keeps the larger half, so this is the depth of merge sort.
- A million items need only 21 levels.
If the depth could exceed about 900, switch to a loop or an explicit stack.
Halve it or cache it
Two fixes cover most slow recursions. Halve the input when the parts are independent. Cache the answers when the same parts repeat.
from functools import lru_cache
@lru_cache(maxsize=None)def ways(n): if n <= 1: return 1 return ways(n - 1) + ways(n - 2)
print(ways(40))Example 3 · Fast power and the built-in
def power(base, n): if n == 0: return 1 half = power(base, n // 2) return half * half if n % 2 == 0 else half * half * base
print(power(3, 25) == 3 ** 25)print(power(2, 100))True 1267650600228229401496703205376
What this code does
- The result matches
**, which does the same job inside Python. - Python integers are exact, so 2 to the 100th has all 31 digits.
The cache makes this O(n). Fast power and merge sort use halving instead, because their parts do not repeat.
Module quiz
Questions from the whole module. Your first answer is your score.
Problems
Graded easy to hard, using everything from this module.
Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.
Exercise 1· Easy
Write a recursive digit_sum(n). Print digit_sum(98765).
35
Exercise 2· Easy
Write a recursive reverse(text) and print the reverse of invoice.
eciovni
Exercise 3· Medium
Write power(base, n) with the halving idea. Print power(2, 64).
18446744073709551616
Exercise 4· Medium
Write flatten(data) for nested lists and print the result for [[1, 2], [3, [4, [5]]], 6].
[1, 2, 3, 4, 5, 6]
Exercise 5· Medium
Write a cached paths(rows, cols) for a grid, moving right or down. Print paths(6, 6).
924
Exercise 6· Hard
Write merge_sort(items) with a hand-written merge. Print the sorted list for [9, 3, 7, 1, 8, 2].
[1, 2, 3, 7, 8, 9]
Exercise 7· Hard
Write total_to(n) as a loop and print total_to(1_000_000). A recursive version would fail at this size.
500000500000
Exercise 8· Hard
Write max_depth(data) for nested lists with an explicit stack of (list, depth) pairs. A flat list has depth 1. Print max_depth([1, [2, [3, [4]]], [5]]).
4
Interview questions
Questions interviewers ask on this topic.
Finish up
Mark complete & continue
Next: Must-do problems: Recursion in Depth