Recursion
When a function solves a problem by calling itself on a smaller piece of it.
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.
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.