recursion
/ rih-KUR-zhun /
Recursion is when a function solves a problem by calling itself on a smaller piece of the very same problem. Instead of one big loop, it says 'handle a little bit, then hand the rest back to me' — over and over, each call chewing off a slightly smaller bite, until there's nothing left to do.
Think of standing in a long line and wanting to know your place. You can't see the front, so you tap the person ahead and ask 'what number are you?' They don't know either, so they ask the person in front of THEM, and so on — until someone at the very front says 'I'm number 1.' That answer flows back down the line, each person adding one, until it reaches you.
The part that keeps it from spinning forever is the base case: the simplest version of the problem that has an answer right away, with no further self-call. 'Person at the front is number 1' is the base case. Forget it, and the function calls itself endlessly and crashes — a 'stack overflow.' Every recursion needs a way to get smaller, and a place to stop.
def factorial(n):
if n == 1: # base case — stop here
return 1
return n * factorial(n - 1) # call itself on a smaller nfactorial(4) becomes 4 × factorial(3) … down to the base case, then it all multiplies back up.
Programmer's in-joke: to understand recursion, you must first understand recursion.