Recursion

Introduction

Some problems are naturally defined in terms of smaller versions of themselves. A folder contains files and other folders, and each of those folders contains more files and folders — the structure repeats. Recursion is the programming technique that mirrors this idea: a function that calls itself to solve a smaller piece of the same problem.

In this lesson, you will learn what recursion is, why every recursive function needs a base case, how Python tracks recursive calls using the call stack, and when recursion is a better choice than a loop.

What is Recursion?

Recursion happens when a function calls itself, either directly or indirectly, in order to solve a problem. Instead of solving the whole problem in one step, a recursive function solves a small piece of it and then hands off a slightly smaller version of the same problem to another call of itself.

def countdown(n):
    print(n)
    if n > 0:
        countdown(n - 1)

countdown(3)

3
2
1
0

Each call to countdown() prints the current number and then calls countdown() again with a smaller number. Eventually n reaches 0, the condition n > 0 becomes False, and the chain of calls stops.

Base Case & Recursive Case

Every correct recursive function has two essential parts.

Without a base case (or with one that is never reached), a recursive function will call itself forever, eventually causing Python to raise a RecursionError.

def recursive_function(n):
    if n == 0:            # base case
        return 0
    else:                  # recursive case
        return n + recursive_function(n - 1)

Example: Factorial

The factorial of a number n (written n!) is the product of all positive integers from 1 up to n. Factorial is a classic example because it is naturally recursive: 5! is just 5 times 4!.

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

print(factorial(5))

120

factorial(5) calls factorial(4), which calls factorial(3), and so on, until factorial(1) returns 1 directly. Then each pending multiplication completes on the way back up.

Tracing the Call Stack

Every time a function is called, Python pushes a new "frame" onto the call stack to keep track of that call's local variables and where it should return to. Recursive calls stack up the same way — the calls go "down" until the base case is hit, then results are returned "up" the stack one level at a time.

factorial(4)
  → factorial(3)
      → factorial(2)
          → factorial(1) returns 1
      factorial(2) returns 2 * 1 = 2
  factorial(3) returns 3 * 2 = 6
factorial(4) returns 4 * 6 = 24

The calls grow downward until factorial(1) hits the base case, and then each waiting call multiplies its own n by the result it receives, unwinding the stack back to the original call.

Example: Fibonacci Sequence

The Fibonacci sequence is another common recursion example: each number is the sum of the two numbers before it (0, 1, 1, 2, 3, 5, 8, ...).

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

for i in range(8):
    print(fibonacci(i), end=" ")

0 1 1 2 3 5 8 13

Example: Summing a List Recursively

Recursion is not limited to numbers — it also works well on sequences like lists, where the "smaller problem" is simply a shorter list.

def sum_list(numbers):
    if not numbers:            # base case: empty list
        return 0
    return numbers[0] + sum_list(numbers[1:])  # recursive case

print(sum_list([4, 8, 15, 16, 23]))

66

Each call adds the first element to the sum of the rest of the list, until the list becomes empty and the base case returns 0.

Recursion Depth Limit

Python protects itself from infinite recursion by limiting how many recursive calls can be stacked at once. This is called the recursion limit, and by default it is 1000 calls.

import sys

print(sys.getrecursionlimit())

1000

If a recursive function goes past this limit — usually because the base case is missing or unreachable — Python raises a RecursionError.

def broken(n):
    return broken(n + 1)  # never stops

broken(1)

RecursionError: maximum recursion depth exceeded

It is possible to raise the limit with sys.setrecursionlimit(), but this is rarely a good fix — it usually just delays the crash and risks exhausting your computer's actual memory stack. It is almost always better to fix the logic or switch to iteration.

Recursion vs Iteration

Almost anything you can write recursively can also be written with a loop, and vice versa. Choosing between them is about readability and the shape of the problem, not just correctness.

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

print(factorial_iterative(5))

120

Common Mistakes

Best Practices

Frequently Asked Questions

Key Takeaways

Summary

Recursion lets a function solve a problem by calling itself on smaller pieces of that same problem, stopping once it reaches a clearly defined base case. Tracing the call stack — calls going down, results returning up — is the key to understanding how recursive functions actually execute.

In this lesson, you saw recursion applied to factorial, Fibonacci, and summing a list, learned about Python's recursion depth limit, and compared recursion with iteration to know when each is the better tool.