A recursive function calls itself with a smaller version of the same problem. Every recursive solution has two parts: a base case that returns directly, and a recursive case that reduces the problem and combines results.
Why it works
Recursion is the algorithmic expression of induction. If your function is correct for the base case, and assuming it works for size it also works for size , then by induction it works for all sizes. Writing the recursive case correctly = writing the induction step.
The call stack
Each recursive call gets its own stack frame holding parameters, locals, and the return address. The call stack grows by one frame per recursion level and shrinks by one on each return. Default stack size is usually around bytes — enough for – frames depending on locals.
Stack overflow
Recursion that's too deep blows the stack. Symptoms: a hard crash, RecursionError in Python, StackOverflowError in Java. Fixes: switch to iteration with an explicit stack, increase the stack limit (sys.setrecursionlimit in Python), or tail-recursion-optimize (some languages, not Python or Java).
Tail recursion
A recursive call is in tail position if it's the last thing the function does before returning. Compilers in some languages (Scheme, Scala, Haskell, occasionally C with optimization) can rewrite tail-recursive calls into a loop, reusing the same frame. Python doesn't do this — recursive idioms in Python often need to be converted to iterative for large inputs.
When recursion shines
When the problem decomposes naturally into smaller versions of itself: tree traversals, divide-and-conquer (merge sort, quicksort), backtracking (next lesson), and dynamic programming (later section). The recursive code matches the problem's structure, often making it the clearest implementation even when an iterative version is faster.