Recursion

Stand in the queue outside your school canteen during recess. You can't see the front of the line from where you're standing, so you don't know your own position. But there's a trick: ask the student directly in front of you what their position is. They don't know either — so they ask the student in front of them. This chain of asking continues until it reaches the very first student, who doesn't need to ask anyone, because they can see for themselves that they are at position 1. That answer — "1" — now travels back down the line: the second student hears "1" and replies "then I'm 2," the third hears "2" and replies "3," and so on, until the answer reaches you.

Notice what just happened. Nobody in that queue solved the whole problem by themselves. Each student solved a tiny piece of it — "what's my position, given the position of the person in front of me?" — and relied on someone else to solve a slightly smaller version of the exact same problem. This is the core idea behind recursion: solving a problem by breaking it into a smaller copy of itself, until the copies get so small that the answer is obvious.

From a queue to a function

We can write the queue trick as a function. Suppose position(student) tells us where a student stands in the line.

def position(student):
    if student.is_at_front():          # base case
        return 1
    else:                                # recursive case
        return 1 + position(student.person_in_front())

Two things make this a recursive function. First, it calls itself — the line position(student.person_in_front()) is a call to the very function we are defining. Second, it has an escape route: the if student.is_at_front() check. Without that check, the chain of asking would never stop — imagine a queue with no first person, where everyone keeps asking the person ahead forever.

Every correct recursive function needs exactly these two parts:

• Base case — the smallest version of the problem, simple enough to answer directly without calling the function again. In the queue, this is "I am at the front, so I am position 1."
• Recursive case — the function calls itself on a smaller version of the same problem, then uses that result to build its own answer. In the queue, this is "ask the person ahead, then add 1."

The word "smaller" is doing important work here. Each recursive call must move closer to the base case — in the queue, each call moves one step closer to the front. If a recursive call ever called itself on the exact same input, or on a larger input, it would never reach the base case, and the calls would continue until the program crashes.

Worked example: factorial, step by step

Recursion becomes concrete once you trace a real numeric example by hand. The factorial of a number n, written n!, is the product of all whole numbers from n down to 1. For example, 4! = 4 × 3 × 2 × 1 = 24. You may already know how to compute this with a loop:

def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result = result * i
    return result

Now notice something about 4!: it equals 4 × 3!, since 4 × (3 × 2 × 1) = 4 × 3!. And 3! equals 3 × 2!. This pattern continues down to 1! = 1 × 0!, and by mathematical convention, 0! = 1 (there is nothing to multiply, so the product is defined as 1). This gives us a base case for free. Here is factorial written recursively:

def factorial(n):
    if n == 0:                       # base case
        return 1
    else:
        return n * factorial(n - 1)  # recursive case

Let's trace factorial(4) exactly as Python would execute it, one call at a time.

factorial(4) calls factorial(3), because n is not 0
  factorial(3) calls factorial(2), because n is not 0
    factorial(2) calls factorial(1), because n is not 0
      factorial(1) calls factorial(0), because n is not 0
        factorial(0) hits the base case -> returns 1
      factorial(1) computes 1 * 1 -> returns 1
    factorial(2) computes 2 * 1 -> returns 2
  factorial(3) computes 3 * 2 -> returns 6
factorial(4) computes 4 * 6 -> returns 24

The final answer is 24, which matches 4 × 3 × 2 × 1. Notice the two-phase shape of this trace: an outward phase where calls pile up, each one waiting on the next, and a return phase where answers flow back, each waiting call finally getting the value it needed to finish its own multiplication. This waiting is not free — Python has to remember all four unfinished factorial calls at once, each with its own value of n, until they can be completed in reverse order. This bookkeeping structure is called the call stack, and it behaves exactly like a stack of trays in the canteen: the last call pushed on is the first one to be popped off and finished.

The misconception that trips up most beginners

Looking at the code for factorial, it's tempting to think that all five calls — for n = 4, 3, 2, 1, 0 — are sharing one single variable called n, the way a global variable would be shared. This is wrong, and it is the single biggest source of recursion bugs. Each call to a function gets its own private copy of every local variable, including its parameters. When factorial(4) calls factorial(3), Python doesn't overwrite the n = 4 that belongs to the first call — it creates a brand new, separate n = 3 that belongs only to the second call, and pauses the first call's frame exactly as it was, waiting. That's why the diagram above shows five separate boxes rather than one box being edited five times: there really are five independent frames alive on the stack at the moment factorial(0) is reached, each one silently holding onto its own value of n and patiently waiting for a multiplication it can't yet finish.

You can verify this for yourself by imagining what would go wrong if variables were shared. If there were only one shared n, then by the time factorial(0) finished, every waiting call would try to compute using n = 0, and the answer would come out as 0 × 1 at every level — clearly not 24. The fact that the real answer is correct is proof that each call's variables are kept separate.

Worked example: powers, and where the pattern generalises

The same shape — reduce, recurse, combine — solves many problems, not just factorial. Consider computing baseᵉˣᵖ, the kind of repeated multiplication your Class 8 mathematics chapter on compound interest depends on (the formula A = P(1 + r)ⁿ needs exactly this operation). 3⁴ means 3 × 3 × 3 × 3, and just like before, we can peel off one multiplication at a time: 3⁴ = 3 × 3³, and 3³ = 3 × 3², down to 3⁰ = 1 by definition.

def power(base, exp):
    if exp == 0:                  # base case
        return 1
    else:
        return base * power(base, exp - 1)   # recursive case

Tracing power(3, 4):

power(3, 4) = 3 * power(3, 3)
power(3, 3) = 3 * power(3, 2)
power(3, 2) = 3 * power(3, 1)
power(3, 1) = 3 * power(3, 0)
power(3, 0) = 1                    (base case)

Unwinding:
power(3, 1) = 3 * 1  = 3
power(3, 2) = 3 * 3  = 9
power(3, 3) = 3 * 9  = 27
power(3, 4) = 3 * 27 = 81

3⁴ = 81, which you can double check directly: 3 × 3 = 9, 9 × 3 = 27, 27 × 3 = 81. The structure is identical to factorial: shrink the exponent by 1 on every call, and stop when it reaches 0. What changes between problems is only what counts as "smaller" and what the base case returns — the skeleton of base case plus recursive case stays the same.

Why bother — where recursion earns its place

A fair question at this point is: since factorial_iterative above used a simple loop and got the same answer, why learn recursion at all? For factorial and power, a loop is arguably simpler and slightly more memory-efficient, since it doesn't need to keep several waiting calls on a stack. Recursion earns its keep on problems where the data itself is built from smaller copies of itself — what computer scientists call self-similar structure.

Think about the folders on your phone's File Manager app. Your WhatsApp/Media folder contains sub-folders like WhatsApp Images and WhatsApp Video, and some of those may contain their own sub-folders for different chats, which may contain further sub-folders. If you wanted to count every photo stored anywhere inside WhatsApp/Media, a fixed number of nested loops won't work, because you don't know in advance how many folder-levels deep the nesting goes — it could be 2 levels for one user and 6 for another. Recursion handles this naturally, because "count files in this folder" reduces cleanly to "count the files directly here, plus, for every sub-folder, count files in that sub-folder" — the same operation, applied to something smaller, with a base case being an empty folder or a folder containing no further sub-folders.

def count_files(folder):
    total = 0
    for item in folder.contents():
        if item.is_file():
            total = total + 1
        else:                              # item is a sub-folder
            total = total + count_files(item)   # recursive case
    return total

Here the base case isn't a single explicit if line — it's the loop simply finding no sub-folders to recurse into, so the function returns total without making any further recursive call. This pattern — recursion over something that can contain smaller versions of itself — is exactly how a family tree, a set of nested comments on a forum thread, or the folder structure on a computer are naturally processed, and writing them with plain loops alone is far more awkward than writing them recursively.

The danger: missing or wrong base cases

Every recursive function is only as safe as its base case. If you wrote factorial without checking for n == 0, or if you mistakenly called factorial(n) again instead of factorial(n - 1) inside the recursive case, the function would keep calling itself without ever getting closer to a stopping point. In Python, this doesn't loop forever the way a broken while loop might — Python keeps a limited amount of space for the call stack (by default, around 1000 nested calls), and once that space runs out, it stops the program with a RecursionError: maximum recursion depth exceeded. This is a useful safety net compared to some other languages, but it still means a bug — it means your base case is missing, unreachable, or that your recursive call isn't shrinking the problem.

A second, subtler danger is a base case that is technically present but wrong. If factorial's base case had been written as if n == 1: return 1 instead of if n == 0, then calling factorial(4) would still work correctly by coincidence — but calling factorial(0) directly would recurse into negative numbers forever, since n would go 0, -1, -2, -3, ... and never hit n == 1. Always check that your base case is reachable from every valid starting input, not just the one example you happened to test.

Choosing between recursion and a loop

Neither approach is universally "better" — they are tools suited to different shapes of problem. Prefer a loop when the problem is a straightforward repetition over a known, flat sequence of steps, such as summing a fixed list of exam marks — a loop does this with less memory overhead, since it doesn't need to keep multiple waiting calls alive. Prefer recursion when the problem is naturally defined in terms of a smaller version of itself, especially when the "smaller version" isn't a simple flat sequence — nested folders, family trees, and (as you'll meet in later chapters) breaking a large search space in half repeatedly are all far more natural to express recursively than iteratively.

In CBSE Computer Science and Informatics Practices, recursion typically appears as an extension of the Functions unit, and board-style questions usually ask you to trace a short recursive function by hand and state its final output — exactly the skill you practised above with factorial(4) and power(3, 4). The same trace-by-hand skill is also a staple of early competitive programming and school-level coding olympiads, which frequently give a short recursive function and ask "what does this print?" as a way of testing whether you actually understand the call stack, rather than whether you've memorised a formula.

Check your understanding

Work through these without running code — trace them by hand the way we traced factorial(4), writing out each call and then each return, before checking your answer.

1. Trace factorial(3) completely, showing every call going out and every return coming back. What is the final value?
2. Trace power(2, 5) the same way. What is the final value, and does it match 2 × 2 × 2 × 2 × 2 computed directly?
3. A classmate writes this function to sum the whole numbers from 1 to n: def sum_to(n): return n + sum_to(n - 1). It has no base case. What will happen if you call sum_to(5), and what single line would you add to fix it, matching what you know 1 + 2 + 3 + 4 + 5 should equal?
4. In the call-stack diagram for factorial(4), explain in your own words why factorial(2)'s copy of n is not overwritten when factorial(1) and factorial(0) are called. Refer to what a "stack frame" holds.
5. Would you use recursion or a loop to add up the runs scored by each player in an 11-player cricket team's batting order? Would you use recursion or a loop to count every file inside a folder that may contain further folders inside it? Justify both choices in one sentence each.

Answers to check yourself: (1) factorial(3) = 3 × 2 × 1 = 6. (2) power(2, 5) = 32, matching 2×2×2×2×2 = 32. (3) Without a base case, sum_to would call itself with n − 1 forever — 5, 4, 3, 2, 1, 0, -1, -2, ... — eventually raising a RecursionError; adding if n == 0: return 0 (checked before the recursive line) fixes it, and sum_to(5) would then correctly return 15. (4) Each call to factorial creates its own separate stack frame holding its own private n; factorial(2)'s frame is paused, not deleted or shared, so its n = 2 stays intact underneath the newer frames for factorial(1) and factorial(0) until it's their turn to return and factorial(2) resumes. (5) A loop suits the batting order because it's a fixed, flat list of 11 known items with no nested sub-structure; recursion suits the folder-counting problem because a folder can contain sub-folders of unknown and varying depth, which is exactly the self-similar shape recursion is built to handle.

Summary

Recursion solves a problem by expressing it in terms of a smaller instance of the same problem, exactly as each student in the canteen queue found their position by asking the person one step ahead. Every correct recursive function needs a base case that stops the chain of calls, and a recursive case that calls the function again on a strictly smaller input and combines that result into its own answer. Tracing factorial(4) showed the two-phase shape of every recursive call — calls piling up on the call stack until the base case is hit, then return values flowing back down, each waiting call finishing its own computation using the answer handed back to it. Crucially, each call keeps its own private copy of its variables rather than sharing one — that's what lets four different multiplications happen correctly instead of colliding into one. Recursion isn't a replacement for loops in general — for flat, fixed-size repetition a loop is usually simpler — but it is the natural tool for self-similar structures like nested folders, family trees, and other problems that contain smaller copies of themselves, and it's exactly this trace-by-hand skill that CBSE board questions and early competitive coding rounds test most often.