Recursion on Lists and Strings

Peel off one piece

A common pattern: handle the first item yourself and let recursion handle the rest.

def total(items):
    if not items:                    # empty list
        return 0
    return items[0] + total(items[1:])

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

print(total([3, 1, 4, 1, 5]))
print(reverse("stressed"))

Output

14
desserts

Cut the problem in half

Even better: split the problem in half. To work out 2¹⁰, work out 2⁵ once and square it:

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

print(power(2, 10))
print(power(3, 13))

Output

1024
1594323

Multiplying one by one takes exp steps: O(n). Halving takes about log₂(exp) steps: O(log n).

Recursion vs loops

Tip: Anything recursion can do, a loop with your own stack can do too. Pick whichever is easier to read.