Recursion

Recursion is when a function calls itself to solve a smaller instance of the same problem. Every correct recursive function has a base case that stops the calls and a recursive case that moves toward it.

Why it matters

Recursion is a natural fit for problems with nested or self-similar structure, such as walking a folder tree, parsing nested JSON or traversing a binary tree. The code is often shorter than the loop equivalent. The cost is that each call uses stack memory, so very deep recursion can fail.

Example

def factorial(n):
    if n <= 1:          # base case
        return 1
    return n * factorial(n - 1)   # recursive case

factorial(4) becomes 4 * factorial(3), then 3 * factorial(2), down to factorial(1) which returns 1, and the results multiply back up to 24.

Common mistakes

• Omitting the base case or never moving toward it, which causes infinite recursion and a stack overflow error.
• Recursing thousands of levels deep in languages that do not optimize tail calls; use a loop instead.
• Recomputing the same sub-problem repeatedly, as in naive Fibonacci; cache results.

Related

• Function
• Algorithm
• Stack trace
• Data structure

This page is general information written by our editorial team and updated when documentation changes. Servers and providers differ, so test changes safely first. See our editorial policy and disclaimer.