Recursion

Introduction

Recursion is when a function calls itself. It's a powerful technique for problems that can be broken down into smaller, similar sub-problems.

How recursion works

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)

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

# More efficient with memoization
from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

Assignment