Python Recursion Examples: A Practical Guide

Home

This is a collection of practical recursion examples in Python. Each example builds on the previous concepts, starting simple and progressing to more complex real-world use cases.

The Two Rules of Recursion

Before diving into examples, remember these two essential rules:

Base Case - Every recursive function needs a stopping condition
Progress Toward Base Case - Each recursive call must move closer to that stopping condition

Example 1: Countdown (Simplest Start)

The countdown function is the perfect introduction to recursion. It demonstrates the basic pattern without any complex logic.

def countdown(n):
    """Count down from n to 0 using recursion"""
    # Base case: stop when we hit 0
    if n <= 0:
        print("🚀 Blast off!")
        return  # This stops the recursion!

    # Recursive case: print and call again with smaller number
    print(f"Counting: {n}")
    countdown(n - 1)  # Call ourselves with n-1

countdown(3)

Output:

Counting: 3
Counting: 2
Counting: 1
🚀 Blast off!

What’s happening:

The base case is n <= 0 - when this is true, we return instead of calling ourselves again
Each recursive call passes n - 1, moving us closer to zero
The function calls stack up: countdown(3) → countdown(2) → countdown(1) → countdown(0) (base case)

Example 2: Factorial (Classic Example)

Factorial is the “Hello World” of recursion. It’s mathematically defined recursively: n! = n × (n-1)!

def factorial(n):
    """Calculate factorial using recursion"""
    # Base case: 0! = 1 and 1! = 1
    if n <= 1:
        return 1

    # Recursive case: n! = n × (n-1)!
    result = n * factorial(n - 1)
    return result

print(factorial(5))  # Output: 120

Breaking down factorial(5):

factorial(5) = 5 × factorial(4)
factorial(4) = 4 × factorial(3)
factorial(3) = 3 × factorial(2)
factorial(2) = 2 × factorial(1)
factorial(1) = 1  ← Base case!

Now it unwinds:
factorial(2) returns 2 × 1 = 2
factorial(3) returns 3 × 2 = 6
factorial(4) returns 4 × 6 = 24
factorial(5) returns 5 × 24 = 120

Example 3: Sum of List (Processing Data)

This example shows how to recursively process a data structure by breaking it into smaller pieces.

def sum_list(numbers):
    """Sum a list using recursion"""
    # Base case: empty list has sum of 0
    if not numbers:
        return 0

    # Recursive case: first element + sum of the rest
    first = numbers[0]
    rest_sum = sum_list(numbers[1:])
    return first + rest_sum

my_list = [1, 2, 3, 4, 5]
print(sum_list(my_list))  # Output: 15

The key idea:

Take the first element
Recursively sum the rest of the list
Add them together
When the list is empty, return 0 (base case)

Example 4: Fibonacci (Multiple Recursive Calls)

This is a famous example that makes two recursive calls, creating a branching pattern. Note: this is inefficient but great for learning!

def fibonacci(n):
    """Get the nth Fibonacci number"""
    # Base cases: fib(0) = 0, fib(1) = 1
    if n <= 0:
        return 0
    if n == 1:
        return 1

    # Recursive case: fib(n) = fib(n-1) + fib(n-2)
    return fibonacci(n - 1) + fibonacci(n - 2)

# First 10 Fibonacci numbers
for i in range(10):
    print(f"fib({i}) = {fibonacci(i)}")

Output:

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34

What’s different here?

Two base cases are needed (for 0 and 1)
Each call branches into two more calls, creating a tree structure
This is why naive Fibonacci is so slow - it recalculates the same values many times

Example 5: Binary Search (Practical Use Case)

Binary search is a real-world algorithm where recursion shines. It efficiently finds items in sorted lists.

def binary_search(arr, target, low=0, high=None):
    """Search for target in sorted array using recursion"""
    if high is None:
        high = len(arr) - 1

    # Base case: target not found
    if low > high:
        return -1

    # Find middle point
    mid = (low + high) // 2

    # Base case: target found!
    if arr[mid] == target:
        return mid

    # Recursive case: search left or right half
    if arr[mid] > target:
        return binary_search(arr, target, low, mid - 1)  # Search left
    else:
        return binary_search(arr, target, mid + 1, high)  # Search right

sorted_list = [1, 3, 5, 7, 9, 11, 13, 15]
result = binary_search(sorted_list, 7)
print(f"Found 7 at index: {result}")  # Output: 3

Why recursion works well here:

Each call eliminates half the remaining elements
The problem naturally divides into smaller, identical subproblems
Much cleaner than the iterative version with manual index tracking

Example 6: Directory Tree Listing (Real-World Use)

Recursion is perfect for hierarchical structures like file systems, where folders contain folders.

import os

def list_files(directory, prefix=""):
    """Recursively list all files in a directory tree"""
    # Base case: directory doesn't exist
    if not os.path.exists(directory):
        return

    # List all items in directory
    try:
        items = os.listdir(directory)
    except PermissionError:
        return

    for i, item in enumerate(items):
        path = os.path.join(directory, item)
        is_last = i == len(items) - 1

        # Tree branch characters
        connector = "└── " if is_last else "├── "
        print(f"{prefix}{connector}{item}")

        # Recursive case: if it's a directory, explore it
        if os.path.isdir(path):
            extension = "    " if is_last else "│   "
            list_files(path, prefix + extension)

# Usage (uncomment to try):
# list_files(".")

Sample output:

├── files
│   ├── doc1.txt
│   └── doc2.txt
└── images
    └── photo.jpg

Visualizing the Call Stack

Understanding what’s happening on the call stack is crucial. Here’s a factorial function that shows its own execution:

def factorial_with_trace(n, depth=0):
    """Factorial that shows the recursive calls"""
    indent = "  " * depth
    print(f"{indent}→ factorial({n}) called")

    if n <= 1:
        print(f"{indent}← Base case! Returning 1")
        return 1

    print(f"{indent}→ Calling factorial({n-1})")
    result = n * factorial_with_trace(n - 1, depth + 1)
    print(f"{indent}← Returning {n} × {result//n} = {result}")
    return result

factorial_with_trace(3)

Output:

→ factorial(3) called
→ Calling factorial(2)
  → factorial(2) called
  → Calling factorial(1)
    → factorial(1) called
    ← Base case! Returning 1
  ← Returning 2 × 1 = 2
← Returning 3 × 2 = 6

Each arrow pointing right (→) is a new function call being pushed onto the stack. Each arrow pointing left (←) is a function returning and being popped off the stack.

Recursion vs Iteration

Some problems can be solved either way. Here’s a comparison:

# Recursive approach
def sum_recursive(n):
    if n <= 0:
        return 0
    return n + sum_recursive(n - 1)

# Iterative approach
def sum_iterative(n):
    total = 0
    for i in range(n + 1):
        total += i
    return total

print(sum_recursive(5))   # 15
print(sum_iterative(5))   # 15

When to use which:

Iteration is usually faster and uses less memory in Python
Recursion is often more readable for problems that are naturally recursive (trees, divide-and-conquer)

Tail Recursion (Advanced Concept)

Tail recursion is when the recursive call is the last operation in the function. Some languages optimize this, but Python doesn’t.

# Not tail recursive (must multiply after recursive call returns)
def factorial_non_tail(n):
    if n <= 1:
        return 1
    return n * factorial_non_tail(n - 1)  # Multiplication happens AFTER

# Tail recursive (recursive call is the last operation)
def factorial_tail(n, accumulator=1):
    if n <= 1:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)  # Call is LAST

The tail-recursive version passes the running total as a parameter (accumulator), so no computation is needed after the recursive call returns.

Key Takeaways

Base case - Every recursive function needs a stopping condition
Progress - Each call must move toward the base case
Memory - Recursion uses more memory than loops (stack frames)
Use cases - Great for trees, graphs, divide-and-conquer algorithms
Watch out - Python has a recursion limit (~1000 calls by default)

Why Recursion is Slower in Python

Function call overhead - Each recursive call creates a new stack frame, saves local variables, and eventually tears it all down
No tail-call optimization - Languages like Haskell or Scala convert certain recursive calls into loops automatically. Python deliberately doesn’t implement this
Stack limit - Python caps you at ~1000 frames by default. Iteration has no such limit

When recursion is still preferred:

Tree traversal (each node has child nodes - same structure)
Merge sort / quicksort (divide and conquer)
Directory traversal (folders inside folders)
Any problem that’s naturally recursive!

The goal of recursion is clarity, not speed.

Tags: PythonRecursionAlgorithmsProgramming