Recursion — Functions That Call Themselves

A recursive function calls itself with a simpler input until it hits a base case.

Classic example — factorial:

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

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

Fibonacci:

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

# Slow! Use lru_cache for speed:
from functools import lru_cache

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

Tree/directory traversal:

import os

def list_files(path):
    for item in os.listdir(path):
        full = os.path.join(path, item)
        if os.path.isdir(full):
            list_files(full)  # recurse into directory
        else:
            print(full)

Recursion limit: Python defaults to 1000. Increase with sys.setrecursionlimit(). For deep recursion, convert to iterative with a stack.

Reference:

Wikipedia: Recursion

https://en.wikipedia.org/wiki/Recursion_(computer_science)