Book 01 · Programming FundamentalsPage 48 of 56

Recursion

In Turkish: Özyineleme
Pronunciation: ri-KUR-zhun or ri-KUR-shun

Updated September 29, 20262 min read

In short

Recursion is a technique in which a function solves a problem by calling itself on smaller versions of the same problem until it reaches a simple base case.

What is recursion?

Recursion is when a function calls itself. Each call works on a smaller or simpler piece of the original problem, and the results are combined to produce the final answer. It is a natural fit for problems that are defined in terms of smaller copies of themselves.

Every recursive function needs two parts. The base case is a simple situation the function can answer directly, without calling itself again. The recursive case breaks the problem down and calls the function again, moving closer to the base case each time. Without a base case, the function would keep calling itself until the program crashes.

Russian nesting dolls are a common analogy for recursion: to reach the smallest doll, you open one doll, then do the same thing to the doll inside, until there is nothing left to open. In software, recursion is widely used to walk through tree-shaped data such as folders on a disk, the DOM, or nested JSON, and in algorithms like merge sort and quicksort.

Recursion is often compared with iteration, which repeats steps using loops like for and while. Anything written recursively can also be written with a loop, and loops are usually more memory-efficient because each recursive call takes up space on the call stack. If recursion goes too deep, the program can fail with a stack overflow error.

At a glance

Each call waits for a smaller one. The base case stops the descent, and the results multiply on the way back up.

Key takeaways

A recursive function calls itself on a smaller version of the problem.
It must have a base case that stops the recursion.
Each call uses space on the call stack; very deep recursion can cause a stack overflow.
It is well suited to trees, nested data, and divide-and-conquer algorithms.

Example

Calculating a factorial recursivelyjavascript

// Factorial: 5! = 5 * 4 * 3 * 2 * 1
function factorial(n) {
  if (n <= 1) return 1;        // base case: stop here
  return n * factorial(n - 1); // recursive case: a smaller problem
}

console.log(factorial(5)); // 120

Readers ask

What is a base case in recursion?

The base case is the condition under which a recursive function returns a result directly instead of calling itself again. It is what stops the recursion from running forever.

What is the difference between recursion and iteration?

Recursion solves a problem by having a function call itself, while iteration repeats steps using a loop. Both can solve the same problems; recursion is often clearer for nested structures, while loops typically use less memory.

What causes a stack overflow in recursion?

Each function call is kept on the call stack until it finishes. If recursion has no base case or goes too deep, the stack runs out of space and the program throws an error, such as RangeError: Maximum call stack size exceeded in JavaScript.