Recursion

Introduction

Recursion is a fundamental concept in programming in which a function to call itself to solve a problem. This approach is useful when solving problems that can be broken down into smaller subproblems of the same type. A special case of recursion, called mutual recursion, occurs when two or more functions call each other in a cyclical manner.

Let’s start with a recursive implementation of factorial:

Example: Factorial

Recall that a factorial, represented by an exclamation mark (!), is a mathematical function in which you multiply a given integer by every positive integer below it. To calculate the factorial of an int, n, we would multiply n by (n-1), then (n-2), and so on, until we reach 1. For instance, to calculate 5!, we would do: 5 * 4 * 3 * 2 * 1, which would evaluate to 120.

Let’s explore the recursive implementation of factorial in Python:

def factorial(n: int) -> int:
    # Base case: factorial of 0 or 1 is 1
    if n <= 1:
        return 1
    # Recursive case: n! = n × (n-1)!
    return n * factorial(n - 1)

# Try different numbers
print("Factorial of 5: ", factorial(n=5))
print("Factorial of 3: ", factorial(n=3))

The output of this code would be:

Factorial of 5: 120
Factorial of 3: 6

Let’s visualize how these recursive calls work for the function call, factorial(n=5):

factorial(5) → return 5 * factorial(4)
                          → return 4 * factorial(3)
                                       → return 3 * factorial(2)
                                                    → return 2 * factorial(1)
                                                                 → return 1

For a more thorough animation of how these recursive function calls work, please see this slide.

The animation in the linked slide illustrates how recursive calls build up and unwind. The downward flow shows each function call breaking down the problem with arguments of (4 → 3 → 2 → 1), while the upward flow demonstrates how the return values (RVs) multiply together to give the final answer. Notice how each level waits for the next level to complete before performing its multiplication, ultimately building up to our final result of 24.

Key Components of Recursion

A recursive function solves a problem by calling itself with altered arguments that progress toward the base case. To avoid infinite recursion, it must include a base case that stops the recursive calls.

1. Base case: The condition under which the recursion stops. In the factorial example, when n <= 1, the function returns 1. We know the recursion stopped at this point, because the function did not call itself in this case. Forgetting to include a base case will cause a RecursionError or Stack Overflow Error (think: your function call frames would overflow in a memory diagram because the function calls wouldn’t stop!).
2. Recursive case: The function calls itself with a modified argument, which progresses toward the base case to prevent infinite recursion. In the factorial example, we do this with the argument, (n - 1).

Tips for Debugging or Writing a Recursive Function

Make sure you have a base case written in your code so you don’t encounter a RecursionError or Stack Overflow Error. Try testing your function with argument values that are close to your base case (meaning, your function won’t call itself lots of times). Write a memory diagram for the code, and reflect on whether your code does what you want it to do. Does the base case cause the recursive calls to stop as expected? Do the return values of each function match your expectations? You can also add print statements in your code (e.g., print("Base case reached!")), to keep track of the control flow. Just don’t forget to remove them once you’re finished testing it!