MASTER YOUR LOGIC BUILDING:Phase 3 - Level 2: Advanced Recursion

Phase 3 - Level 2: Advanced Recursion

Why This Level Matters

You already know the basics: base case + recursive case. Now you'll apply that same "trust the smaller case" idea to numbers — counting digits, finding GCD, converting to binary. The mental model hasn't changed; only the way you shrink the problem has.

Think of a long number like 12345 as a stack of digits. Each recursive step peels off one layer (n // 10 removes the last digit) until you're left with a single digit or zero — your base case.

What You'll Learn

• Recursion on digits (count, sum, reverse)
• Classic math recursion: GCD and binary conversion
• How to spot the pattern: process one piece, recurse on the rest

The Digit-Shrinking Pattern

Most number problems follow one recipe:

def work_on_number(n):
    if n == 0:              # base case — nothing left
        return 0            # or 1, or "", depending on problem
    last_part = n % 10      # the "current" digit (optional)
    rest = n // 10          # the smaller problem
    return ??? + work_on_number(rest)

Count digits example:

def count_digits(n):
    if n == 0:
        return 0
    return 1 + count_digits(n // 10)

You trust: "count_digits(1234) correctly returns 4, so count_digits(12345) is 1 + 4 = 5."

GCD — Recursion That Swaps Roles

The Euclidean algorithm is elegant: instead of n - 1, you replace (a, b) with (b, a % b)) until b` becomes 0.

def gcd(a, b):
    if b == 0:        # base: no remainder left
        return a
    return gcd(b, a % b)  # smaller pair each time

Trust the smaller case: gcd(48, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6.

Binary Conversion — Build From the Inside Out

def to_binary(n):
    if n == 0:
        return ""
    return to_binary(n // 2) + str(n % 2)

Recursion gives you the left digits first; you append the current remainder (n % 2) on the right. Like nesting dolls opened from the biggest inward.

Step-by-Step Thinking Process

1. What is "one step smaller"? — Remove a digit (n // 10), halve the number (n // 2), or swap GCD arguments.
2. What's the base case? — n == 0, single digit, or `b == 0).
3. What do I do with the current step? — Add 1, multiply, append a character, etc.
4. Edge cases: Use abs(n) for negatives; handle n == 0 separately when counting digits.

Common Mistakes & Tips

• Forgetting `n == 0` — counting digits of 0 is a special case (0 has 1 digit, or you handle it before calling).
• Mixing up `//` and `%` — // shrinks the number; % gives you the last digit.
• Not trusting the return value — you don't need to manually expand gcd(b, a % b); just write the formula.
• Tip: Draw one level: "For 12345, I add 1 to count_digits(1234)." That's enough.

Practice Focus

Try the examples below — Count Digits reinforces the peel-one-digit pattern, and GCD shows recursion where the "smaller problem" looks different but still shrinks every time. Modify inputs and trace just two levels by hand, then trust the rest.