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.

Greatest Common Divisor

list_sum.py 
# 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 = 

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 = 

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 = 

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))
string_reverse.py 
# 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")
power.py 
# 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")
count.py 
# 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)}")
binary_search.py 
# 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)
gcd.py 
# 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)}")

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
head_recursion Recursive call happens before processing the current element
tail_recursion Recursive call is the last operation, enabling potential optimization
list_recursion Process the first element, then recursively handle the rest of the list
divide_conquer Break the problem in half to achieve O(log n) instead of O(n)
euclidean_algorithm GCD(a, b) = GCD(b, a mod b) until b is 0

Exercise: practical.py

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