Recursion
A function that solves a problem by calling itself on a smaller version of the same problem, until it reaches a case simple enough to answer directly.
Definition
Every recursive function needs a base case that stops the calls and a step that makes the problem smaller. Each call waits on the call stack until the calls it made return, so very deep recursion can run out of stack space. Tree traversals, divide and conquer, and backtracking are naturally recursive.
In practice
factorial(n) returns 1 when n is 0, and n * factorial(n - 1) otherwise.