# Recursion

> When a function solves a problem by calling itself on a smaller piece of it.

- Level: Intermediate
- Topics: Software
- URL: https://tidbit.legios.com.ar/recursion/
- In Spanish: [Recursión](https://tidbit.legios.com.ar/es/recursion/)

**Recursion** is a way of solving a problem by breaking it into a smaller version of the same problem, and solving that one the same way. In code, it means a function that calls itself. To add up the sizes of everything in a folder, a recursive function adds the files it sees and, for each subfolder, calls itself on that subfolder, which does the same, and so on down.

Every recursive function needs a **base case**: a version of the problem so small that the answer is obvious and no further call is needed, like an empty folder whose size is zero. Without it the function keeps calling itself forever. In practice the program runs out of the memory it uses to track pending calls (the call stack) and crashes with an error known as a **stack overflow**, the same name the popular programming Q&A site took.

Recursion fits naturally anything shaped like a tree: folders inside folders, comments with replies to replies, the structure of a web page, or a sorting method that splits a list in halves, sorts each half and merges them. Anything written recursively can also be written with an ordinary loop, and sometimes the loop is faster or safer; programmers pick whichever version is clearer for the problem.

## An analogy

Russian nesting dolls. To find the smallest doll you open one, and inside is the same problem again, a bit smaller, until you reach the tiny solid one that does not open: the base case.

## Keep in mind

- A recursive function calls itself on a smaller version of the problem.
- It needs a base case that stops the calls.
- Too many nested calls exhaust the call stack: a stack overflow.
- Ideal for tree-shaped data like folders, threads of replies or web pages.

## Go deeper

- [Recursion (MDN glossary)](https://developer.mozilla.org/en-US/docs/Glossary/Recursion)
- [Recursion (computer science) on Wikipedia](https://en.wikipedia.org/wiki/Recursion_(computer_science))

## Related terms

- [Website](https://tidbit.legios.com.ar/website/): A set of web pages under one address, stored on a server and opened in a browser.
- [Cores and threads](https://tidbit.legios.com.ar/cpu-cores-and-threads/): Why a CPU is really several processors, and why it can juggle even more tasks.
