Recursion

Recursion

A recursive function calls itself. Every recursive function needs:

1. A base case — the simplest input that doesn't recurse
2. A recursive case — reduce the problem and recurse

Classic Example: Factorial

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

factorial(5)  # 120

Tree Traversal

Recursion shines on recursive data structures like trees and nested lists:

def depth(tree):
    if not isinstance(tree, list):
        return 0
    return 1 + max(depth(child) for child in tree)

Memoization

Avoid recomputing by caching results. The @lru_cache decorator wraps fib so previously computed values are returned from a cache instead of being recalculated — turning exponential time into linear:

from functools import lru_cache

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

Mutual Recursion

Two functions calling each other:

def is_even(n):
    if n == 0: return True
    return is_odd(n - 1)

def is_odd(n):
    if n == 0: return False
    return is_even(n - 1)

Your Task

Implement flatten(nested) that recursively flattens an arbitrarily-nested list of integers into a single flat list.

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