Recursion

Recursion means a function calling itself while it runs. A hard problem is reduced to the same problem on smaller data, and this continues until the simplest case is reached. Every correct recursive function has two parts: a base case (the simplest case, answered without recursion) and a recursive step (the function calls itself with smaller data).

The classic example is factorial: n! = n · (n − 1)!, with 0! = 1. In Python it is written def f(n): return 1 if n == 0 else n * f(n - 1). Calling f(3) computes 3 * f(2), then 2 * f(1), then 1 * f(0); once f(0) is reached the answers return in reverse order and the result is 6. Without a base case the function would call itself forever.

Fibonacci numbers are also defined recursively: fib(n) = fib(n - 1) + fib(n - 2), fib(0) = 0, fib(1) = 1. Written naively, however, the same values are computed over and over and the time grows very fast with n; for example, fib(40) takes noticeably long this way. In such cases it is better to store intermediate results or to use a loop.

Each recursive call occupies memory, so very deep recursion leads to overflow. In Python the depth is limited (usually about 1000 calls), and exceeding it raises RecursionError. Recursion suits tree-like data and divide-and-conquer algorithms, while for simple repetition a loop is often faster and safer.

Key takeaways

• Recursion is a function calling itself with smaller data.
• Recursion always needs a base case and a recursive step.
• Without a base case the recursion never ends and an error occurs.
• Naive recursive Fibonacci is slow because it recomputes the same values.
• Recursion depth in Python is limited (about 1000).