# Recursion

Notes on recursion from various sources:

## Outline

Recursion is when a function calls itself.

At least one base case is needed to end the recursion—otherwise, the algorithm recurses until it overflows the stack. There are recursive and iterative (non-recursive) algorithms. When you are writing a recursive function involving an array, the base case is often an empty array or an array with one element. In other words, the case in which the method will not recurse is the base case.

Divide-and-conquer algorithms are all recursive algorithms:

1. Figure out a simple case as the base case.
2. Figure out how to reduce your problem and get to the base case.

You need to move closer to the base case with every recursive call.

``````function countdown(number) {
console.log(number);
if (number === 0) {
// base case
return;
} else {
countdown(number - 1); // moving closer to base case
}
}

countdown(10);``````

Recursion is useful for tasks that can be defined in terms of similar subtasks. For example, sort, search, and traversal problems often have simple recursive solutions. A recursive function performs a task in part by calling itself to perform the subtasks. At some point, the function encounters a subtask that it can perform without calling itself. This case, in which the function does not recurse, is called the “base case”; the former, in which the function calls itself to perform a subtask, is referred to as the “recursive case”.

Every recursive case must eventually lead to a base case. Every recursive call reduces the original problem, bringing it increasingly closer to a base case until it becomes that case.

## Performance

There is no performance benefit to using recursion; in fact, loops are sometimes better for performance. Each function call takes up some memory, and when your stack is too tall, your computer is saving information for many function calls.

Recursion is powerful, but it is not always the best approach, and rarely is it the most efficient approach. This is due to the relatively large overhead for function calls on most platforms. For a simple recursive function, most computer architectures spend more time on call overhead than on the actual calculation. Iterative functions, which use looping constructs instead of recursive function calls, do not suffer from this overhead and are frequently more efficient.

Iterative solutions are usually more efficient than recursive solutions.

Any problem that can be solved recursively can be solved nonrecursively with iterations. Recursion has some negative aspects: it uses up too much time and too much memory. Why, then, should you use it? In some cases, using recursion enables you to specify a clear, simple solution for an inherently recursive problem that would otherwise be difficult to obtain. Examples are the directory-size problem, the Tower of Hanoi problem, and the fractal problem, which are rather difficult to solve without using recursion.

## Tail recursion

A tail-recursive method has no pending operations after a recursive call.