Recursion

Recursion solves a problem by reducing it to smaller versions of the same problem. A recursive function calls itself until it reaches a case that no longer needs another call.

Recursion is common in trees, depth-first search, divide and conquer, and many dynamic programming solutions.

Core Idea

A recursive solution needs two parts: a base case and a recursive case. The base case stops the recursion. The recursive case makes progress toward the base case.

Without a base case, or without progress toward it, recursion does not terminate.

Python Example

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

The base case is n == 0. The recursive case reduces n by one.

Common Confusions

Recursion is not magic. Each call has its own local variables and waits for smaller calls to return.

Python has a recursion limit. Very deep recursion can raise RecursionError, even when the algorithm idea is correct.

When To Use It

Use recursion when the problem naturally splits into smaller similar problems, especially with trees, nested structures, backtracking choices, and divide-and-conquer algorithms.