Recursion

Objectives

By the end of this chapter, you should be able to:

• Explain what a recursive function is
• Identify the base case and recursive case in a recursive function
• Write a simple recursive function

💡 Why this matters: Some problems are naturally defined in terms of smaller versions of themselves (a directory containing files and other directories, for instance). Recursion is how you write code that mirrors that structure directly, instead of forcing it into a loop.

What Is Recursion?

A recursive function is a function that calls itself. Every recursive function needs two parts:

• A base case: the condition where the function stops calling itself and just returns a value
• A recursive case: where the function calls itself again, with input that’s closer to the base case

Without a base case (or a bug that never reaches it), a recursive function calls itself forever, until Python raises a RecursionError.

A First Example: Factorial

The factorial of n (written n!) is n × (n-1) × (n-2) × ... × 1. It’s a natural fit for recursion, since n! is just n × (n-1)!:

def factorial(n):
    if n <= 1:
        return 1          # base case
    return n * factorial(n - 1)  # recursive case

factorial(5)  # 5 * 4 * 3 * 2 * 1 = 120

Tracing through factorial(3) shows what’s actually happening:

factorial(3)
= 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * (2 * 1)
= 6

Each call waits on the one below it, and nothing gets multiplied until factorial(1) finally hits the base case and starts returning values back up the chain.

A Second Example: Fibonacci

The Fibonacci sequence is another classic: each number is the sum of the two before it. Written recursively:

def fibonacci(n):
    if n <= 1:
        return n          # base case
    return fibonacci(n - 1) + fibonacci(n - 2)  # recursive case

fibonacci(6)  # 8

This version is simple to read, but worth knowing its downside: computing fibonacci(n) this way recomputes the same smaller values over and over, which gets slow fast as n grows. fibonacci(5) alone calls fibonacci(3) twice and fibonacci(2) three times, even though each of those calls returns the exact same result every time. A later module covers a faster version built with generators.

Recursion vs. a Loop

Anything recursion can do, a loop can also do. Recursion isn’t magic, it’s a different way of expressing the same repetition. Compare:

def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

Recursion tends to read more naturally when the problem itself is defined recursively (walking a nested folder structure, or a nested dictionary of unknown depth), where a loop would need to manage its own stack of “things to come back to” manually.

Try It

1. Write factorial yourself, and trace through factorial(4) by hand before running it.
2. Write a recursive function sum_to_n(n) that returns the sum of every integer from 1 to n.
3. Add a print(n) as the first line inside fibonacci, then call fibonacci(5) and watch the order calls actually happen in.

Recap

• A recursive function calls itself, and needs both a base case (where it stops) and a recursive case (where it calls itself again with smaller input).
• Skipping or never reaching the base case causes infinite recursion, ending in a RecursionError.
• Recursion and loops can solve the same problems. Recursion tends to read more naturally for problems that are themselves defined recursively.

Next lesson: put functions, parameters, scope, and recursion together across a wide range of small problems.