# Base Cases and Recurrence

The terminating conditions of a recursion and the rule relating a case to smaller ones — together a complete definition of the computation.

**Rests on:** Recursive Thinking

**Leads to:** Depth-First Search with Backtracking, Stack Memory Behaviour

*Mathematical Foundations · Recursion*


## Why learn this

This concept is the foundation for any technique where a problem is solved by breaking it down into smaller versions of itself. Mastering this allows you to build tools like maze-solving programs, code that can undo mistakes in complex tasks, and algorithms that efficiently navigate large data structures. Without understanding how these self-referential steps work, such programs appear as magic boxes. With it, they become predictable logic you can construct yourself.


## The intuition

Think of a long queue at a ticket counter. The person standing directly at the window gets served first — this is your stopping point, your 'base case'. Everyone else in line waits for the person ahead of them to finish before they get their turn. Now, imagine someone asks the person at the very back of the line, 'How many people are in front of you?' They don't count everyone individually. Instead, they shout the question to the person directly in front: 'How many people are in front of YOU?' That person does the same, shouting back until it reaches the person at the window. The person at the window simply answers, 'Zero'. This answer travels back up the line. Each person adds one to the number they received and passes it on. Finally, the person at the back gets the total count. This process has two essential halves: the stopping point (the base case) and the rule for connecting each person's count to the one before them (the recurrence). If there were no person at the window — no one who could say 'Zero' — the question would echo endlessly until the system ran out of time or memory. If the rule was wrong, say, adding two instead of one, the final answer would be incorrect, even though the chain eventually stopped.


## An analogy

Imagine you are a tour guide leading a group down a narrow, dark staircase in a cave. You cannot see the bottom, and you cannot turn around to count steps from the top. To know how many steps remain to the floor, you ask the person directly in front of you, 'How many steps are below you?' That person asks the next, and so on, until the message reaches the very last person at the bottom. That last person stands on solid ground and says, 'Zero.' This answer travels back up: each person adds one step to the number they received and passes it forward. You finally know the total. The rule 'add one' is your recurrence; the floor being underfoot is your base case. Here is where the analogy ends: in a real cave, these are separate people shouting down steps. In a computer program, a single block of code calls itself repeatedly, managing all those simultaneous 'waiting' moments by stacking them in memory until the bottom is reached.


## Definition

A recursive process consists of two parts: a base case, which provides a direct answer for the smallest possible scenario without further division, and a recurrence rule, which defines how to calculate the answer for any larger scenario using the answers from smaller ones. A valid recursion must always reach the base case eventually to produce a result.


## How it connects

This concept is the core mechanism of Recursion. It directly supports Depth-First Search, a method that explores every possible path in a structure like a maze or a file system by going as deep as possible before backing up. It also underlies Stack Memory Behaviour, which explains how computers track these nested, self-calling steps by stacking them in memory.


## The mathematics

This concept rests on a branch of mathematics called discrete mathematics — the study of countable, separate things like whole numbers, as opposed to continuous things like distances. Recursion is a discrete idea: you are counting steps, not measuring a smooth slope. The specific operation you need is simple arithmetic — addition, subtraction, and multiplication — and the idea of a pattern that repeats with smaller numbers. There is no calculus here, no algebra beyond shorthand.

Let me teach you the two pieces plainly.

The first piece is the base case. This is a stopping rule. It tells you what to do when the input is as small as it can possibly be. For example, 'the number of people ahead of the first person in a queue is zero.' You do not need to look at anyone else to know this answer.

The second piece is the recurrence. This is a rule that says: for any larger input, the answer is built from the answer to a smaller input. For example, 'the number of people ahead of person number n is one more than the number ahead of person number n minus one.'

Here is what that sentence means in plain words:
1. Take your current person, let us call them person n.
2. Look at the person immediately behind them in the queue? No, look at the person immediately *ahead* of them in terms of index, which is person n minus one.
3. Find out how many people are ahead of that smaller person.
4. Add one to that number.

That second rule always refers to a smaller case — it never mentions the same size case, and it never mentions a larger one. That shrinking is what guarantees the chain eventually reaches a base case. If you keep subtracting one from your person number (n, n-1, n-2...), you will eventually hit 1. Once you hit 1, you stop using the recurrence rule and use the base case rule instead.

Together, the base case and the recurrence define the answer for every possible input. The base case alone covers only the smallest inputs; the recurrence alone never stops. Only both together give a complete definition.

We can write this down using letters to stand for numbers. Let f(n) be read as 'f of n'. This means: 'the answer for input n.'

Then a recursion is defined by two lines:

Line 1 (The Base Case): f(1) = 0.
This says: when the input is 1, the answer is 0.

Line 2 (The Recurrence): f(n) = f(n - 1) + 1 for all n greater than 1.
This says: when the input is any number bigger than 1, take the answer for the number one smaller than it (which is n minus 1), and add 1 to it.

Notice that Line 2 refers back to f. This is allowed because we already defined what f means in Line 1. We are not creating a circle; we are creating a ladder. You climb down the ladder using Line 2 until you hit the ground (Line 1), then you climb back up.


## A worked example

We want to compute the number of people ahead of person number 4 in a queue, where person 1 is at the front.

The base case says: person 1 has 0 people ahead.
The recurrence says: person n has 1 person ahead more than person n - 1.

Here is the step-by-step calculation. We start with the number we want (4) and work our way down to the base case (1).

Step 1: Start with person 4.
We need to find f(4). The recurrence rule says f(4) equals f(4 - 1) plus 1.
So, f(4) = f(3) + 1.
We do not know f(3) yet, so we pause here and go find it.

Step 2: Find f(3).
We need to find f(3). The recurrence rule says f(3) equals f(3 - 1) plus 1.
So, f(3) = f(2) + 1.
We do not know f(2) yet, so we pause here and go find it.

Step 3: Find f(2).
We need to find f(2). The recurrence rule says f(2) equals f(2 - 1) plus 1.
So, f(2) = f(1) + 1.
We do not know f(1) yet, so we pause here and go find it.

Step 4: Find f(1).
We need to find f(1). The input is now 1. This matches our base case rule.
The base case says: f(1) = 0.
Now we have a real number. We can start climbing back up the ladder.

Step 5: Go back to Step 3.
We found that f(2) = f(1) + 1.
We now know f(1) is 0.
So, f(2) = 0 + 1.
f(2) = 1.

Step 6: Go back to Step 2.
We found that f(3) = f(2) + 1.
We now know f(2) is 1.
So, f(3) = 1 + 1.
f(3) = 2.

Step 7: Go back to Step 1.
We found that f(4) = f(3) + 1.
We now know f(3) is 2.
So, f(4) = 2 + 1.
f(4) = 3.

Result: people_ahead(4) = 3. The chain of questions descended from 4 down to 1, hit the base case, and then added one on the way back up.


## From scratch, in Python

```python
# Let's write the queue example as Python code.
# First, a building block: a function.
# A function is a named block of code you can call with an input.
# It looks like: def name(input): ... return output

def people_ahead(n):
    # Base case: the front person has 0 people ahead.
    if n == 1:
        return 0
    # Recurrence: one more than the person in front.
    else:
        return people_ahead(n - 1) + 1

# Let's test it.
print(people_ahead(4))  # Output: 3
print(people_ahead(1))  # Output: 0
print(people_ahead(10)) # Output: 9
```


## What the code does

The code defines a function called people_ahead that takes a single input n. The first line inside the function checks if n is 1 — that is the base case. If true, it returns 0 immediately, without any further calls. If n is not 1, the function does the else part — the recurrence. It calls itself with n - 1 (a smaller number) and adds 1 to whatever that call returns. So when we call people_ahead(4), Python computes people_ahead(3) + 1. To compute people_ahead(3), it computes people_ahead(2) + 1. To compute people_ahead(2), it computes people_ahead(1) + 1. people_ahead(1) hits the base case and returns 0. Then the +1s cascade back up: people_ahead(2) gets 0 + 1 = 1, people_ahead(3) gets 1 + 1 = 2, people_ahead(4) gets 2 + 1 = 3. If we had forgotten the base case — if the function had no 'if n == 1' — then people_ahead(1) would call people_ahead(0), which would call people_ahead(-1), and so on forever, never stopping, until Python runs out of memory and crashes with a 'RecursionError'. That is the infinite recursion problem. If we had written the base case as 'if n == 1: return 1' instead of 0, then people_ahead(4) would return 4 instead of 3 — a subtly wrong answer. This code needs nothing beyond a function and an if-else statement — no lists, no loops, no dictionaries. The recursion itself is the loop.


## Common misconceptions

**A recursion without a base case might still work if the input is small.** — If I only call my function with small numbers, maybe it will stop on its own.

The function always checks the base case first. If the base case is absent or unreachable, the function calls itself with a smaller input every time, and no matter how small the input gets, it never stops — it just keeps going to smaller and smaller (or more negative) inputs until the stack overflows. The base case is not an optimisation; it is the only thing that stops the chain. In fact: The base case is mandatory and must be reachable for every possible input. For a case like n == 1, the function returns without recursing. For any other input, the recurrence eventually reaches a base case because it strictly shrinks the input.

**The recurrence and base case are the same thing.** — The base case is just the first step of the recurrence — they are basically the same rule.

The base case gives an answer directly for the smallest input, with no reference to any other case. The recurrence always refers to a smaller case. They are structurally different: one is a constant, the other is a relationship. A recurrence alone cannot start, and a base case alone cannot handle larger inputs. In fact: The base case is an anchor — a fixed answer for the smallest input. The recurrence is a bridge — a rule that connects every larger input to a smaller one. Both together cover all cases.

**One base case is always enough.** — As long as I have one base case, my recursion is correct.

A single base case such as f(0) = 1 does not cover f(1) if the recurrence is f(n) = f(n - 2) + 1. For an odd input, the chain skips past 0 and never hits it, descending into negative numbers forever. Some recursions genuinely need multiple base cases because the recurrence reduces by more than one at a time, or because different small inputs have different direct answers. In fact: You need enough base cases so that every possible input eventually reaches one. If the recurrence subtracts 2, you need base cases for both even and odd smallest inputs. If the recurrence has several forms, each may need its own base case.

**A wrong base case only causes a crash, not a wrong answer.** — If my base case is off by one, the program will probably crash, so I will notice it.

If the base case returns 1 instead of 0, the recursion still terminates — it just returns a wrong answer for every input. For a queue of 4 people, it returns 4 instead of 3. The program runs fine, produces plausible-looking output, and the bug is invisible unless you test with known answers. In fact: A wrong base case produces silently wrong results, not a crash. Always test the base case directly and check the output for a few small inputs against hand-computed values.

**The recurrence can refer to any smaller case and still be correct.** — As long as I shrink the input, the recurrence will give the right answer.

The recurrence must reflect the actual relationship between the problem and its subproblem. Subtracting 2 when the real relationship subtracts 1 gives wrong answers even though the recursion terminates. The shrinking is necessary but not sufficient — the rule itself must be true. In fact: The recurrence must correctly express how a problem relates to its smaller instances. Check it by hand on two or three small inputs before trusting it.


## In short

A recursion has two mandatory parts: a base case that gives the answer directly for the smallest input, and a recurrence that expresses every larger input in terms of strictly smaller ones. Missing or wrong base cases produce infinite recursion or silently wrong answers. Multiple base cases are common. The recurrence is also what you analyse to determine how many steps the algorithm takes — its complexity. Test both parts with hand-computed small inputs before trusting the code.


## Where this is used

Base cases and recurrence relations are everywhere in AI, often hidden inside libraries you will never write yourself but will rely on. **Large language models (LLMs) like ChatGPT.** When an LLM generates text, it produces one word (token) at a time, and each next word depends on all the words before it — a recursive process where the 'current state' is the entire sequence so far. The recurrence is the attention mechanism computing the next token from the previous tokens. The base case is the initial prompt — the starting sequence with no prior tokens. Training an LLM also uses recursion: backpropagation computes gradients by applying the chain rule recursively from the output layer back to the input layer. The base case is the output layer's error; the recurrence relates each layer's error to the layer after it. **Small models on phones or laptops.** When a model must run on limited hardware, developers often use recursion to traverse the model's structure efficiently — for example, a recursive function that walks a decision tree or a deep network's layers. The base case stops at the leaf or the final layer; the recurrence passes the output of one layer into the next. A wrong base case here means the model doesn't finish — it crashes the app. **Retrieval-augmented generation (RAG).** RAG systems search a document store for relevant chunks to feed the LLM. The search itself often uses a tree structure (like a k-d tree or an ANN index) where finding a match is recursive: start at the root (a base case if the tree is empty), and recurse into the child that is closer to the query. The base case is reaching a leaf node; the recurrence is the decision to go left or right. **Agentic systems that plan and call tools.** Agents that break a task into subtasks use recursion to explore possible action sequences. Each call to a tool produces a new state, and the agent recursively decides the next action. The base case is reaching a goal state or exhausting the budget; the recurrence is the rule 'choose an action, then continue from the new state.' Depth-First Search with Backtracking — your neighbouring topic — is exactly this pattern, and it appears in constraint solvers, puzzle solvers, and planning algorithms. **Everyday applied machine learning.** Decision trees — used for credit scoring, fraud detection, and medical diagnosis — are built recursively: pick a feature, split the data, and recurse on each subset. The base case is when a subset is pure (all same class) or too small to split further; the recurrence is the rule that selects the best feature to split on. A missing base case means the tree grows until it memorises every training example — overfitting — and a wrong base case (e.g., stopping too early) means it underfits. **What a developer actually writes.** In Python, a developer building a decision tree writes a function like build_tree(data) that checks 'if len(data) < 5 or all same label: return a leaf' (base case) and otherwise 'split data, then call build_tree on each half' (recurrence). In PyTorch, backpropagation is called with loss.backward(), and the framework recursively walks the computational graph — the base case is the input tensors, and the recurrence is the chain rule applied at each operation. When done badly — a wrong base case in a tree builder — the model silently underperforms; when done badly in a recursive search, the program crashes outright.


---

Read this on the web: https://basavapurushottam.com/learn-ai/base-cases-and-recurrence
