When loops get clumsy

A binary tree branches in two at each node, but recursion handles any kind of branching. The pattern stays the same: deal with this level, and call the function for everything nested inside it, however deep that goes.

Lists inside lists

Take a list whose items can be numbers or lists, which again can hold numbers or lists: [1, [2, 3], [4, [5, 6]], 7]. One loop handles one level, and a loop inside it handles two, but how many loops would you need when nobody knows how deep the nesting goes? With recursion, you don't need to know. For each item, if it's a list, ask the same function about it. Otherwise it's a number:

def deep_sum(items):
    total = 0
    for item in items:
        if type(item) == list:
            total += deep_sum(item)
        else:
            total += item
    return total


print(deep_sum([1, [2, 3], [4, [5, 6]], 7]))
print(deep_sum([[[[10]]]]))

28
10

type(item) gives the type of the item, and type(item) == list is true when the item is a list. The loop goes across one level, and the recursive calls go down into the lists inside it. There's no separate base case: a list without lists inside it simply makes no recursive calls.

Any number of children

In a discussion thread, a comment can have any number of replies, and each reply can have replies of its own. A list of children takes the place of left and right:

class Comment:
    def __init__(self, author, text):
        self.author = author
        self.text = text
        self.replies = []

    def add_reply(self, comment):
        self.replies.append(comment)


def show(comment, depth):
    print("  " * depth + f"{comment.author}: {comment.text}")
    for reply in comment.replies:
        show(reply, depth + 1)


def count_comments(comment):
    return 1 + sum([count_comments(reply) for reply in comment.replies])


first = Comment("Ada", "Is recursion hard?")
answer = Comment("Ben", "Only until it clicks.")
first.add_reply(answer)
answer.add_reply(Comment("Ada", "It clicked!"))
first.add_reply(Comment("Cy", "Draw the calls on paper."))

show(first, 0)
print(count_comments(first), "comments")

Ada: Is recursion hard?
  Ben: Only until it clicks.
    Ada: It clicked!
  Cy: Draw the calls on paper.
4 comments

count_comments combines a comprehension with recursion: one comment, plus the count of each reply's whole thread. It has no if at all. For a comment without replies, the comprehension goes through an empty list and makes [], sum([]) is 0, and the function returns 1 without calling itself. That's the base case.

Loop or recursion?

Use a loop to go through a flat series of items one by one. Reach for recursion when the data is nested to a depth you don't know in advance (trees, folders, menus inside menus, lists inside lists), or when a problem splits into smaller problems of the same kind, as in binary search. As the examples show, the two often work together: the loop goes across, and the recursion goes down.