Recursive Functions: Functions That Call Themselves

After completing this topic

You will be able to explain how recursive functions work, understand the importance of the base case, and solve simple recursive problems yourself.

What is Recursion?

Recursion is when a function calls itself.

python

def countdown(n):
    if n <= 0:
        print("Launch!")
        return
    print(n)
    countdown(n - 1)  # Calls itself

countdown(5)
# 5
# 4
# 3
# 2
# 1
# Launch!

countdown(5) calls countdown(4), countdown(4) calls countdown(3), and so on, until countdown(0) prints "Launch!" and stops.

That's all there is to recursion. It has two components:

Base Case: if n <= 0 — the condition for when to stop calling itself.
Recursive Case: countdown(n - 1) — calling itself, but making the problem smaller.

Why is the Base Case Essential?

Without a base case, the function will call itself infinitely.

python

def infinite():
    print("Help!")
    infinite()  # Calls itself forever

infinite()
# Help!
# Help!
# Help!
# ...
# RecursionError: maximum recursion depth exceeded

Python allows recursion up to a limit of 1,000 times by default. After that, it will forcibly terminate with a RecursionError. This is a safety measure to prevent infinite recursion from exploding memory usage.

Factorial: A Classic Example of Recursion

5! = 5 × 4 × 3 × 2 × 1 = 120

We can think of factorial recursively: 5! = 5 × 4!

python

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

print(factorial(5))  # 120

Following the call sequence:

text

factorial(5)
  → 5 * factorial(4)
       → 4 * factorial(3)
            → 3 * factorial(2)
                 → 2 * factorial(1)
                      → 1  (base case!)
                 ← 2 * 1 = 2
            ← 3 * 2 = 6
       ← 4 * 6 = 24
  ← 5 * 24 = 120

The function "goes deep" and then "comes back up" with the result.

The Call Stack: How Recursion Works

Each time a function is called, the computer stores the current state in a memory area called a stack.

text

factorial(5) called → Stack: [factorial(5)]
factorial(4) called → Stack: [factorial(5), factorial(4)]
factorial(3) called → Stack: [factorial(5), factorial(4), factorial(3)]
factorial(2) called → Stack: [factorial(5), factorial(4), factorial(3), factorial(2)]
factorial(1) called → Stack: [factorial(5), factorial(4), factorial(3), factorial(2), factorial(1)]
factorial(1) returns → Stack: [factorial(5), factorial(4), factorial(3), factorial(2)]
factorial(2) returns → Stack: [factorial(5), factorial(4), factorial(3)]
...

As the recursion gets deeper, the stack grows. Python's default limit of 1,000 is because each item on the stack takes up memory, and if it gets too deep, the memory will be exhausted.

Fibonacci: A Pitfall of Recursion

python

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))  # 55
print(fib(30))  # 832040 — but slow!
# print(fib(50))  # Never finishes...

The code is concise, but fib(50) will never finish. This is because it repeatedly calculates the same values.

text

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2) ← repeated
│   │   └── fib(1)
│   └── fib(2) ← repeated
└── fib(3) ← repeated
    ├── fib(2) ← repeated
    └── fib(1)

fib(2) is calculated multiple times. For fib(30), this happens millions of times, and for fib(50), billions of times.

Solving with Memoization

python

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_fast(n):
    if n <= 1:
        return n
    return fib_fast(n - 1) + fib_fast(n - 2)

print(fib_fast(50))   # 12586269025 — instant!
print(fib_fast(100))  # 354224848179261915075

@lru_cache stores the results of calculations and returns them if the same input is called again. This eliminates redundant calculations, reducing the complexity from O(2^n) to O(n).

Recursion vs. Iteration

The same problem can often be solved with iteration as well.

python

# Recursion
def factorial_rec(n):
    if n <= 1:
        return 1
    return n * factorial_rec(n - 1)

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

Comparison	Recursion	Iteration
Readability	Intuitive if the problem is inherently recursive	Simpler repetition can be more clear
Performance	Call stack overhead	Generally faster
Memory	Uses memory proportional to the stack depth	O(1)
Suitable Problems	Tree traversal, divide and conquer, permutations/combinations	Simple repetition, cumulative calculations

Rule: If the structure of the problem is naturally recursive (trees, graphs, divide and conquer), use recursion. If it's simple repetition, use a for loop.

Practical Example: Directory Traversal

python

import os

def list_all_files(directory, indent=0):
    """Recursively list all files in a directory tree."""
    items = sorted(os.listdir(directory))
    for item in items:
        path = os.path.join(directory, item)
        print("  " * indent + item)
        if os.path.isdir(path):
            list_all_files(path, indent + 1)  # subdirectory → recurse

list_all_files("project")
# project
#   app.js
#   routes
#     users.js
#     posts.js
#   public
#     css
#       style.css
#     index.html

A folder contains folders, which contain more folders - this is a classic recursive problem. If you don't know how many levels deep it goes, but the same pattern repeats, recursion is natural.

Key Takeaways

Concept	Summary
Recursion	A function calling itself
Base Case	The termination condition for when to stop recursing (essential)
Recursive Case	Making the problem smaller and calling itself
Call Stack	Stores the state of each call in memory (Python limit of 1,000)
Memoization	Prevents redundant calculations (`@lru_cache`)

At first, recursion might seem strange: "If a function calls itself, won't it cause an infinite loop?" The key is that each time, the problem gets smaller, and eventually, it reaches the base case. Understanding this pattern will allow you to understand many algorithms naturally, such as tree traversal, sorting (merge sort), combinations/permutations, and graph traversal (DFS).

Practical Pattern: Traversing Nested Dictionaries

If you encounter a nested structure of unknown depth, such as in JSON or configuration files, recursion is a natural fit.

python

def flatten_dict(d, prefix=""):
    result = {}
    for key, value in d.items():
        full_key = f"{prefix}.{key}" if prefix else key
        if isinstance(value, dict):
            result.update(flatten_dict(value, full_key))
        else:
            result[full_key] = value
    return result

config = {
    "database": {
        "host": "localhost",
        "port": 5432,
        "credentials": {
            "user": "admin",
            "password": "secret"
        }
    },
    "debug": True
}

print(flatten_dict(config))
# {
#   'database.host': 'localhost',
#   'database.port': 5432,
#   'database.credentials.user': 'admin',
#   'database.credentials.password': 'secret',
#   'debug': True
# }

This pattern is often used in logging systems, configuration management, and Elasticsearch indexing.

BioPlayground

Recursive Function — A Function That Calls Itself

Recursive Functions: Functions That Call Themselves

After completing this topic

What is Recursion?

Why is the Base Case Essential?

Factorial: A Classic Example of Recursion

The Call Stack: How Recursion Works

Fibonacci: A Pitfall of Recursion

Solving with Memoization

Recursion vs. Iteration

Practical Example: Directory Traversal

Key Takeaways

Practical Pattern: Traversing Nested Dictionaries

💬 Questions & Comments