A tiny introduction to recursion in Python

recursion.py

from typing import List, Optional, Sequence


# A recursive function is a function that calls itself. They're an alternative option to iteration, like using a while
# or for loop. Sometimes, they can make code easier to read and write. The examples below are overly simplified and
# have obviously better alternatives.

def multiply_string(s: str, n: int) -> str:
    # There are 3 main parts to a recursive function.
    # 1. A way to go to either the base case (no recursion) or recursive case (function calls itself).
    if n == 0:  # The switch between base and recursive is often an if statement.
        # 2. The base case. This is the case that doesn't require recursion.
        return ''  # Any string times 0 is empty string. That's easy.
    # 3. The recursive case. This same function gets called again, but slightly differently.
    # This needs to eventually get to the base case.
    return s + multiply_string(s, n - 1)  # Add the string to result of multiplying the string times n -1.
    # Eventually, n will be 0 and we'll be at the base case.


# This is also a good order to first write your recursive functions, even if you rewrite in a different order later.
# 1. What input is the base case?
# 2. What calculation needs to be done for the base case (if any)?
# 3. What calculation needs to be done for the recursive case?

# For the base case, there are some common patterns. It's often when an integer input is 0 or 1, the collection is
# totally empty, or you're at the thing you're looking for. A good question is: "What's the easiest possible case?"
# There can also be more than one base case! You've searched everywhere and haven't found the thing could be one
# base case, and you've found the thing could be another.
# For the recursive case, it's often easiest to think of being one step away from a base case. If your base case is
# n=0, think of how to get from n=0 to n=1. This is usually easier than how to get from n=9 to n=10.

def triangle_number(n: int) -> int:
    """Calculate the sum of 1, 2, n. This is like a triangle with n items on the bottom."""
    if n == 0:  # Easy case. n == 1 is just as easy, but this way our function also supports 0.
        return 0
    return n + triangle_number(n - 1)  # This will sum the numbers from highest to lowest. The calculation is like:
    # (3 + (2 + (1 + (0))))


# Recursive functions often have default arguments. These aren't used when you call the function from the outside,
# but they are used when you call the function recursively. They often hold data about the path to get where you are,
# or what you've already looked at.
def contains(item: object, sequence: Sequence, index: int = 0) -> bool:
    # When this function gets called by a user, they won't provide an index and we'll start at 0.
    if index == len(sequence):  # This means we've gone past the last index in the sequence.
        return False
    if sequence[index] == item:  # Another base case. We've found the item.
        return True
    # For the recursion, the item stays the same, the sequence stays the same, but let's check what's at the next index.
    # Any outside user of this function won't provide the index, but we can provide it now and check the next item.
    return contains(item, sequence, index + 1)


# The default arguments also might be mutated. This can help runtime. Rather than create a new thing every time,
# just mutate what was provided. Maybe you return it at the end.
def path_to_zero(n: int, path: Optional[List[int]] = None) -> List[int]:
    """Returns a list of how to get from n to 0 by subtracting 1."""
    if path is None:  # Classic Python mutable default stuff.
        path = []

    if n == 0:  # If we're already at 0 (the end)
        path.append(0)  # Our base case, no recursion required.
        return path
    else:
        path.append(n)  # Put the current number on the path.
        path_to_zero(n - 1, path)  # The path will get mutated in the recursive calls, adding the remaining numbers.
        return path


#  It can be helpful to write recursive functions in a verbose (if: base case, else: recursive) way, then refactor
#  them to be simpler. Here's the function above, refactored.
def path_to_zero_refactored(n: int, path: Optional[List[int]] = None) -> List[int]:
    if path is None:
        path = []

    path.append(n)  # Add the number we're at.
    if n:  # If we're not at 0
        path_to_zero_refactored(n - 1, path)  # Add the next thing until we are.
    return path


#  A good exercise is translating recursive functions to iterative, or vice versa.
def path_to_zero_iterative(n: int) -> List[int]:
    # This isn't the best code, but it's the closest to the recursive version above.
    path = []
    while n != 0:  # Recursive to iterative translations will often have "while not base case" loops.
        path.append(n)
        n -= 1  # This is the same transformation to n that happens in the recursive call above.
    path.append(0)  # Our while loop skips the base case, so we do it here.
    return path


#  The above examples are contrived, but this is an example where the recursive version makes for code that's just
#  as good or better than the iterative version.
def collatz(n: int, steps: int = 0) -> int:
    """Calculates how many steps to get from n to 1 following the Collatz rules.

    The Collatz rules are:
        If the number is even, get the next number by dividing it by 2.
        If the number is odd, get the next number by multiplying by 3 and adding 1.
    """
    if n == 1:  # We're at the end.
        return steps
    elif n % 2 == 0:  # If n is even
        return collatz(n // 2, steps + 1)
    else:  # n is odd
        return collatz(n * 3 + 1, steps + 1)  # Woah, a second recursive case!


# A downside to recursion in Python is that there is a limit to the call stack. This means there's a limit to how
# deep your recursion can go. The default is 1,000.
def deep_recursion():
    """Requires over 1,000 recursive calls, raising a RecursionError on most Python implementations."""
    collatz(9780657630)

# Those are some recursion in Python basics. Go find some other recursive problems and enjoy!