Base Cases and Recurrence

This concept is the heart of recursion — the technique that lets a program solve a big problem by solving a smaller version of itself. Master it, and you unlock Depth-First Search with Backtracking (how a chess engine or a puzzle solver explores possibilities), Stack Memory Behaviour (why a wrongly-written recursion crashes), Tail Recursion (how some recursions become loops), and Tower of Hanoi (a classic puzzle whose solution is three lines of code). Without it, these topics are just magic. With it, they are arithmetic.

Think of a queue at a ticket counter. The person at the front is served first — that's the base case. Everyone behind is waiting on the person ahead of them — that's the recursion. Now imagine someone asks the last person in the queue, 'How many people are ahead of you?' They don't count everyone; they ask the person in front, 'How many ahead of you?' That person asks the next, and so on, until the front person says 'Zero' (the base case). That answer travels back up, each person adding one, until the last person learns the total. That's recursion: the answer to a big question is built from the answer to a smaller question, and the smallest question has a fixed answer that stops the chain. Base cases and the recurrence are the two halves of this. The base case is the 'Zero' — the stopping point. The recurrence is the 'add one' — the rule that connects each case to a smaller one. If you leave out the base case, the chain never ends — the program keeps asking 'how many ahead of you?' forever, until it runs out of memory. If you get the recurrence wrong, the chain gives you a wrong answer, even though it stops correctly.

Imagine you are a tour guide leading a group down a narrow staircase in a cave. You cannot see the bottom, and you cannot turn around. To know how many steps there are, you ask the person in front of you, 'How many steps below you?' They ask the person in front of them, and so on, until the last person reaches the cave floor. That last person says, 'Zero — I am on the floor' (the base case). That answer passes back up, each person adding one, until you know the total. The rule 'add one to whatever the person below you said' is the recurrence. The cave floor is the base case. Now, what happens if there is no cave floor — just a hole going down forever? The question 'how many steps below you?' never gets a 'Zero' answer; each person asks the next, and the chain never ends. That is infinite recursion. What happens if, instead of saying 'Zero', the last person mistakenly says 'One'? The total is wrong by one at every step above — that is a wrong base case. And what if, instead of adding one, each person adds two? Then the total is double the truth — that is a wrong recurrence. Here is where the analogy stops: in the cave, each person is a separate human; in a computer, recursion reuses the same code, not separate copies of it. The same function calls itself, with different numbers, over and over. Also, in the cave, the chain can be arbitrarily long; in a computer, the chain is limited by memory — each unanswered question occupies a slot in the computer's stack, and too many slots run the program out of memory (Stack Memory Behaviour). So the analogy captures the idea of 'smaller and smaller until a stop', but not the reality that the computer is a single machine juggling all the unanswered questions at once.

A recursion is a computation defined by two parts: one or more base cases, which give answers directly without further recursion, and a recurrence relation, which expresses the answer for a given case in terms of the answers to strictly smaller cases.

You have no prior notes, so this page builds from arithmetic alone. It sits under the parent concept of Recursion, and it is the foundation for the neighbouring topics you will study later: Depth-First Search with Backtracking (which uses recursion to explore choices), Stack Memory Behaviour (which explains why deep recursion crashes), Tail Recursion (which converts some recursions into loops), and Tower of Hanoi (a classic three-line recursion). This concept also connects to Discrete Mathematics — the formal study of counting and structures — because the recurrence relation is precisely what you write down when you analyse how many steps a recursive algorithm takes.