Recursion

In the previous unit, we finished our exploration of OOP. Now let's look at recursion, a technique where a function calls itself to solve a problem.

What Is Recursion?

Recursion solves a problem by breaking it into smaller instances of the same problem. A recursive function calls itself, either directly or indirectly, until it reaches a stopping condition.

Every recursive function needs two parts:

The base case is where the recursion stops. Without it, the function would call itself forever.

The recursive case is where the function calls itself with a smaller or simpler input, moving toward the base case.

Factorial Example

The factorial of a number $n$ (written as $n!$) is the product of all positive integers up to $n$. For example, $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$.

Here's a recursive implementation:

def factorial(n):
    if n == 1:  # Base case
        return 1
    else:       # Recursive case
        return n * factorial(n - 1)

print(factorial(5))  # prints 120

When you call factorial(5), it returns 5 * factorial(4). That call returns 4 * factorial(3), and so on. When factorial(1) returns 1 (the base case), all the pending multiplications resolve: 5 * 4 * 3 * 2 * 1 = 120.

Recursion vs Iteration

Recursion and loops (iteration) can often solve the same problems. Recursion tends to be more concise and intuitive for problems that naturally break into smaller versions of themselves. Iteration is usually more memory-efficient since it doesn't build up a stack of function calls.

Project: Fractal Tree

Recursion shines when creating fractals, patterns that repeat at different scales. Let's draw a tree where each branch splits into smaller branches:

import turtle

def draw_tree(branch_length):
    if branch_length > 5:  # Base case: stop when branches get too small
        turtle.forward(branch_length)
        turtle.right(20)
        draw_tree(branch_length - 15)  # Right subtree
        turtle.left(40)
        draw_tree(branch_length - 15)  # Left subtree
        turtle.right(20)
        turtle.backward(branch_length)

turtle.speed(0)
turtle.left(90)  # Point upward
draw_tree(100)
turtle.done()

The function draws a branch, then recursively draws a right subtree (turning 20 degrees right) and a left subtree (turning 40 degrees left to compensate and go the other direction). After drawing both subtrees, it backs up to return to where it started, ready for the parent call to continue.

The base case stops the recursion when branch_length drops to 5 or below. This creates the "leaves" at the tips of the tree.

The recursive structure produces surprisingly complex output from simple rules. Each call to draw_tree creates two more calls, which each create two more, building up the branching structure. Try changing the angles or the amount subtracted from branch_length to create different tree shapes.

In the next unit, we'll learn how to organize code into reusable modules.