Codectionary / Developer documentation / Python

Recursion

Recursion is when a function calls itself to solve a smaller instance of the same problem. Every recursive function needs a base case - a condition that stops the recursion - and a recursive case that moves progressively toward that base case. Recursion is a natural fit for problems with a self-similar structure, like tree traversal, factorial calculation, and Fibonacci sequences, though it's not always the most efficient approach in Python due to function call overhead.

Syntax

def func(n):\n    if base_case:\n        return value\n    return func(smaller_n)

Examples

Factorial with Recursion

A classic first example of recursion.

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

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

Fibonacci with Recursion

Computing Fibonacci numbers, where each call makes two further recursive calls.

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

for i in range(8):
    print(fibonacci(i), end=" ")  # 0 1 1 2 3 5 8 13

Recursion with an Accumulator

Passing a running total through recursive calls, a common technique for building efficient recursive functions.

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

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

Recursive Directory-Style Traversal

A practical use case: recursively walking a nested structure, like folders inside folders.

tree = {
    "name": "root",
    "children": [
        {"name": "src", "children": [
            {"name": "app.py", "children": []}
        ]},
        {"name": "README.md", "children": []}
    ]
}

def print_tree(node, depth=0):
    print("  " * depth + node["name"])
    for child in node["children"]:
        print_tree(child, depth + 1)

print_tree(tree)

Best practices

  • Always define a clear base case that stops the recursion - forgetting one causes infinite recursion and a RecursionError
  • Make sure each recursive call moves closer to the base case (smaller input, decremented counter, etc.)
  • Use @functools.lru_cache for recursive functions like Fibonacci that repeat the same calculations, to avoid redundant work
  • Consider an iterative (loop-based) solution instead of recursion for very deep problems, since Python has a limited default recursion depth (usually 1000)

Runtime & versions

Python interpreter. Feature availability depends on the language and runtime version used by your project; consult the official reference below.

Python language reference

Specifications & further reading