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)

At a glance

Purpose
Scripting and general-purpose applications
File extension
.py
Runs in
Python interpreter
Usually used with
Python standard library and packages

Specifications & further reading

Related Python documentation

def
The def keyword in Python is used to define functions - reusable blocks of code that perform specific tasks. Functions are fundamental to organizing code, avoiding repetition, and making programs more maintainable. A function can accept inputs (parameters), perform operations, and return outputs. Functions are one of the core building blocks of clean, modular Python code.lambda
A lambda is a small, anonymous, single-expression function, created without the def keyword or a name. Lambdas are restricted to a single expression whose result is automatically returned - they can't contain multiple statements or assignments. They're most useful as short, throwaway functions passed as arguments to other functions like sorted(), map(), and filter().return
The return statement exits a function immediately and optionally sends a value back to the caller. A function can return any type - including multiple values as a tuple - or nothing at all, in which case it implicitly returns None. Once return executes, no further code in the function runs, making it useful for early exits as well as producing a final result.*args and **kwargs
*args and **kwargs let a function accept a variable number of arguments. *args collects any extra positional arguments into a tuple, while **kwargs collects extra keyword arguments into a dictionary. The names 'args' and 'kwargs' are just convention - what matters is the * and ** prefixes. This pattern is common in wrapper functions, decorators, and APIs that need to stay flexible about their inputs.