Recursion

A function that calls itself. Every recursion has two parts:

1. Base case — when do we stop?
2. Recursive case — call ourselves with a smaller subproblem.

When it shines

• Tree / graph traversals
• Anything naturally defined "in terms of itself" (factorial, fib, parsers)
• Quick & dirty divide-and-conquer

Pitfalls

• Forgetting the base case → RecursionError
• Python's default recursion limit is ~1000; deep recursion needs sys.setrecursionlimit or an iterative rewrite.

Try it

1. Write a recursive flatten([1, [2, [3, 4]]]) → [1, 2, 3, 4].
2. Use recursion to reverse a list.