Recursion

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem, until the problem is small enough to answer directly. Think of Russian nesting dolls. To count them, you open one and say '1 + however many are inside'. Opening the inside is the same task, just smaller. Eventually you reach the tiny solid doll with nothing inside: that's the base case, where you stop and answer 0. Every recursion needs two things: a base case (when to stop) and a recursive step (how to shrink toward the base). Forget the base case and it calls itself forever, crashing with a stack overflow. The magic is that you describe only one layer honestly, and the layers stack up to solve the whole thing.