The Rules
3 min- Every problem solved with a recursive function. No
for/whileloops in your solution (helpers may have them). - Each function has at least one base case at the top and shrinks the input in its recursive call.
- Solve at least 4 of the 5; all 5 puts you in great shape for the Dungeon Quest capstone.
Problem 1 · Palindrome Check
8 minWrite is_palindrome(s) that returns True if s reads the same forwards and backwards. Ignore case and non-letter characters.
assert is_palindrome("racecar") assert is_palindrome("Was it a car or a cat I saw?") assert not is_palindrome("hello") assert is_palindrome("") # empty is vacuously a palindrome
Hint · structure
Normalise once (strip non-letters, lower-case). Then recursively check that s[0] == s[-1] and the middle s[1:-1] is also a palindrome. Base cases: length ≤ 1.
Problem 2 · Deep Flatten
8 minWrite flatten(nested) that takes an arbitrarily-deep nested list and returns a flat list of all the leaf elements.
assert flatten([1, [2, 3], [4, [5, 6], 7]]) == [1, 2, 3, 4, 5, 6, 7] assert flatten([1, [2, [3, [4, [5]]]]]) == [1, 2, 3, 4, 5] assert flatten([]) == []
Hint · structure
For each item: if it's a list, recursively flatten it and add the result; otherwise add it as-is. Use isinstance(item, list) to test. Build the result with + on lists.
Problem 3 · Directory Walk
8 minA simulated filesystem is given as a nested dict:
fs = { "name": "root", "children": [ {"name": "Documents", "children": [ {"name": "report.docx", "children": []}, {"name": "photo.jpg", "children": []}, ]}, {"name": "Music", "children": [ {"name": "albums", "children": [ {"name": "song1.mp3", "children": []}, {"name": "song2.mp3", "children": []}, ]}, ]}, {"name": "todo.txt", "children": []}, ], }
Write all_files(node, prefix="") that returns a list of full paths to every leaf (a node with empty children).
all_files(fs) # → [ # 'root/Documents/report.docx', # 'root/Documents/photo.jpg', # 'root/Music/albums/song1.mp3', # 'root/Music/albums/song2.mp3', # 'root/todo.txt', # ]
Hint · structure
Build the current path as prefix + "/" + node["name"] (or just node["name"] if prefix is empty). If children is empty, return [that path]. Otherwise recurse on each child with the current path as the new prefix; concatenate the results.
Problem 4 · Binary Search
8 minGiven a sorted list and a target, return the index of the target or -1 if not present. Use recursion — no loops.
assert binary_search([1, 3, 5, 7, 9, 11], 7) == 3 assert binary_search([1, 3, 5, 7, 9, 11], 4) == -1 assert binary_search([], 1) == -1 assert binary_search([42], 42) == 0
Hint · structure
Three-parameter helper: (lst, target, lo, hi). Base: if lo > hi, not found, return -1. Compute mid = (lo + hi) // 2. If lst[mid] == target, return mid. If less, recurse on right half (lo = mid + 1). If greater, recurse on left half (hi = mid - 1). The public function calls the helper with lo=0, hi=len(lst)-1.
Problem 5 · Change-Making
8 minGiven an amount and a list of coin denominations, return the minimum number of coins needed to make exactly that amount. Return -1 if impossible.
assert min_coins(11, [1, 5, 6]) == 2 # 5 + 6 assert min_coins(7, [1, 3, 4]) == 2 # 3 + 4 assert min_coins(0, [1, 5]) == 0 assert min_coins(3, [2]) == -1
Hint · structure
For each coin: if it fits (amount >= coin), recurse on amount - coin and add 1 to the result. Take the minimum across all coin choices. Base cases: amount == 0 → 0. If amount < 0 → infinity (or a sentinel). Use @lru_cache for speed — without it the function is exponentially slow on bigger inputs.
Putting It All Together · recursion_lab.py
8 minAssemble all five problems into one file with tests.
Show one complete solution
# recursion_lab.py — five recursive solutions from functools import lru_cache # 1 — Palindrome def is_palindrome(s): cleaned = "".join(ch.lower() for ch in s if ch.isalpha()) return _pal_recursive(cleaned) def _pal_recursive(s): if len(s) <= 1: return True if s[0] != s[-1]: return False return _pal_recursive(s[1:-1]) # 2 — Deep flatten def flatten(nested): if nested == []: return [] head, *tail = nested head_part = flatten(head) if isinstance(head, list) else [head] return head_part + flatten(tail) # 3 — Directory walk def all_files(node, prefix=""): path = node["name"] if not prefix else prefix + "/" + node["name"] if not node["children"]: return [path] # Concatenate the results from each child if len(node["children"]) == 1: return all_files(node["children"][0], path) head, *rest = node["children"] return all_files(head, path) + all_files({"name": "", "children": rest}, prefix) # (Cleaner: use a small loop. We're cheating slightly on the "no loops" rule — # the helper above shows pure recursion if you really want it.) # Cleaner version with one loop (acceptable): def all_files_v2(node, prefix=""): path = node["name"] if not prefix else prefix + "/" + node["name"] if not node["children"]: return [path] result = [] for child in node["children"]: result += all_files_v2(child, path) return result # 4 — Binary search def binary_search(lst, target): return _bsearch(lst, target, 0, len(lst) - 1) def _bsearch(lst, target, lo, hi): if lo > hi: return -1 mid = (lo + hi) // 2 if lst[mid] == target: return mid if lst[mid] < target: return _bsearch(lst, target, mid + 1, hi) return _bsearch(lst, target, lo, mid - 1) # 5 — Change-making INF = float("inf") @lru_cache(maxsize=None) def _min_coins(amount, coins): if amount == 0: return 0 if amount < 0: return INF best = INF for coin in coins: result = _min_coins(amount - coin, coins) if result + 1 < best: best = result + 1 return best def min_coins(amount, coins): result = _min_coins(amount, tuple(coins)) # tuple for hash return -1 if result == INF else result # --- tests --- if __name__ == "__main__": assert is_palindrome("racecar") assert is_palindrome("Was it a car or a cat I saw?") assert not is_palindrome("hello") assert is_palindrome("") assert flatten([1, [2, 3], [4, [5, 6], 7]]) == [1, 2, 3, 4, 5, 6, 7] assert flatten([1, [2, [3, [4, [5]]]]]) == [1, 2, 3, 4, 5] assert flatten([]) == [] fs = { "name": "root", "children": [ {"name": "Documents", "children": [ {"name": "report.docx", "children": []}, ]}, {"name": "todo.txt", "children": []}, ], } assert all_files_v2(fs) == ["root/Documents/report.docx", "root/todo.txt"] assert binary_search([1, 3, 5, 7, 9, 11], 7) == 3 assert binary_search([1, 3, 5, 7, 9, 11], 4) == -1 assert binary_search([], 1) == -1 assert min_coins(11, [1, 5, 6]) == 2 assert min_coins(0, [1, 5]) == 0 assert min_coins(3, [2]) == -1 print("All 5 problems pass.")
Non-negotiables: each function recursive at its core. _min_coins needs memoisation — without it, larger inputs run for minutes. The change-making problem is a classic intro to dynamic programming.
Recap · The Last 36 Lessons
5 minThree-quarters of Level 3 in your fingers now.
OOP foundations PY-L3-01..06 Inheritance + polymorphism PY-L3-07..13 Dunders + Pet Shop PY-L3-14..17 Decorators PY-L3-18..19 Functional PY-L3-20..24 Iterators + generators PY-L3-25..29 Functional Olympics PY-L3-30 Recursion fundamentals PY-L3-31..32 Recursive art trilogy PY-L3-33..35 Recursion Lab PY-L3-36
You can now design classes, write functional pipelines, build generators, and reason recursively. That's the trio that powers most senior Python code. Twelve more lessons to go — searching/sorting/Big-O, then the data-structures arc (stack, queue, linked list), then the Dungeon Quest capstone and PCEP exam prep.
PY-L3-37 starts the algorithms arc. Linear search, binary search, bubble sort, insertion sort. Then complexity in human terms ("why O(n²) is too slow for a million items"). Then your own data structures.
Homework
4 minAdd three more recursive problems to your recursion_lab.py:
count_paths(rows, cols)— count grid paths from top-left to bottom-right moving only right or down. Use memoisation.flatten_dict(d, parent_key="")— flatten a nested dict to a single-level dict with dotted keys. Example:{"a": {"b": 1}}→{"a.b": 1}.permutations(s)— return a list of all permutations of the characters in a string.permutations("abc")= 6 strings.
Sample · three more recursive solutions
from functools import lru_cache @lru_cache(maxsize=None) def count_paths(rows, cols): if rows == 0 or cols == 0: return 1 return count_paths(rows - 1, cols) + count_paths(rows, cols - 1) def flatten_dict(d, parent_key=""): if not isinstance(d, dict): return {parent_key: d} result = {} for key, value in d.items(): new_key = key if not parent_key else parent_key + "." + key result.update(flatten_dict(value, new_key)) return result def permutations(s): if len(s) <= 1: return [s] result = [] for i in range(len(s)): rest = s[:i] + s[i+1:] for p in permutations(rest): result.append(s[i] + p) return result print(count_paths(2, 2)) # 6 print(flatten_dict({"a": {"b": 1, "c": {"d": 2}}, "e": 3})) # {'a.b': 1, 'a.c.d': 2, 'e': 3} print(permutations("abc")) # 6 strings
Non-negotiables: each function recursive. count_paths needs lru_cache — it's exponential without it. permutations uses the classic "pick one item, recurse on the rest" pattern.