Exercises: Recursion

Contributors

Exercises: Recursion

These exercises progress from tracing recursive calls to designing original recursive solutions. Every function should include a proper base case and recursive case.

Difficulty Guide: - ⭐ Foundational (5-10 min each) - ⭐⭐ Intermediate (10-20 min each) - ⭐⭐⭐ Challenging (20-40 min each) - ⭐⭐⭐⭐ Advanced/Research (40+ min each)

Part A: Tracing and Understanding ⭐

A.1. Trace the execution of factorial(5) by hand. Write out each call, the value returned by each call, and draw the call stack at the moment the base case is reached.

A.2. For each of the following recursive functions, identify the base case and the recursive case. Then state what the function computes:

def mystery_a(n):
    if n == 0:
        return 0
    return n + mystery_a(n - 1)

def mystery_b(s):
    if len(s) == 0:
        return 0
    return 1 + mystery_b(s[1:])

def mystery_c(n):
    if n < 2:
        return n
    return mystery_c(n - 2)

A.3. The following function has a bug that causes infinite recursion. Identify the bug and fix it:

def countdown(n):
    print(n)
    countdown(n - 1)

A.4. Predict the output of the following code without running it. Then run it to check:

def foo(n):
    if n <= 0:
        return
    print(f"Before: {n}")
    foo(n - 1)
    print(f"After: {n}")

foo(3)

A.5. Explain in your own words what the "leap of faith" means in the context of recursion. Why is it impractical to trace every recursive call for fibonacci(30)?

A.6. For each scenario, state whether recursion or iteration is the better choice and explain why: - a) Summing numbers from 1 to 1000 - b) Finding a file in a deeply nested directory tree - c) Printing "Hello" 50 times - d) Processing a JSON document with arbitrary nesting depth

Part B: Writing Recursive Functions ⭐⭐

B.1. Write a recursive function power(base, exp) that computes base ** exp for non-negative integer exponents. Do not use the ** operator.

# Expected behavior:
# power(2, 10) → 1024
# power(3, 0) → 1
# power(5, 3) → 125

B.2. Write a recursive function count_digits(n) that returns the number of digits in a non-negative integer.

# Expected behavior:
# count_digits(12345) → 5
# count_digits(0) → 1
# count_digits(9) → 1
# count_digits(1000000) → 7

B.3. Write a recursive function remove_char(s, ch) that returns a new string with all occurrences of character ch removed.

# Expected behavior:
# remove_char("hello world", "l") → "heo word"
# remove_char("aabbcc", "b") → "aacc"
# remove_char("python", "z") → "python"

B.4. Write a recursive function list_max(lst) that returns the largest element in a non-empty list. Do not use the built-in max() function.

# Expected behavior:
# list_max([3, 7, 2, 9, 1]) → 9
# list_max([42]) → 42
# list_max([-5, -2, -8]) → -2

B.5. Write a recursive function binary_to_decimal(binary_str) that converts a binary string (like "1011") to its decimal equivalent (11).

# Expected behavior:
# binary_to_decimal("1011") → 11
# binary_to_decimal("1") → 1
# binary_to_decimal("0") → 0
# binary_to_decimal("11111111") → 255

B.6. Write a recursive function gcd(a, b) that computes the greatest common divisor of two positive integers using the Euclidean algorithm: gcd(a, b) = gcd(b, a % b), with base case gcd(a, 0) = a.

# Expected behavior:
# gcd(48, 18) → 6
# gcd(100, 25) → 25
# gcd(17, 13) → 1

Part C: Converting Between Recursion and Iteration ⭐⭐

C.1. Convert the following recursive function to an iterative version using a while loop:

def recursive_multiply(a, b):
    """Multiply a by b using only addition (b >= 0)."""
    if b == 0:
        return 0
    return a + recursive_multiply(a, b - 1)

C.2. Convert the following iterative function to a recursive version:

def iterative_sum_evens(n):
    """Sum all even numbers from 2 to n (inclusive)."""
    total = 0
    for i in range(2, n + 1, 2):
        total += i
    return total

C.3. The following function computes the nth triangular number iteratively. Write a recursive version:

def triangular_iter(n):
    """Return the nth triangular number: 1 + 2 + ... + n."""
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

Part D: Tree Recursion and Memoization ⭐⭐⭐

D.1. The Tribonacci sequence is like Fibonacci but uses three previous values: - trib(0) = 0, trib(1) = 0, trib(2) = 1 - trib(n) = trib(n-1) + trib(n-2) + trib(n-3) for n >= 3

Write both a naive recursive version and a memoized version. Time them for n=25 and n=35 to demonstrate the difference.

D.2. Write a recursive function subsets(lst) that returns all subsets of a list. For example, subsets([1, 2, 3]) should return [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]] (order doesn't matter).

Hint: the subsets of [1, 2, 3] are: all subsets of [2, 3] (without 1) PLUS all subsets of [2, 3] with 1 added to each.

D.3. Write a recursive function climb_stairs(n) that returns the number of distinct ways to climb n stairs if you can take 1 or 2 steps at a time. Use memoization to handle large values of n.

# Expected behavior:
# climb_stairs(1) → 1
# climb_stairs(2) → 2
# climb_stairs(3) → 3
# climb_stairs(5) → 8
# climb_stairs(30) → 1346269

D.4. Implement the "making change" problem from the Productive Struggle box. Write count_change(amount, coins) that returns the number of ways to make change for amount cents using the given coin denominations.

# Expected behavior:
# count_change(5, [1, 5]) → 2   (five pennies, or one nickel)
# count_change(10, [1, 5, 10]) → 4
# count_change(100, [1, 5, 10, 25, 50]) → 292

Part E: Recursive Data Structures ⭐⭐⭐

E.1. Write a recursive function deep_sum(data) that returns the sum of all numbers found anywhere inside a nested structure of lists and dictionaries.

# Expected behavior:
# deep_sum([1, [2, [3, 4]], 5]) → 15
# deep_sum({"a": 1, "b": {"c": 2, "d": [3, 4]}}) → 10
# deep_sum([]) → 0

E.2. Write a recursive function deep_copy(obj) that creates a deep copy of a nested data structure made of dicts, lists, and primitives. Do not use copy.deepcopy.

# Expected behavior:
original = {"a": [1, 2, {"b": 3}]}
copied = deep_copy(original)
copied["a"][2]["b"] = 99
# original["a"][2]["b"] should still be 3

E.3. Write a recursive function find_paths(tree, target) that returns all paths (as lists of keys) from the root to any occurrence of a target value in a nested dictionary.

data = {
    "dept": "Engineering",
    "teams": {
        "backend": {"lead": "Alice", "size": 5},
        "frontend": {"lead": "Bob", "size": 3},
        "devops": {"lead": "Alice", "size": 2},
    },
}

# find_paths(data, "Alice") → [["teams", "backend", "lead"], ["teams", "devops", "lead"]]

Part F: Anchor Example Extensions ⭐⭐⭐-⭐⭐⭐⭐

F.1. Extend the TaskFlow recursive search from Section 18.10 to support: - a) Searching by priority (find all "high" priority tasks anywhere in the tree) - b) A mark_done function that recursively finds a task by title and marks it as done - c) A prune_empty function that recursively removes categories with no tasks and no non-empty subcategories

F.2. Extend the Crypts of Pythonia dungeon generator to: - a) Include a monster field with random enemies (dragon, goblin, skeleton, None) - b) Write a recursive function count_monsters(dungeon) that returns the total number of monsters across all rooms - c) Write a recursive function find_treasure_path(dungeon, treasure_name) that returns the path (list of room names) from the entrance to the first room containing the specified treasure

F.3. (Research/Challenge) Implement a recursive descent parser for simple arithmetic expressions. The parser should handle addition, subtraction, multiplication, division, and parentheses, and follow standard precedence rules.

Example: parsing "3 + 4 * 2" should produce 11, and "(3 + 4) * 2" should produce 14.

Hint: define three mutually recursive functions — expression() handles +/-, term() handles *//, and factor() handles numbers and parentheses.

F.4. (Research/Challenge) The Tower of Hanoi is a classic recursive puzzle. You have three pegs and n disks of different sizes, all starting on peg A. Move all disks to peg C, following these rules: - Move only one disk at a time - Never place a larger disk on top of a smaller one

Write a recursive function hanoi(n, source, target, auxiliary) that prints the sequence of moves. Then answer: how many moves does it take for n disks? Express your answer as a formula.

# Expected output for hanoi(3, "A", "C", "B"):
# Move disk 1 from A to C
# Move disk 2 from A to B
# Move disk 1 from C to B
# Move disk 3 from A to C
# Move disk 1 from B to A
# Move disk 2 from B to C
# Move disk 1 from A to C