Algorithms
What Is Recursion?
Recursion is when a function solves a problem by calling itself on a smaller version of the same problem until it reaches a simple base case.
Definition
Recursion is a technique where a function calls itself. Each call works on a smaller piece of the problem, and the calls stop at a base case that can be answered directly.
It fits problems that contain smaller copies of themselves, such as walking a folder tree, traversing a tree data structure or computing a factorial.
How it works
Every recursive function needs a base case, which stops the calls, and a recursive case, which moves toward the base case. Without a base case the calls never end and the program fails with a stack overflow.
Each call waits on the call stack until the calls below it return. Python allows about 1,000 nested calls by default.