Common Algorithms

Recursion Examples

Real-world applications frequently need to process nested data structures, calculate mathematical sequences, or search through hierarchical information. This page demonstrates practical recursive algorithms that solve common programming challenges like summing lists, reversing strings, and computing greatest common divisors.

This page demonstrates practical applications of recursion beyond the basic factorial and Fibonacci examples.

Common Patterns

  1. List processing: recursively process each element
  2. String manipulation: work on substring recursively
  3. Mathematical computations: divide problem into parts
  4. Tree traversal: process node, recurse on children

Key Techniques

  • Head recursion: recursive call before processing
  • Tail recursion: recursive call as last operation
  • Multiple recursion: multiple recursive calls
  • Helper functions: wrapper with extra parameters
head_recursion Recursive call happens before processing the current element
tail_recursion Recursive call is the last operation, enabling potential optimization

Sum of List

numbers
list_sum.py
Replay: real traced execution (multi-file project)
# Recursive sum of list


def sum_list(lst):
    """Sum list recursively"""
    # Base case: empty list
    if not lst:
        return 0

    # Recursive case: first + sum of rest
    return lst[0] + sum_list(lst[1:])


def sum_by_index(lst, index=0):
    """Sum using index parameter"""
    # Base case: reached end
    if index >= len(lst):
        return 0

    # Recursive: current + rest
    return lst[index] + sum_by_index(lst, index + 1)


def sum_tail_recursive(lst, accumulator=0):
    """Tail recursive sum"""
    # Base case
    if not lst:
        return accumulator

    # Tail recursion: recursive call is last operation
    return sum_tail_recursive(lst[1:], accumulator + lst[0])


# Test list sum
numbers = [1, 2, 3, 4, 5]

print("List:", numbers)
print("Sum (basic): ", sum_list(numbers))
print("Sum (index): ", sum_by_index(numbers))
print("Sum (tail):  ", sum_tail_recursive(numbers))

values = [10, 20, 30, 40]
print("\nList:", values)
print("Sum:", sum_list(values))


# Recursive sum of list


def sum_list(lst):
    """Sum list recursively"""
    # Base case: empty list
    if not lst:
        return 0

    # Recursive case: first + sum of rest
    return lst[0] + sum_list(lst[1:])


def sum_by_index(lst, index=0):
    """Sum using index parameter"""
    # Base case: reached end
    if index >= len(lst):
        return 0

    # Recursive: current + rest
    return lst[index] + sum_by_index(lst, index + 1)


def sum_tail_recursive(lst, accumulator=0):
    """Tail recursive sum"""
    # Base case
    if not lst:
        return accumulator

    # Tail recursion: recursive call is last operation
    return sum_tail_recursive(lst[1:], accumulator + lst[0])


# Test list sum
numbers = [2, 4, 6]

print("List:", numbers)
print("Sum (basic): ", sum_list(numbers))
print("Sum (index): ", sum_by_index(numbers))
print("Sum (tail):  ", sum_tail_recursive(numbers))

values = [10, 20, 30, 40]
print("\nList:", values)
print("Sum:", sum_list(values))


# Recursive sum of list


def sum_list(lst):
    """Sum list recursively"""
    # Base case: empty list
    if not lst:
        return 0

    # Recursive case: first + sum of rest
    return lst[0] + sum_list(lst[1:])


def sum_by_index(lst, index=0):
    """Sum using index parameter"""
    # Base case: reached end
    if index >= len(lst):
        return 0

    # Recursive: current + rest
    return lst[index] + sum_by_index(lst, index + 1)


def sum_tail_recursive(lst, accumulator=0):
    """Tail recursive sum"""
    # Base case
    if not lst:
        return accumulator

    # Tail recursion: recursive call is last operation
    return sum_tail_recursive(lst[1:], accumulator + lst[0])


# Test list sum
numbers = [10, -5, 15]

print("List:", numbers)
print("Sum (basic): ", sum_list(numbers))
print("Sum (index): ", sum_by_index(numbers))
print("Sum (tail):  ", sum_tail_recursive(numbers))

values = [10, 20, 30, 40]
print("\nList:", values)
print("Sum:", sum_list(values))

  1. numbers ← [1, 2, 3, 4, 5]

    34# Test list sum35numbers→ [1, 2, 3, 4, 5] = [1, 2, 3, 4, 5]36#@numbers=[2, 4, 6], [10, -5, 15]3738print("List:", numbers[1, 2, 3, 4, 5])39print("Sum (basic): ", sum_list(numbers[1, 2, 3, 4, 5]))40print("Sum (index): ", sum_by_index(numbers))
    outputList: [1, 2, 3, 4, 5]

  2. def sum_list(lst):

    pass 1 of 11
    4def sum_list(lst[1, 2, 3, 4, 5]):5    """Sum list recursively"""6    # Base case: empty list7    if not lst:8        return 0910    # Recursive case: first + sum of rest11    return lst[0]1 + sum_list(lst[1:][2, 3, 4, 5])
    All 11 passes — pass 1 is the card above
    passlstlst[0]lst[1:]
    1[1, 2, 3, 4, 5]1[2, 3, 4, 5]
    2[2, 3, 4, 5]2[3, 4, 5]
    3[3, 4, 5]3[4, 5]
    4[4, 5]4[5]
    5[5]5[]
    6[]——
    7[10, 20, 30, 40]10[20, 30, 40]
    8[20, 30, 40]20[30, 40]
    9[30, 40]30[40]
    10[40]40[]
    11[]——

  3. if not lst:

    pass 1 of 2
    6# Base case: empty list7if not lst[]:8    return 0

  4. print("Sum (basic): ", sum_list(numbers))

    38print("List:", numbers)39print("Sum (basic): ", sum_list(numbers[1, 2, 3, 4, 5]))40print("Sum (index): ", sum_by_index(numbers[1, 2, 3, 4, 5]))41print("Sum (tail):  ", sum_tail_recursive(numbers))
    outputSum (basic):  15

  5. def sum_by_index(lst, index=0):

    pass 1 of 6
    14def sum_by_index(lst[1, 2, 3, 4, 5], index0=0):15    """Sum using index parameter"""16    # Base case: reached end17    if index >= len(lst):18        return 01920    # Recursive: current + rest21    return lst[index]1 + sum_by_index(lst[1, 2, 3, 4, 5], index0 + 1)
    All 6 passes — pass 1 is the card above
    passindexlst[index]
    101
    212
    323
    434
    545
    65—

  6. if index >= len(lst):

    16# Base case: reached end17if index5 >= len(lst[1, 2, 3, 4, 5]):18    return 0

  7. print("Sum (index): ", sum_by_index(numbers))

    39print("Sum (basic): ", sum_list(numbers))40print("Sum (index): ", sum_by_index(numbers[1, 2, 3, 4, 5]))41print("Sum (tail):  ", sum_tail_recursive(numbers[1, 2, 3, 4, 5]))
    outputSum (index):  15

  8. def sum_tail_recursive(lst, accumulator=0):

    pass 1 of 6
    24def sum_tail_recursive(lst[1, 2, 3, 4, 5], accumulator0=0):25    """Tail recursive sum"""26    # Base case27    if not lst:28        return accumulator2930    # Tail recursion: recursive call is last operation31    return sum_tail_recursive(lst[1:][2, 3, 4, 5], accumulator0 + lst[0]1)
    All 6 passes — pass 1 is the card above
    passlstaccumulatorlst[1:]lst[0]
    1[1, 2, 3, 4, 5]0[2, 3, 4, 5]1
    2[2, 3, 4, 5]1[3, 4, 5]2
    3[3, 4, 5]3[4, 5]3
    4[4, 5]6[5]4
    5[5]10[]5
    6[]15——

  9. if not lst:

    26# Base case27if not lst[]:28    return accumulator15

  10. values ← [10, 20, 30, 40]

    40print("Sum (index): ", sum_by_index(numbers))41print("Sum (tail):  ", sum_tail_recursive(numbers[1, 2, 3, 4, 5]))4243values→ [10, 20, 30, 40] = [10, 20, 30, 40]44print("\nList:", values[10, 20, 30, 40])45print("Sum:", sum_list(values[10, 20, 30, 40]))
    outputSum (tail):   15

List: [10, 20, 30, 40]

  11. if not lst:

    pass 2 of 2
    6# Base case: empty list7if not lst[]:8    return 0

  12. print("Sum:", sum_list(values))

    44print("\nList:", values)45print("Sum:", sum_list(values[10, 20, 30, 40]))
    outputSum: 100

  1. numbers ← [2, 4, 6]

    34# Test list sum35numbers→ [2, 4, 6] = [2, 4, 6]3637print("List:", numbers[2, 4, 6])38print("Sum (basic): ", sum_list(numbers[2, 4, 6]))39print("Sum (index): ", sum_by_index(numbers))
    outputList: [2, 4, 6]

  2. def sum_list(lst):

    pass 1 of 9
    4def sum_list(lst[2, 4, 6]):5    """Sum list recursively"""6    # Base case: empty list7    if not lst:8        return 0910    # Recursive case: first + sum of rest11    return lst[0]2 + sum_list(lst[1:][4, 6])
    All 9 passes — pass 1 is the card above
    passlstlst[0]lst[1:]
    1[2, 4, 6]2[4, 6]
    2[4, 6]4[6]
    3[6]6[]
    4[]——
    5[10, 20, 30, 40]10[20, 30, 40]
    6[20, 30, 40]20[30, 40]
    7[30, 40]30[40]
    8[40]40[]
    9[]——

  3. if not lst:

    pass 1 of 2
    6# Base case: empty list7if not lst[]:8    return 0

  4. print("Sum (basic): ", sum_list(numbers))

    37print("List:", numbers)38print("Sum (basic): ", sum_list(numbers[2, 4, 6]))39print("Sum (index): ", sum_by_index(numbers[2, 4, 6]))40print("Sum (tail):  ", sum_tail_recursive(numbers))
    outputSum (basic):  12

  5. def sum_by_index(lst, index=0):

    pass 1 of 4
    14def sum_by_index(lst[2, 4, 6], index0=0):15    """Sum using index parameter"""16    # Base case: reached end17    if index >= len(lst):18        return 01920    # Recursive: current + rest21    return lst[index]2 + sum_by_index(lst[2, 4, 6], index0 + 1)
    All 4 passes — pass 1 is the card above
    passindexlst[index]
    102
    214
    326
    43—

  6. if index >= len(lst):

    16# Base case: reached end17if index3 >= len(lst[2, 4, 6]):18    return 0

  7. print("Sum (index): ", sum_by_index(numbers))

    38print("Sum (basic): ", sum_list(numbers))39print("Sum (index): ", sum_by_index(numbers[2, 4, 6]))40print("Sum (tail):  ", sum_tail_recursive(numbers[2, 4, 6]))
    outputSum (index):  12

  8. def sum_tail_recursive(lst, accumulator=0):

    pass 1 of 4
    24def sum_tail_recursive(lst[2, 4, 6], accumulator0=0):25    """Tail recursive sum"""26    # Base case27    if not lst:28        return accumulator2930    # Tail recursion: recursive call is last operation31    return sum_tail_recursive(lst[1:][4, 6], accumulator0 + lst[0]2)
    All 4 passes — pass 1 is the card above
    passlstaccumulatorlst[1:]lst[0]
    1[2, 4, 6]0[4, 6]2
    2[4, 6]2[6]4
    3[6]6[]6
    4[]12——

  9. if not lst:

    26# Base case27if not lst[]:28    return accumulator12

  10. values ← [10, 20, 30, 40]

    39print("Sum (index): ", sum_by_index(numbers))40print("Sum (tail):  ", sum_tail_recursive(numbers[2, 4, 6]))4142values→ [10, 20, 30, 40] = [10, 20, 30, 40]43print("\nList:", values[10, 20, 30, 40])44print("Sum:", sum_list(values[10, 20, 30, 40]))
    outputSum (tail):   12

List: [10, 20, 30, 40]

  11. if not lst:

    pass 2 of 2
    6# Base case: empty list7if not lst[]:8    return 0

  12. print("Sum:", sum_list(values))

    43print("\nList:", values)44print("Sum:", sum_list(values[10, 20, 30, 40]))
    outputSum: 100

  1. numbers ← [10, -5, 15]

    34# Test list sum35numbers→ [10, -5, 15] = [10, -5, 15]3637print("List:", numbers[10, -5, 15])38print("Sum (basic): ", sum_list(numbers[10, -5, 15]))39print("Sum (index): ", sum_by_index(numbers))
    outputList: [10, -5, 15]

  2. def sum_list(lst):

    pass 1 of 9
    4def sum_list(lst[10, -5, 15]):5    """Sum list recursively"""6    # Base case: empty list7    if not lst:8        return 0910    # Recursive case: first + sum of rest11    return lst[0]10 + sum_list(lst[1:][-5, 15])
    All 9 passes — pass 1 is the card above
    passlstlst[0]lst[1:]
    1[10, -5, 15]10[-5, 15]
    2[-5, 15]-5[15]
    3[15]15[]
    4[]——
    5[10, 20, 30, 40]10[20, 30, 40]
    6[20, 30, 40]20[30, 40]
    7[30, 40]30[40]
    8[40]40[]
    9[]——

  3. if not lst:

    pass 1 of 2
    6# Base case: empty list7if not lst[]:8    return 0

  4. print("Sum (basic): ", sum_list(numbers))

    37print("List:", numbers)38print("Sum (basic): ", sum_list(numbers[10, -5, 15]))39print("Sum (index): ", sum_by_index(numbers[10, -5, 15]))40print("Sum (tail):  ", sum_tail_recursive(numbers))
    outputSum (basic):  20

  5. def sum_by_index(lst, index=0):

    pass 1 of 4
    14def sum_by_index(lst[10, -5, 15], index0=0):15    """Sum using index parameter"""16    # Base case: reached end17    if index >= len(lst):18        return 01920    # Recursive: current + rest21    return lst[index]10 + sum_by_index(lst[10, -5, 15], index0 + 1)
    All 4 passes — pass 1 is the card above
    passindexlst[index]
    1010
    21-5
    3215
    43—

  6. if index >= len(lst):

    16# Base case: reached end17if index3 >= len(lst[10, -5, 15]):18    return 0

  7. print("Sum (index): ", sum_by_index(numbers))

    38print("Sum (basic): ", sum_list(numbers))39print("Sum (index): ", sum_by_index(numbers[10, -5, 15]))40print("Sum (tail):  ", sum_tail_recursive(numbers[10, -5, 15]))
    outputSum (index):  20

  8. def sum_tail_recursive(lst, accumulator=0):

    pass 1 of 4
    24def sum_tail_recursive(lst[10, -5, 15], accumulator0=0):25    """Tail recursive sum"""26    # Base case27    if not lst:28        return accumulator2930    # Tail recursion: recursive call is last operation31    return sum_tail_recursive(lst[1:][-5, 15], accumulator0 + lst[0]10)
    All 4 passes — pass 1 is the card above
    passlstaccumulatorlst[1:]lst[0]
    1[10, -5, 15]0[-5, 15]10
    2[-5, 15]10[15]-5
    3[15]5[]15
    4[]20——

  9. if not lst:

    26# Base case27if not lst[]:28    return accumulator20

  10. values ← [10, 20, 30, 40]

    39print("Sum (index): ", sum_by_index(numbers))40print("Sum (tail):  ", sum_tail_recursive(numbers[10, -5, 15]))4142values→ [10, 20, 30, 40] = [10, 20, 30, 40]43print("\nList:", values[10, 20, 30, 40])44print("Sum:", sum_list(values[10, 20, 30, 40]))
    outputSum (tail):   20

List: [10, 20, 30, 40]

  11. if not lst:

    pass 2 of 2
    6# Base case: empty list7if not lst[]:8    return 0

  12. print("Sum:", sum_list(values))

    43print("\nList:", values)44print("Sum:", sum_list(values[10, 20, 30, 40]))
    outputSum: 100
list_recursion Process the first element, then recursively handle the rest of the list

Reverse String

string_reverse.py
Replay: real traced execution (multi-file project)
# Recursive string reverse


def reverse(s):
    """Reverse using substring"""
    # Base case: empty or single character
    if len(s) <= 1:
        return s

    # Recursive: last char + reverse of rest
    return s[-1] + reverse(s[:-1])


def reverse_alt(s):
    """Alternative: first char at end"""
    # Base case
    if len(s) <= 1:
        return s

    # Recursive: reverse rest + first char
    return reverse_alt(s[1:]) + s[0]


def reverse_trace(s, depth=0):
    """Reverse with trace"""
    indent = "  " * depth
    print(f"{indent}reverse(\"{s}\")")

    # Base and recursive cases
    if len(s) <= 1:
        print(f"{indent}  → \"{s}\"")
        return s

    last = s[-1]
    rest = s[:-1]
    result = last + reverse_trace(rest, depth + 1)

    print(f"{indent}  → \"{result}\"")
    return result


# Test string reverse
words = ["hello", "recursion", "Python"]

for word in words:
    print(f"{word} → {reverse(word)}")

print("\nAlternative approach:")
print(f"world → {reverse_alt('world')}")

print("\nWith trace:")
reverse_trace("abc")

  1. words ← ['hello', 'recursion', 'Python']

    42# Test string reverse43words→ ['hello', 'recursion', 'Python'] = ["hello", "recursion", "Python"]

  2. for word in words:

    pass 1 of 3
    45for wordhello in words['hello', 'recursion', 'Python']:46    print(f"{wordhello} → {reverse(word)}")
    All 3 passes — pass 1 is the card above
    password
    1hello
    2recursion
    3Python

  3. def reverse(s):

    pass 1 of 20
    4def reverse(shello):5    """Reverse using substring"""6    # Base case: empty or single character7    if len(s) <= 1:8        return s910    # Recursive: last char + reverse of rest11    return s[-1]o + reverse(s[:-1]hell)
    20 passes — pass 1 is the card above
    passss[-1]s[:-1]
    1helloohell
    2helllhel
    3hellhe
    4heeh
    5h——
    6recursionnrecursio
    7recursioorecursi
    8recursiirecurs
    9recurssrecur
    ⋯ 9 more passes ⋯
    19PyyP
    20P——

  4. if len(s) <= 1:

    pass 1 of 3
    6# Base case: empty or single character7if len(sh) <= 1:8    return sh
    All 3 passes — pass 1 is the card above
    passs
    1h
    2r
    3P

  5. print(f"{word} → {reverse(word)}")

    45for word in words:46    print(f"{wordhello} → {reverse(word)}")
    outputhello → olleh

  6. print(f"{word} → {reverse(word)}")

    45for word in words:46    print(f"{wordrecursion} → {reverse(word)}")
    outputrecursion → noisrucer

  7. print(f"{word} → {reverse(word)}")

    45for word in words:46    print(f"{wordPython} → {reverse(word)}")
    outputPython → nohtyP

  8. print(" Alternative approach:")

    48print("\nAlternative approach:")49print(f"world → {reverse_alt('world')}")
    output
Alternative approach:

  9. def reverse_alt(s):

    pass 1 of 5
    14def reverse_alt(sworld):15    """Alternative: first char at end"""16    # Base case17    if len(s) <= 1:18        return s1920    # Recursive: reverse rest + first char21    return reverse_alt(s[1:]orld) + s[0]w
    All 5 passes — pass 1 is the card above
    passss[1:]s[0]
    1worldorldw
    2orldrldo
    3rldldr
    4lddl
    5d——

  10. if len(s) <= 1:

    16# Base case17if len(sd) <= 1:18    return sd

  11. print(f"world → {reverse_alt('world')}")

    48print("\nAlternative approach:")49print(f"world → {reverse_alt('world')}")5051print("\nWith trace:")52reverse_trace("abc")
    outputworld → dlrow

With trace:

  12. indent ← (empty), last ← c, rest ← ab

    pass 1 of 3
    24def reverse_trace(sabc, depth0=0):25    """Reverse with trace"""26    indent→ (empty) = "  " * depth027    print(f"{indent(empty)}reverse(\"{sabc}\")")2829    # Base and recursive cases30    if len(s) <= 1:31        print(f"{indent}  → \"{s}\"")32        return s3334    last→ c = s[-1]c35    rest→ ab = s[:-1]ab36    result = lastc + reverse_trace(restab, depth0 + 1)
    outputreverse("abc")
    All 3 passes — pass 1 is the card above
    passsdepths[-1]s[:-1]indentlastrest
    1abc0cab(empty)cab
    2ab1ba ba
    3a2—— ——

  13. if len(s) <= 1:

    29# Base and recursive cases30if len(sa) <= 1:31    print(f"{indent    }  → \"{sa}\"")32    return sa
    output      → "a"

  14. result ← ba

    35rest = s[:-1]36result→ ba = lastb + reverse_trace(resta, depth1 + 1)3738print(f"{indent  }  → \"{resultba}\"")39return resultba
    output    → "ba"

  15. last ← c, rest ← ab, depth ← 0, result ← cba

    35rest = s[:-1]36result→ cba = last→ c + reverse_trace(rest→ ab, depth→ 0 + 1)3738print(f"{indent(empty)}  → \"{resultcba}\"")39return resultcba
    output  → "cba"

  16. reverse_trace("abc")

    51print("\nWith trace:")52reverse_trace("abc")

Power Function

power.py
Replay: real traced execution (multi-file project)
# Recursive power function


def power(base, exp):
    """Simple recursive power"""
    # Base case
    if exp == 0:
        return 1

    # Recursive case: base * base^(exp-1)
    return base * power(base, exp - 1)


def power_optimized(base, exp):
    """Optimized: divide and conquer"""
    # Base case
    if exp == 0:
        return 1

    # If even: (base^(exp/2))^2
    if exp % 2 == 0:
        half = power_optimized(base, exp // 2)
        return half * half

    # If odd: base * base^(exp-1)
    return base * power_optimized(base, exp - 1)


# Count calls
call_count = 0


def power_counted(base, exp):
    """Power with call counting"""
    global call_count
    call_count += 1

    if exp == 0:
        return 1
    return base * power_counted(base, exp - 1)


def power_optimized_counted(base, exp):
    """Optimized power with call counting"""
    global call_count
    call_count += 1

    if exp == 0:
        return 1
    if exp % 2 == 0:
        half = power_optimized_counted(base, exp // 2)
        return half * half
    return base * power_optimized_counted(base, exp - 1)


# Test power functions
print(f"2^10 = {power(2, 10)}")
print(f"3^5 = {power(3, 5)}")

print("\nOptimized:")
print(f"2^10 = {power_optimized(2, 10)}")

# Compare call counts
call_count = 0
r1 = power_counted(2, 10)
calls1 = call_count

call_count = 0
r2 = power_optimized_counted(2, 10)
calls2 = call_count

print("\nCalls for 2^10:")
print(f"  Simple: {calls1} calls")
print(f"  Optimized: {calls2} calls")

  1. call_count ← 0

    29# Count calls30call_count→ 0 = 0313233def power_counted(base, exp):34    """Power with call counting"""35    global call_count36    call_count += 13738    if exp == 0:39        return 140    return base * power_counted(base, exp - 1)414243def power_optimized_counted(base, exp):44    """Optimized power with call counting"""45    global call_count46    call_count += 14748    if exp == 0:49        return 150    if exp % 2 == 0:51        half = power_optimized_counted(base, exp // 2)52        return half * half53    return base * power_optimized_counted(base, exp - 1)545556# Test power functions57print(f"2^10 = {power(2, 10)}")58print(f"3^5 = {power(3, 5)}")

  2. def power(base, exp):

    pass 1 of 17
    4def power(base2, exp10):5    """Simple recursive power"""6    # Base case7    if exp == 0:8        return 1910    # Recursive case: base * base^(exp-1)11    return base2 * power(base, exp10 - 1)
    17 passes — pass 1 is the card above
    passbaseexp
    1210
    229
    328
    427
    526
    625
    724
    823
    922
    ⋯ 6 more passes ⋯
    1631
    1730

  3. if exp == 0:

    pass 1 of 2
    6# Base case7if exp0 == 0:8    return 1

  4. print(f"2^10 = {power(2, 10)}")

    56# Test power functions57print(f"2^10 = {power(2, 10)}")58print(f"3^5 = {power(3, 5)}")
    output2^10 = 1024

  5. if exp == 0:

    pass 2 of 2
    6# Base case7if exp0 == 0:8    return 1

  6. print(f"3^5 = {power(3, 5)}")

    57print(f"2^10 = {power(2, 10)}")58print(f"3^5 = {power(3, 5)}")5960print("\nOptimized:")61print(f"2^10 = {power_optimized(2, 10)}")
    output3^5 = 243

Optimized:

  7. def power_optimized(base, exp):

    pass 1 of 6
    14def power_optimized(base2, exp10):15    """Optimized: divide and conquer"""16    # Base case
    All 6 passes — pass 1 is the card above
    passexp
    110
    25
    34
    42
    51
    60

  8. if exp % 2 == 0:

    pass 1 of 3
    20# If even: (base^(exp/2))^221if exp10 % 2 == 0:22    half = power_optimized(base2, exp10 // 2)23    return half * half
    All 3 passes — pass 1 is the card above
    passexp
    110
    24
    32

  9. if exp == 0:

    16# Base case17if exp0 == 0:18    return 1

  10. half ← 2

    21if exp % 2 == 0:22    half→ 2 = power_optimized(base2, exp2 // 2)23    return half2 * half

  11. base ← 2, exp ← 4, half ← 4

    21if exp % 2 == 0:22    half→ 4 = power_optimized(base→ 2, exp→ 4 // 2)23    return half4 * half

  12. base ← 2, exp ← 10, half ← 32

    21if exp % 2 == 0:22    half→ 32 = power_optimized(base→ 2, exp→ 10 // 2)23    return half32 * half

  13. call_count ← 0

    60print("\nOptimized:")61print(f"2^10 = {power_optimized(2, 10)}")6263# Compare call counts64call_count→ 0 = 065r1 = power_counted(2, 10)66calls1 = call_count
    output2^10 = 1024

  14. call_count ← 1

    pass 1 of 11
    33def power_counted(base2, exp10):34    """Power with call counting"""35    global call_count36    call_count→ 1 += 13738    if exp == 0:39        return 140    return base2 * power_counted(base, exp10 - 1)
    All 11 passes — pass 1 is the card above
    passexpcall_count
    1100 → 1
    291 → 2
    382 → 3
    473 → 4
    564 → 5
    655 → 6
    746 → 7
    837 → 8
    928 → 9
    1019 → 10
    11010 → 11

  15. if exp == 0:

    38if exp0 == 0:39    return 140return base * power_counted(base, exp - 1)

  16. r1 ← 1024, calls1 ← 11, call_count ← 0

    64call_count = 065r1→ 1024 = power_counted(2, 10)66calls1→ 11 = call_count116768call_count→ 0 = 069r2 = power_optimized_counted(2, 10)70calls2 = call_count

  17. call_count ← 1

    pass 1 of 6
    43def power_optimized_counted(base2, exp10):44    """Optimized power with call counting"""45    global call_count46    call_count→ 1 += 1
    All 6 passes — pass 1 is the card above
    passexpcall_count
    1100 → 1
    251 → 2
    342 → 3
    423 → 4
    514 → 5
    605 → 6

  18. if exp % 2 == 0:

    pass 1 of 3
    49    return 150if exp10 % 2 == 0:51    half = power_optimized_counted(base2, exp10 // 2)52    return half * half
    All 3 passes — pass 1 is the card above
    passexp
    110
    24
    32

  19. if exp == 0:

    48if exp0 == 0:49    return 150if exp % 2 == 0:

  20. half ← 2

    50if exp % 2 == 0:51    half→ 2 = power_optimized_counted(base2, exp2 // 2)52    return half2 * half53return base * power_optimized_counted(base, exp - 1)

  21. base ← 2, exp ← 4, half ← 4

    50if exp % 2 == 0:51    half→ 4 = power_optimized_counted(base→ 2, exp→ 4 // 2)52    return half4 * half53return base * power_optimized_counted(base, exp - 1)

  22. base ← 2, exp ← 10, half ← 32

    50if exp % 2 == 0:51    half→ 32 = power_optimized_counted(base→ 2, exp→ 10 // 2)52    return half32 * half53return base * power_optimized_counted(base, exp - 1)

  23. r2 ← 1024, calls2 ← 6

    68call_count = 069r2→ 1024 = power_optimized_counted(2, 10)70calls2→ 6 = call_count67172print("\nCalls for 2^10:")73print(f"  Simple: {calls111} calls")74print(f"  Optimized: {calls26} calls")
    output
Calls for 2^10:
  Simple: 11 calls
  Optimized: 6 calls
divide_conquer Break the problem in half to achieve O(log n) instead of O(n)

Count Occurrences

count.py
Replay: real traced execution (multi-file project)
# Count occurrences


def count_in_list(lst, target):
    """Count value in list"""
    # Base case: empty list
    if not lst:
        return 0

    # Check first element
    current_count = 1 if lst[0] == target else 0

    # Add count from rest
    return current_count + count_in_list(lst[1:], target)


def count_char(s, target):
    """Count char in string"""
    # Base case: empty string
    if not s:
        return 0

    # Check first character
    current_count = 1 if s[0] == target else 0

    # Add count from rest
    return current_count + count_char(s[1:], target)


def count_digits(n):
    """Count digits in number"""
    # Base case: single digit
    if n < 10:
        return 1

    # Recursive: 1 + count of remaining digits
    return 1 + count_digits(n // 10)


def count_even(lst):
    """Count even numbers"""
    # Base case
    if not lst:
        return 0

    # Count current if even
    current = 1 if lst[0] % 2 == 0 else 0
    return current + count_even(lst[1:])


# Test counting
numbers = [1, 2, 3, 2, 4, 2, 5]

print("List:", numbers)
print(f"Count of 2: {count_in_list(numbers, 2)}")
print(f"Count of 5: {count_in_list(numbers, 5)}")
print(f"Count of 9: {count_in_list(numbers, 9)}")

text = "recursion"
print(f"\nString: {text}")
print(f"Count 'r': {count_char(text, 'r')}")
print(f"Count 'i': {count_char(text, 'i')}")

print(f"\nDigits in 12345: {count_digits(12345)}")
print(f"Digits in 987: {count_digits(987)}")

print(f"\nEven numbers in {numbers}: {count_even(numbers)}")

  1. numbers ← [1, 2, 3, 2, 4, 2, 5]

    51# Test counting52numbers→ [1, 2, 3, 2, 4, 2, 5] = [1, 2, 3, 2, 4, 2, 5]5354print("List:", numbers[1, 2, 3, 2, 4, 2, 5])55print(f"Count of 2: {count_in_list(numbers[1, 2, 3, 2, 4, 2, 5], 2)}")56print(f"Count of 5: {count_in_list(numbers, 5)}")
    outputList: [1, 2, 3, 2, 4, 2, 5]

  2. current_count ← 0

    pass 1 of 24
    4def count_in_list(lst[1, 2, 3, 2, 4, 2, 5], target2):5    """Count value in list"""6    # Base case: empty list7    if not lst:8        return 0910    # Check first element11    current_count→ 0 = 1 if lst[0]1 == target2 else 01213    # Add count from rest14    return current_count0 + count_in_list(lst[1:][2, 3, 2, 4, 2, 5], target2)
    24 passes — pass 1 is the card above
    passlsttargetlst[0]lst[1:]current_count
    1[1, 2, 3, 2, 4, 2, 5]21[2, 3, 2, 4, 2, 5]0
    2[2, 3, 2, 4, 2, 5]22[3, 2, 4, 2, 5]1
    3[3, 2, 4, 2, 5]23[2, 4, 2, 5]0
    4[2, 4, 2, 5]22[4, 2, 5]1
    5[4, 2, 5]24[2, 5]0
    6[2, 5]22[5]1
    7[5]25[]0
    8[]2———
    9[1, 2, 3, 2, 4, 2, 5]51[2, 3, 2, 4, 2, 5]0
    ⋯ 13 more passes ⋯
    23[5]95[]0
    24[]9———

  3. if not lst:

    pass 1 of 3
    6# Base case: empty list7if not lst[]:8    return 0

  4. print(f"Count of 2: {count_in_list(numbers, 2)}")

    54print("List:", numbers)55print(f"Count of 2: {count_in_list(numbers[1, 2, 3, 2, 4, 2, 5], 2)}")56print(f"Count of 5: {count_in_list(numbers[1, 2, 3, 2, 4, 2, 5], 5)}")57print(f"Count of 9: {count_in_list(numbers, 9)}")
    outputCount of 2: 3

  5. print(f"Count of 5: {count_in_list(numbers, 5)}")

    55print(f"Count of 2: {count_in_list(numbers, 2)}")56print(f"Count of 5: {count_in_list(numbers[1, 2, 3, 2, 4, 2, 5], 5)}")57print(f"Count of 9: {count_in_list(numbers[1, 2, 3, 2, 4, 2, 5], 9)}")
    outputCount of 5: 1

  6. text ← recursion

    56print(f"Count of 5: {count_in_list(numbers, 5)}")57print(f"Count of 9: {count_in_list(numbers[1, 2, 3, 2, 4, 2, 5], 9)}")5859text→ recursion = "recursion"60print(f"\nString: {textrecursion}")61print(f"Count 'r': {count_char(textrecursion, 'r')}")62print(f"Count 'i': {count_char(text, 'i')}")
    outputCount of 9: 0

String: recursion

  7. current_count ← 1

    pass 1 of 20
    17def count_char(srecursion, targetr):18    """Count char in string"""19    # Base case: empty string20    if not s:21        return 02223    # Check first character24    current_count→ 1 = 1 if s[0]r == targetr else 02526    # Add count from rest27    return current_count1 + count_char(s[1:]ecursion, targetr)
    20 passes — pass 1 is the card above
    passstargets[0]s[1:]current_count
    1recursionrrecursion1
    2ecursionrecursion0
    3cursionrcursion0
    4ursionrursion0
    5rsionrrsion1
    6sionrsion0
    7ionrion0
    8onron0
    9nrn(empty)0
    ⋯ 9 more passes ⋯
    19nin(empty)0
    20(empty)i———

  8. if not s:

    pass 1 of 2
    19# Base case: empty string20if not s(empty):21    return 0

  9. print(f"Count 'r': {count_char(text, 'r')}")

    60print(f"\nString: {text}")61print(f"Count 'r': {count_char(textrecursion, 'r')}")62print(f"Count 'i': {count_char(textrecursion, 'i')}")
    outputCount 'r': 2

  10. if not s:

    pass 2 of 2
    19# Base case: empty string20if not s(empty):21    return 0

  11. print(f"Count 'i': {count_char(text, 'i')}")

    61print(f"Count 'r': {count_char(text, 'r')}")62print(f"Count 'i': {count_char(textrecursion, 'i')}")6364print(f"\nDigits in 12345: {count_digits(12345)}")65print(f"Digits in 987: {count_digits(987)}")
    outputCount 'i': 1

  12. def count_digits(n):

    pass 1 of 8
    30def count_digits(n12345):31    """Count digits in number"""32    # Base case: single digit33    if n < 10:34        return 13536    # Recursive: 1 + count of remaining digits37    return 1 + count_digits(n12345 // 10)
    All 8 passes — pass 1 is the card above
    passn
    112345
    21234
    3123
    412
    51
    6987
    798
    89

  13. if n < 10:

    pass 1 of 2
    32# Base case: single digit33if n1 < 10:34    return 1

  14. print(f" Digits in 12345: {count_digits(12345)}")

    64print(f"\nDigits in 12345: {count_digits(12345)}")65print(f"Digits in 987: {count_digits(987)}")
    output
Digits in 12345: 5

  15. if n < 10:

    pass 2 of 2
    32# Base case: single digit33if n9 < 10:34    return 1

  16. print(f" Even numbers in {numbers}: {count_even(numbers)}")

    64print(f"\nDigits in 12345: {count_digits(12345)}")65print(f"Digits in 987: {count_digits(987)}")6667print(f"\nEven numbers in {numbers[1, 2, 3, 2, 4, 2, 5]}: {count_even(numbers)}")
    outputDigits in 987: 3

  17. current ← 0

    pass 1 of 8
    40def count_even(lst[1, 2, 3, 2, 4, 2, 5]):41    """Count even numbers"""42    # Base case43    if not lst:44        return 04546    # Count current if even47    current→ 0 = 1 if lst[0]1 % 2 == 0 else 048    return current0 + count_even(lst[1:][2, 3, 2, 4, 2, 5])
    All 8 passes — pass 1 is the card above
    passlstlst[0]lst[1:]current
    1[1, 2, 3, 2, 4, 2, 5]1[2, 3, 2, 4, 2, 5]0
    2[2, 3, 2, 4, 2, 5]2[3, 2, 4, 2, 5]1
    3[3, 2, 4, 2, 5]3[2, 4, 2, 5]0
    4[2, 4, 2, 5]2[4, 2, 5]1
    5[4, 2, 5]4[2, 5]1
    6[2, 5]2[5]1
    7[5]5[]0
    8[]———

  18. if not lst:

    42# Base case43if not lst[]:44    return 0

  19. print(f" Even numbers in {numbers}: {count_even(numbers)}")

    67print(f"\nEven numbers in {numbers[1, 2, 3, 2, 4, 2, 5]}: {count_even(numbers)}")
    output
Even numbers in [1, 2, 3, 2, 4, 2, 5]: 4

Binary Search (Recursive)

binary_search.py
Replay: real traced execution (multi-file project)
# Recursive binary search


def binary_search(lst, target, left=0, right=None):
    """Recursive binary search"""
    if right is None:
        right = len(lst) - 1

    # Base case: not found
    if left > right:
        return -1

    # Find middle
    mid = left + (right - left) // 2

    # Check middle element
    if lst[mid] == target:
        return mid

    # Recurse on appropriate half
    if lst[mid] > target:
        # Search left half
        return binary_search(lst, target, left, mid - 1)
    else:
        # Search right half
        return binary_search(lst, target, mid + 1, right)


def binary_search_trace(lst, target, left=0, right=None, depth=0):
    """Binary search with trace"""
    if right is None:
        right = len(lst) - 1

    indent = "  " * depth

    # Base case
    if left > right:
        print(f"{indent}Not found")
        return -1

    # Find and check middle
    mid = left + (right - left) // 2
    print(f"{indent}Searching [{left}..{right}], mid={mid} (value={lst[mid]})")

    if lst[mid] == target:
        print(f"{indent}Found at index {mid}")
        return mid

    # Recurse
    if lst[mid] > target:
        print(f"{indent}Go left")
        return binary_search_trace(lst, target, left, mid - 1, depth + 1)
    else:
        print(f"{indent}Go right")
        return binary_search_trace(lst, target, mid + 1, right, depth + 1)


# Test binary search
numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

print("List:", numbers)
print(f"Search 7: index {binary_search(numbers, 7)}")
print(f"Search 15: index {binary_search(numbers, 15)}")
print(f"Search 8: index {binary_search(numbers, 8)}")

print("\nSearch 13 with trace:")
binary_search_trace(numbers, 13)

  1. numbers ← [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

    58# Test binary search59numbers→ [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]6061print("List:", numbers[1, 3, 5, 7, 9, 11, 13, 15, 17, 19])62print(f"Search 7: index {binary_search(numbers[1, 3, 5, 7, 9, 11, 13, 15, 17, 19], 7)}")63print(f"Search 15: index {binary_search(numbers, 15)}")
    outputList: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

  2. def binary_search(lst, target, left=0, right=None):

    pass 1 of 11
    4def binary_search(lst[1, 3, 5, 7, 9, 11, 13, 15, 17, 19], target7, left0=0, rightNone=NoneNone):5    """Recursive binary search"""6    if right is None:
    All 11 passes — pass 1 is the card above
    passtargetleftrightlst[mid]mid
    170None——
    2703—1
    3723—2
    473373
    5150None——
    61559157
    780None——
    8803—1
    9823—2
    10833—3
    11843——

  3. right ← 9

    pass 1 of 3
    5"""Recursive binary search"""6if rightNone is None:7    right→ 9 = len(lst[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]) - 1
    All 3 passes — pass 1 is the card above
    passright
    1None → 9
    2None → 9
    3None → 9

  4. mid ← 4

    13# Find middle14mid→ 4 = left0 + (right9 - left) // 2

  5. if lst[mid] > target: # Search left half

    pass 1 of 2
    20# Recurse on appropriate half21if lst[mid]9 > target7:22    # Search left half23    return binary_search(lst[1, 3, 5, 7, 9, 11, 13, 15, 17, 19], target7, left0, mid4 - 1)24else:

  6. else: # Search right half

    pass 1 of 6
    22    # Search left half23    return binary_search(lst, target, left, mid - 1)24else:25    # Search right half26    return binary_search(lst[1, 3, 5, 7, 9, 11, 13, 15, 17, 19], target7, mid1 + 1, right3)
    All 6 passes — pass 1 is the card above
    passtargetmidrightlst[mid]left
    1713——
    27237—
    3154915—
    4813——
    5823——
    6833—4

  7. if lst[mid] == target:

    pass 1 of 2
    16# Check middle element17if lst[mid]7 == target7:18    return mid3

  8. print(f"Search 7: index {binary_search(numbers, 7)}")

    61print("List:", numbers)62print(f"Search 7: index {binary_search(numbers[1, 3, 5, 7, 9, 11, 13, 15, 17, 19], 7)}")63print(f"Search 15: index {binary_search(numbers[1, 3, 5, 7, 9, 11, 13, 15, 17, 19], 15)}")64print(f"Search 8: index {binary_search(numbers, 8)}")
    outputSearch 7: index 3

  9. mid ← 4

    13# Find middle14mid→ 4 = left0 + (right9 - left) // 2

  10. if lst[mid] == target:

    pass 2 of 2
    16# Check middle element17if lst[mid]15 == target15:18    return mid7

  11. print(f"Search 15: index {binary_search(numbers, 15)}")

    62print(f"Search 7: index {binary_search(numbers, 7)}")63print(f"Search 15: index {binary_search(numbers[1, 3, 5, 7, 9, 11, 13, 15, 17, 19], 15)}")64print(f"Search 8: index {binary_search(numbers[1, 3, 5, 7, 9, 11, 13, 15, 17, 19], 8)}")
    outputSearch 15: index 7

  12. mid ← 4

    13# Find middle14mid→ 4 = left0 + (right9 - left) // 2

  13. if lst[mid] > target: # Search left half

    pass 2 of 2
    20# Recurse on appropriate half21if lst[mid]9 > target8:22    # Search left half23    return binary_search(lst[1, 3, 5, 7, 9, 11, 13, 15, 17, 19], target8, left0, mid4 - 1)24else:

  14. if left > right:

    9# Base case: not found10if left4 > right3:11    return -1

  15. print(f"Search 8: index {binary_search(numbers, 8)}")

    63print(f"Search 15: index {binary_search(numbers, 15)}")64print(f"Search 8: index {binary_search(numbers[1, 3, 5, 7, 9, 11, 13, 15, 17, 19], 8)}")6566print("\nSearch 13 with trace:")67binary_search_trace(numbers[1, 3, 5, 7, 9, 11, 13, 15, 17, 19], 13)
    outputSearch 8: index -1

Search 13 with trace:

  16. def binary_search_trace(lst, target, left=0, right=None, depth=0):

    pass 1 of 4
    29def binary_search_trace(lst[1, 3, 5, 7, 9, 11, 13, 15, 17, 19], target13, left0=0, rightNone=NoneNone, depth0=0):30    """Binary search with trace"""31    if right is None:
    All 4 passes — pass 1 is the card above
    passleftdepthlst[mid]rightindentmid
    100—None → 9——
    251159 7
    352116 5
    463136 6

  17. right ← 9

    30"""Binary search with trace"""31if rightNone is None:32    right→ 9 = len(lst[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]) - 1

  18. indent ← (empty), mid ← 4

    34indent→ (empty) = "  " * depth03536# Base case37if left > right:38    print(f"{indent}Not found")39    return -14041# Find and check middle42mid→ 4 = left0 + (right9 - left) // 243print(f"{indent(empty)}Searching [{left0}..{right9}], mid={mid4} (value={lst[mid]9})")
    outputSearching [0..9], mid=4 (value=9)

  19. else:

    pass 1 of 2
    51    print(f"{indent}Go left")52    return binary_search_trace(lst, target, left, mid - 1, depth + 1)53else:54    print(f"{indent(empty)}Go right")55    return binary_search_trace(lst[1, 3, 5, 7, 9, 11, 13, 15, 17, 19], target13, mid4 + 1, right9, depth0 + 1)
    outputGo right

  20. if lst[mid] > target:

    49# Recurse50if lst[mid]15 > target13:51    print(f"{indent  }Go left")52    return binary_search_trace(lst[1, 3, 5, 7, 9, 11, 13, 15, 17, 19], target13, left5, mid7 - 1, depth1 + 1)53else:
    output  Go left

  21. else:

    pass 2 of 2
    51    print(f"{indent}Go left")52    return binary_search_trace(lst, target, left, mid - 1, depth + 1)53else:54    print(f"{indent    }Go right")55    return binary_search_trace(lst[1, 3, 5, 7, 9, 11, 13, 15, 17, 19], target13, mid5 + 1, right6, depth2 + 1)
    output    Go right

  22. if lst[mid] == target:

    45if lst[mid]13 == target13:46    print(f"{indent      }Found at index {mid6}")47    return mid6
    output      Found at index 6

  23. binary_search_trace(numbers, 13)

    66print("\nSearch 13 with trace:")67binary_search_trace(numbers[1, 3, 5, 7, 9, 11, 13, 15, 17, 19], 13)

Greatest Common Divisor

gcd.py
Replay: real traced execution (multi-file project)
# Greatest Common Divisor (GCD)


def gcd(a, b):
    """Euclidean algorithm"""
    # Base case: b is 0
    if b == 0:
        return a

    # Recursive case: gcd(b, a mod b)
    return gcd(b, a % b)


def gcd_trace(a, b):
    """GCD with trace"""
    print(f"gcd({a}, {b})")

    # Base and recursive cases
    if b == 0:
        print(f"  → {a}")
        return a

    return gcd_trace(b, a % b)


def lcm(a, b):
    """Least Common Multiple using GCD"""
    return (a * b) // gcd(a, b)


def gcd_iterative(a, b):
    """Iterative GCD for comparison"""
    while b != 0:
        a, b = b, a % b
    return a


# Test GCD
print(f"GCD(48, 18) = {gcd(48, 18)}")
print(f"GCD(100, 35) = {gcd(100, 35)}")
print(f"GCD(17, 13) = {gcd(17, 13)}")

print("\nGCD(48, 18) with trace:")
gcd_trace(48, 18)

print(f"\nLCM(12, 18) = {lcm(12, 18)}")
print(f"LCM(7, 5) = {lcm(7, 5)}")

print(f"\nIterative GCD(48, 18) = {gcd_iterative(48, 18)}")

  1. print(f"GCD(48, 18) = {gcd(48, 18)}")

    38# Test GCD39print(f"GCD(48, 18) = {gcd(48, 18)}")40print(f"GCD(100, 35) = {gcd(100, 35)}")

  2. def gcd(a, b):

    pass 1 of 20
    4def gcd(a48, b18):5    """Euclidean algorithm"""6    # Base case: b is 07    if b == 0:8        return a910    # Recursive case: gcd(b, a mod b)11    return gcd(b18, a48 % b)
    20 passes — pass 1 is the card above
    passab
    14818
    21812
    3126
    460
    510035
    63530
    7305
    850
    91713
    ⋯ 9 more passes ⋯
    1921
    2010

  3. if b == 0:

    pass 1 of 5
    6# Base case: b is 07if b0 == 0:8    return a6
    All 5 passes — pass 1 is the card above
    passa
    16
    25
    31
    46
    51

  4. print(f"GCD(48, 18) = {gcd(48, 18)}")

    38# Test GCD39print(f"GCD(48, 18) = {gcd(48, 18)}")40print(f"GCD(100, 35) = {gcd(100, 35)}")41print(f"GCD(17, 13) = {gcd(17, 13)}")
    outputGCD(48, 18) = 6

  5. print(f"GCD(100, 35) = {gcd(100, 35)}")

    39print(f"GCD(48, 18) = {gcd(48, 18)}")40print(f"GCD(100, 35) = {gcd(100, 35)}")41print(f"GCD(17, 13) = {gcd(17, 13)}")
    outputGCD(100, 35) = 5

  6. print(f"GCD(17, 13) = {gcd(17, 13)}")

    40print(f"GCD(100, 35) = {gcd(100, 35)}")41print(f"GCD(17, 13) = {gcd(17, 13)}")4243print("\nGCD(48, 18) with trace:")44gcd_trace(48, 18)
    outputGCD(17, 13) = 1

GCD(48, 18) with trace:

  7. def gcd_trace(a, b):

    pass 1 of 4
    14def gcd_trace(a48, b18):15    """GCD with trace"""16    print(f"gcd({a48}, {b18})")1718    # Base and recursive cases19    if b == 0:20        print(f"  → {a}")21        return a2223    return gcd_trace(b18, a48 % b)
    outputgcd(48, 18)
    All 4 passes — pass 1 is the card above
    passab
    14818
    21812
    3126
    460

  8. if b == 0:

    18# Base and recursive cases19if b0 == 0:20    print(f"  → {a6}")21    return a6
    output  → 6

  9. gcd_trace(48, 18)

    43print("\nGCD(48, 18) with trace:")44gcd_trace(48, 18)4546print(f"\nLCM(12, 18) = {lcm(12, 18)}")47print(f"LCM(7, 5) = {lcm(7, 5)}")

  10. def lcm(a, b):

    pass 1 of 2
    26def lcm(a12, b18):27    """Least Common Multiple using GCD"""28    return (a12 * b18) // gcd(a, b)

  11. print(f" LCM(12, 18) = {lcm(12, 18)}")

    46print(f"\nLCM(12, 18) = {lcm(12, 18)}")47print(f"LCM(7, 5) = {lcm(7, 5)}")
    output
LCM(12, 18) = 36

  12. def lcm(a, b):

    pass 2 of 2
    26def lcm(a7, b5):27    """Least Common Multiple using GCD"""28    return (a7 * b5) // gcd(a, b)

  13. print(f"LCM(7, 5) = {lcm(7, 5)}")

    46print(f"\nLCM(12, 18) = {lcm(12, 18)}")47print(f"LCM(7, 5) = {lcm(7, 5)}")4849print(f"\nIterative GCD(48, 18) = {gcd_iterative(48, 18)}")
    outputLCM(7, 5) = 35

  14. def gcd_iterative(a, b):

    31def gcd_iterative(a48, b18):32    """Iterative GCD for comparison"""33    while b != 0:

  15. a ← 18, b ← 12

    pass 1 of 3
    32"""Iterative GCD for comparison"""33while b18 != 0:34    a→ 18, b→ 12 = b, a % b35return a
    All 3 passes — pass 1 is the card above
    passab
    148 → 1818 → 12
    218 → 1212 → 6
    312 → 66 → 0

  16. return a

    34    a, b = b, a % b35return a6

  17. print(f" Iterative GCD(48, 18) = {gcd_iterative(48, 18)}")

    49print(f"\nIterative GCD(48, 18) = {gcd_iterative(48, 18)}")
    output
Iterative GCD(48, 18) = 6
euclidean_algorithm GCD(a, b) = GCD(b, a mod b) until b is 0

Recursion Tips

  • Start with base case: what is the simplest input?
  • Ensure progress: each call moves toward base case
  • Trust the recursion: assume it works for simpler case
  • Combine results: decide how to use the recursive result

Exercise: practical.py

Implement recursive functions to flatten a nested list and find the maximum value in a list