Recursion

Introduction

Recursion — a function that calls itself — is natural for tree/graph traversal, divide-and-conquer, and parsing. Python's default recursion limit is 1000 frames.

Understanding the topic

Core concepts to understand:

• Always have a base case.
• Each recursive call must move toward the base.
• sys.setrecursionlimit can raise the cap.
• Use @functools.lru_cache for memoization.

Syntax reference

Visual flow / code:

from functools import lru_cache

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

print(fib(50))  # instant with memoization

Execution workflow

Real-world use

Memoized recursion turns exponential algorithms (naive fib) into linear ones — a one-line decorator. Standard tool in dynamic programming.

Best practices

• Always define the base case first.
• Add @lru_cache for overlapping subproblems.
• Prefer iteration when depth is huge.

Common mistakes

• Missing base case → RecursionError.
• Python has no tail-call optimization.

Hands-on exercise

Interview preparation — practice these questions:

• What's tail recursion?
• Why does Python lack TCO?
• What is memoization?

Summary

In summary: Base case + smaller problem. lru_cache supercharges recursion.