Python Tutorial — Learn Python Step by Step

Python Recursion

Recursion is when a function calls itself to solve a problem by breaking it into smaller sub-problems. Every recursive function needs a base case to stop the recursion.

Basic Recursion: Factorial

# Factorial: n! = n * (n-1) * (n-2) * ... * 1
def factorial(n):
    # Base case: stop recursion
    if n == 0 or n == 1:
        return 1
    # Recursive case: call itself with smaller input
    return n * factorial(n - 1)

print(factorial(5))   # 120 (5*4*3*2*1)
print(factorial(10))  # 3628800

# How it works:
# factorial(5) = 5 * factorial(4)
#              = 5 * 4 * factorial(3)
#              = 5 * 4 * 3 * factorial(2)
#              = 5 * 4 * 3 * 2 * factorial(1)
#              = 5 * 4 * 3 * 2 * 1 = 120

Fibonacci Sequence

# Naive recursive Fibonacci (slow for large n)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))  # 55

# Optimized with memoization (cache results)
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

Practical Recursive Examples

# Sum of a list
def sum_list(lst):
    if not lst:  # base case: empty list
        return 0
    return lst[0] + sum_list(lst[1:])

print(sum_list([1, 2, 3, 4, 5]))  # 15

# Count occurrences in nested structure
def count_items(data):
    """Count all non-list items in a nested list."""
    if not isinstance(data, list):
        return 1
    return sum(count_items(item) for item in data)

nested = [1, [2, 3], [4, [5, 6]], 7]
print(count_items(nested))  # 7

# Flatten a nested list
def flatten(lst):
    result = []
    for item in lst:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

print(flatten([1, [2, [3, 4]], [5, 6]]))  # [1, 2, 3, 4, 5, 6]

# Directory tree traversal
import os

def list_files(path, indent=0):
    """Recursively list all files in a directory."""
    for entry in os.listdir(path):
        full_path = os.path.join(path, entry)
        print(" " * indent + entry)
        if os.path.isdir(full_path):
            list_files(full_path, indent + 2)

Recursion vs Iteration

# Recursive version
def power_recursive(base, exp):
    if exp == 0:
        return 1
    return base * power_recursive(base, exp - 1)

# Iterative version (generally preferred for simple cases)
def power_iterative(base, exp):
    result = 1
    for _ in range(exp):
        result *= base
    return result

# Both produce the same result
print(power_recursive(2, 10))  # 1024
print(power_iterative(2, 10))  # 1024

Recursion Limits and Tail Recursion

import sys

# Python has a default recursion limit of 1000
print(sys.getrecursionlimit())  # 1000

# You can increase it (be careful!)
# sys.setrecursionlimit(5000)

# For deep recursion, convert to iteration
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial_iterative(1000))  # works! No stack overflow

• Every recursive function needs a base case to prevent infinite recursion.
• Use @lru_cache to memoize recursive functions and avoid redundant calculations.
• Python default recursion limit is 1000 — use iteration for deep recursion.
• Recursion is ideal for tree/graph traversal, nested structures, and divide-and-conquer algorithms.
• For simple loops (sum, factorial), iteration is usually clearer and more efficient in Python.