Recursion Workshop · Solo Project A Opens

What this session is for

• Make the two ingredients of recursion automatic
• Run your own recursion-versus-loop comparison
• Understand the basic backtracking pattern
• Start solo project A

Core problems

7-1 Counting digits recursively

Implement count_digits(n: int) -> int, counting the digits of a non-negative integer.

count_digits(0)     →  1
count_digits(7)     →  1
count_digits(12345) →  5

7-2 Reversing a string recursively

Implement reverse_string(s: str) -> str. [::-1], reversed() and loops are all off limits.

reverse_string("")      →  ""
reverse_string("a")     →  "a"
reverse_string("hello") →  "olleh"

7-3 Palindromes

Implement is_palindrome(s: str) -> bool recursively, testing whether a string reads the same in both directions.

is_palindrome("")      →  True
is_palindrome("a")     →  True
is_palindrome("abba")  →  True
is_palindrome("abc")   →  False

7-4 Flattening a nested list

Implement flatten(items: list) -> list[int], collapsing a list nested to any depth into one dimension.

flatten([1, [2, [3, [4]]]])      →  [1, 2, 3, 4]
flatten([])                       →  []
flatten([[], [1], [[2], [3]]])    →  [1, 2, 3]

7-5 Recursion versus a loop

Implement “sum of digits” twice:

• sum_digits_rec(n: int) -> int — recursively
• sum_digits_loop(n: int) -> int — with a loop (you wrote this in Lab 4)

Then answer in your submission notes:

1. Which is shorter? Which is easier to follow?
2. Run both on n = 10**1000 (a thousand-digit number). What happens, and why?

7-6 Counting coin combinations

Given a list of denominations and an amount, count recursively how many ways there are to make it (order does not matter).

def count_ways(amount: int, coins: list[int]) -> int:
    ...

count_ways(5, [1, 2, 5])    →  4     # 5 / 2+2+1 / 2+1+1+1 / 1×5
count_ways(0, [1, 2, 5])    →  1     # taking nothing counts as one way
count_ways(3, [2])          →  0

---

Solo Project A: Towers of Hanoi, Visualized

Worth 7.5% of the final grade (projects A and B are 15% together) Due next Sunday, 23:59

Background

In Lab 4 you used a loop to compute the minimum number of moves. In L7 you used recursion to produce the moves themselves. This project finishes the job.

What to build

A module containing the following functions. The signatures must match exactly — the platform calls them as written:

def hanoi_moves(n: int) -> list[tuple[int, str, str]]:
    """Return the sequence of moves, each one (disk number, from peg, to peg).
    Pegs are "A", "B" and "C"; start at A and finish at C."""

def is_valid_sequence(n: int, moves: list[tuple[int, str, str]]) -> bool:
    """Check that a move sequence is legal: one disk at a time, never a larger
    disk onto a smaller one, and every disk ends up on C."""

def render(n: int, moves: list[tuple[int, str, str]]) -> str:
    """Draw the whole process as text and return it as one multi-line string."""

Marks

The report

At most one page, answering three questions:

1. What checks did you build into is_valid_sequence? Which illegal situation does each one catch?
2. Why did you draw it that way in render? What alternatives did you consider and reject?
3. How large can n get? Try it, and say what the limiting factor is — time, memory, or recursion depth.

Before you submit

• All six core problems are annotated
• 7-1 tested with n = 0
• 7-3 handles both base cases
• Both questions in 7-5 answered in your notes
• Project A: all three signatures match the brief
• Project A: is_valid_sequence tested against illegal sequences
• Project A: the report answers all three questions