Recursive problem solving approaches

recursive_approaches.py

# Recursion + number + return
def sum_digits(n):
    """
    >>> sum_digits(1234)
    10
    """
    if n < 10:
        return n
    return n % 10 + sum_digits(n // 10)

# Recursion + list + return
def sum_list(lst):
    """
    >>> sum_list([1, 2, 3, 4])
    10
    """
    if len(lst) == 0:
        return 0
    return lst[0] + sum_list(lst[1:])

# Recursion + linked list + return
def sum_linked_list(lnk):
    """
    >>> sum_linked_list(Link(1, Link(2, Link(3, Link(4)))))
    10
    """
    if lnk is Link.empty:
        return 0
    return lnk.first + sum_linked_list(lnk.rest)

# Recursion + tree + return
def sum_tree(tree):
    """
    >>> sum_tree(Tree(1, [Tree(2), Tree(3, [Tree(4)])]))
    10
    """
    if tree.is_leaf():
        return tree.label
    branches_sum = 0
    for b in tree.branches:
        branches_sum += sum_tree(b)
    return tree.label + branches_sum

# Recursion + number + yield
def yield_digits(n):
    """
    >>> gen = yield_digits(1234)
    >>> next(gen)
    4
    >>> next(gen)
    3
    >>> next(gen)
    2
    >>> next(gen)
    1
    >>> list(gen)
    []
    """
    if n < 10:
        yield n
    else:
        yield n % 10
        yield from yield_digits(n // 10)

# Recursion + list + yield
def yield_list(lst):
    """
    >>> gen = yield_list([1, 2, 3, 4])
    >>> next(gen)
    1
    >>> next(gen)
    2
    >>> next(gen)
    3
    >>> next(gen)
    4
    >>> list(gen)
    []
    """
    # No base case needed! It will just stop yielding.
    if len(lst) > 0:
        yield lst[0]
        yield from yield_list(lst[1:])

# Recursion + linked list + yield
def yield_linked_list(lnk):
    """
    >>> gen = yield_linked_list(Link(1, Link(2, Link(3, Link(4)))))
    >>> next(gen)
    1
    >>> next(gen)
    2
    >>> next(gen)
    3
    >>> next(gen)
    4
    >>> list(gen)
    []
    """
    # No base case needed! It will just stop yielding.
    if lnk is not Link.empty:
        yield lnk.first
        yield from yield_linked_list(lnk.rest)

# Recursion + tree + yield
def yield_tree(tree):
    """
    >>> gen = yield_tree(Tree(1, [Tree(2), Tree(3, [Tree(4)])]))
    >>> next(gen)
    1
    >>> next(gen)
    2
    >>> next(gen)
    3
    >>> next(gen)
    4
    >>> list(gen)
    []
    """
    # No base case needed! It will just stop yielding.
    yield tree.label
    if tree.branches:
        for b in tree.branches:
            yield from yield_tree(b)
            
            
# Recursion + number + mutation: Can't be done, numbers are immutable

# Recursion + list + mutation
def square_list(lst):
    """
    >>> lst = [1, 2, 3, 4]
    >>> square_list(lst)
    >>> lst
    [1, 4, 9, 16]
    """
    def square_item(index):
        if index == len(lst):
            return
        lst[index] = lst[index] * lst[index]
        square_item(index + 1)
    square_item(0)

# Recursion + linked list + mutation
def square_linked_list(lnk):
    """
    >>> lnk = Link(1, Link(2, Link(3, Link(4))))
    >>> square_linked_list(lnk)
    >>> lnk
    Link(1, Link(4, Link(9, Link(16))))
    """
    if lnk is Link.empty:
        return
    lnk.first = lnk.first * lnk.first
    square_linked_list(lnk.rest)

# Recursion + tree + mutation
def square_tree(t):
    """
    >>> t = Tree(1, [Tree(2), Tree(3, [Tree(4)])])
    >>> square_tree(t)
    >>> t
    Tree(1, [Tree(4), Tree(9, [Tree(16)])])
    """
    t.label = t.label * t.label
    for b in t.branches:
        square_tree(b)