Recursion: Functions That Call Themselves

Picture a Saturday evening at a crowded PVR ticket counter. You've just joined the queue and you want to know exactly how many people are ahead of you — but the queue snakes around a pillar and you genuinely cannot see past the person standing right in front of you. You can't count them all at a glance. What can you do?

You could ask the person directly in front of you, "how many people are ahead of you?" They can't see past the person in front of them either, so they turn around and ask the exact same question to the person ahead of them. That person asks the next, and so on, all the way to the front of the queue. Eventually someone reaches the very first person, who has nobody ahead — they immediately answer "zero." That answer travels backward: the second person hears "zero," adds one for the first person, and reports "one." The third person hears "one," adds one, reports "two." The answers ripple back down the queue, each person adding exactly one, until it reaches you.

You just solved a problem by breaking it into a smaller copy of the exact same problem, asked one person closer to the answer, and combined that smaller answer with your own contribution. That is recursion: a technique where a function solves a problem by calling itself on a smaller version of the same problem, until the problem becomes so small that the answer is obvious — and then the answers combine on the way back out.

From the queue to code

Let's turn the queue idea into a real Python function. Say each person's position in the queue is numbered starting from 0 at the front. Position 0 has nobody ahead. Position n has exactly one more person ahead than position n - 1.

def people_ahead(position):
    if position == 0:          # base case: nobody ahead of the front person
        return 0
    return 1 + people_ahead(position - 1)   # recursive case

print(people_ahead(3))   # asks position 2, who asks position 1, who asks position 0

Every recursive function needs exactly these two ingredients:

• Base case — the smallest version of the problem, answered directly without calling the function again. Here, position == 0, answer is 0. Without a base case the function would call itself forever.
• Recursive case — the function calls itself on a smaller version of the problem (position - 1, which is strictly closer to the base case), then uses that result to build its own answer (1 + ...).

Trace people_ahead(3) exactly the way the queue conversation happened:

• people_ahead(3) can't answer yet — it calls people_ahead(2) and waits.
• people_ahead(2) can't answer yet — it calls people_ahead(1) and waits.
• people_ahead(1) can't answer yet — it calls people_ahead(0) and waits.
• people_ahead(0) hits the base case and returns 0 immediately — no further calls.
• people_ahead(1) receives 0, computes 1 + 0 = 1, returns 1.
• people_ahead(2) receives 1, computes 1 + 1 = 2, returns 2.
• people_ahead(3) receives 2, computes 1 + 2 = 3, returns 3.

Notice the two distinct phases: a calling phase that dives deeper and deeper (3 → 2 → 1 → 0), and a returning phase that climbs back out, doing real work at every step (0 → 1 → 2 → 3). Every recursive function you'll ever write has this same two-phase shape. Keep this queue picture in your head — it's the template for everything that follows.

Factorial: the classic worked example

In mathematics, n! (read "n factorial") means multiply all the whole numbers from n down to 1. So 4! = 4 × 3 × 2 × 1 = 24. Notice something: 4! = 4 × (3 × 2 × 1) = 4 × 3!. Factorial is defined in terms of a smaller factorial — it's naturally recursive, exactly like the queue.

Formally: 0! = 1 (base case, by mathematical convention), and for n > 0, n! = n × (n-1)! (recursive case). Here's the Python:

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

print(factorial(4))   # 24

Compare this with the loop-based version you may already know:

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

print(factorial_iterative(4))   # 24

Both produce identical output, but they think about the problem differently. The iterative version builds the answer forward, multiplying as it goes, keeping one running total. The recursive version defers all multiplication until the base case is reached, then multiplies while returning. That deferral is exactly what the diagram below makes visible.

Common misconception: "the base case jumps straight back to the top"

Look carefully at the diagram again. A very common mistake is to imagine that once factorial(0) returns 1, that value shoots directly back up to factorial(4), which then instantly computes 24. That is not what happens, and it matters that you understand why.

Each waiting call is frozen, holding on to its own copy of n, and it can only do one thing next: multiply n by whatever value it eventually receives, then return that product to whoever called it — never to the very top directly. So the value 1 from factorial(0) goes only to factorial(1), which computes 1 × 1 = 1 and returns only to factorial(2), which computes 2 × 1 = 2 and returns only to factorial(3), which computes 3 × 2 = 6 and returns only to factorial(4), which finally computes 4 × 6 = 24. Four separate multiplications happen, one per frozen call, each waking up in turn. This "unwind one layer at a time" behaviour is managed automatically by something called the call stack — every time a function calls another, Python pushes a new frame on top of the stack holding that call's local variables; when a call finishes, its frame is popped off and control returns to exactly the frame just below it, never further.

Fibonacci: when recursion repeats work

The Fibonacci sequence is defined recursively too: fib(0) = 0, fib(1) = 1, and for n ≥ 2, fib(n) = fib(n-1) + fib(n-2). Each term is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21, ... The direct translation into Python is almost embarrassingly short:

def fibonacci(n):
    if n == 0 or n == 1:      # base cases
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)   # recursive case

print(fibonacci(6))   # 8

Unlike factorial, which makes exactly one recursive call per level, fibonacci makes two — and those two calls each branch into two more. The diagram below draws out every single call triggered by fibonacci(4).

Count the calls yourself using the tree. Every leaf (green) is a base case that answers immediately without branching further; every non-leaf (indigo/amber/orange) waits for both of its children before it can add them together and return. Count the nodes hanging below fib(3), including fib(3) itself: there are 5 of them (fib(3), fib(2), fib(1), fib(1), fib(0)) — so answering fib(3) alone takes 5 calls. Count the nodes below either orange fib(2), including itself: there are 3 (fib(2), fib(1), fib(0)) — so answering fib(2) alone takes 3 calls. Add up the whole tree — 1 root, 1 amber, 2 orange, 3 green fib(1)s, 2 green fib(0)s — and you get 9 calls total just to compute fib(4).

Here is the problem: notice that both orange fib(2) nodes are solving the identical question, fib(2), completely independently, from scratch, with zero memory of each other. Nobody remembered the first answer and reused it. This wastefulness compounds ferociously as n grows, because every level roughly doubles the number of calls needed below it. Computing fibonacci(30) this way triggers over two and a half million function calls in total, just to produce one number — even though the actual mathematical answer, 832,040, could be reached by a simple loop in 30 steps. This is a genuine limitation of naive recursion: elegant code is not automatically efficient code. (Programmers fix this specific problem with a technique called memoization — caching each answer the first time it's computed so repeated subtrees like the two fib(2) calls above are never recomputed — but that is a topic for when you study dynamic programming later.)

Recursion on strings: checking palindromes

A palindrome is a word or phrase that reads identically forwards and backwards. The classic English example is MADAM — a courtesy title historically shortened from the French "ma dame," which happens to also be a palindrome. An equally famous example from an Indian language is even more striking: the word MALAYALAM itself — the name of the Dravidian language spoken widely in Kerala — reads exactly the same forwards and backwards, letter for letter: M-A-L-A-Y-A-L-A-M.

Checking whether a word is a palindrome is naturally recursive: a string is a palindrome if its first and last letters match and the string with those two letters stripped away is also a palindrome. The base case is a string of length 0 or 1, which is trivially a palindrome (nothing to mismatch).

def is_palindrome(word):
    if len(word) <= 1:                     # base case
        return True
    if word[0] != word[-1]:                # letters don't match — fail fast
        return False
    return is_palindrome(word[1:-1])       # recursive case: strip both ends

print(is_palindrome("MALAYALAM"))   # True
print(is_palindrome("DELHI"))       # False

Trace is_palindrome("MALAYALAM"): first letter M matches last letter M, strip both ends, leaving "ALAYALA". First A matches last A, strip, leaving "LAYAL". First L matches last L, strip, leaving "AYA". First A matches last A, strip, leaving "Y". Length 1 — base case — return True. That True now travels back up through every waiting call, unchanged, because none of them found a mismatch. Final answer: True.

Now trace is_palindrome("DELHI"): first letter D, last letter I — they don't match, so the function returns False immediately, on the very first call, without ever calling itself again. Recursion doesn't force you to go all the way to the base case; a recursive case can also terminate the recursion early the moment it detects failure.

Recursion on sorted data: binary search

Binary search finds a target value inside a sorted list far faster than checking every element one by one. The idea: look at the middle element. If it's the target, you're done. If the target is smaller, the answer (if it exists) must be in the left half, so search only that half. If larger, search only the right half. Each step throws away half the remaining list — and "search a smaller version of the same list" is, again, naturally recursive.

def binary_search(arr, target, low, high):
    if low > high:                          # base case: nothing left to search
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, high)   # search right half
    else:
        return binary_search(arr, target, low, mid - 1)    # search left half

irctc_pnr_slots = [101, 105, 110, 118, 125, 130, 142]
print(binary_search(irctc_pnr_slots, 142, 0, 6))   # 6
print(binary_search(irctc_pnr_slots, 105, 0, 6))   # 1

Trace the search for 142 in [101, 105, 110, 118, 125, 130, 142] (indices 0 to 6): mid = (0+6)//2 = 3, arr[3] = 118, and 118 < 142, so search the right half: low = 4, high = 6. Now mid = (4+6)//2 = 5, arr[5] = 130, and 130 < 142, so search right again: low = 6, high = 6. Now mid = 6, arr[6] = 142 — match. Return index 6. Only three comparisons were needed to search seven elements.

Trace the search for 105: mid = 3, arr[3] = 118, and 118 > 105, so search the left half: low = 0, high = 2. Now mid = (0+2)//2 = 1, arr[1] = 105 — match. Return index 1. Just two comparisons this time. This halving is precisely why binary search examines roughly log₂(n) elements instead of all n — searching a sorted list of a million values takes about 20 comparisons, not a million.

When recursion runs out of room

Every recursive call adds a new frame to the call stack, and computer memory for the stack is finite. Python, by default, refuses to let a chain of calls go deeper than 1000 levels — if you exceed that, it raises a RecursionError rather than crashing your computer's memory. Try running people_ahead(2000) from the very first example and Python will stop you with exactly this error, because the calling phase would need 2000 frames stacked before the base case is even reached. This is a genuine, practical constraint: recursion is a natural way to think about self-similar problems, but for very deep or very large inputs, an iterative version (like factorial_iterative above, which uses a single loop variable and no growing stack) is often the safer and more memory-efficient choice. Choosing between recursion and iteration is a real engineering decision, not just a stylistic one — recursion tends to win for problems with a naturally branching or nested structure (like the folders-inside-folders on your computer, or search trees), while iteration tends to win for simple linear repetition over huge inputs.

Practice: test yourself before moving on

1. Write out the full calling-and-returning trace for factorial(3), the way this chapter traced factorial(4). What value does each frozen call multiply by, and in what order do the multiplications actually happen?
2. Using only the fibonacci call-tree diagram (not new computation), how many total calls does answering fib(3) alone require? How many for fib(2) alone?
3. Is is_palindrome("MALAYALAM") still correctly identified as a palindrome if you compare it letter-by-letter with a loop instead of recursion? Would the loop version and the recursive version ever disagree on any input? Why or why not?
4. In binary_search, what is the base case, and what does returning -1 from it actually mean about the search?
5. A student claims: "when factorial(0) returns 1, that 1 is sent straight to factorial(4), which multiplies it by 4 to get the final answer." Explain precisely why this claim is wrong, using the idea of the call stack.

Answer key:

1. factorial(3) calls factorial(2) calls factorial(1) calls factorial(0), which returns 1 (base case). Then factorial(1) computes 1 × 1 = 1, factorial(2) computes 2 × 1 = 2, and factorial(3) computes 3 × 2 = 6. The multiplications happen from the innermost call outward, one layer at a time, never skipping a layer.
2. Counting the nodes in the diagram: the subtree rooted at fib(3) contains 5 nodes total (fib(3), fib(2), fib(1), fib(1), fib(0)), so fib(3) alone costs 5 calls. Either orange fib(2) subtree contains 3 nodes (itself plus fib(1) and fib(0)), so fib(2) alone costs 3 calls.
3. Yes, both versions must agree on every input — they are checking exactly the same mathematical condition (do the outer letters match, all the way inward), just using different control-flow mechanisms to check it. Recursion and iteration are two different ways of expressing the same repeated logic; when both are implemented correctly, they always produce the same answer.
4. The base case is low > high, meaning the search range has become empty — there is nowhere left to look. Returning -1 means the target is definitely not present anywhere in the original list.
5. It's wrong because each call can only return its value to the one call that directly invoked it — the call stack only lets a frame hand its result to the frame immediately below it, never further. So factorial(0)'s 1 only reaches factorial(1); it takes three more separate returns (through factorial(1), factorial(2), and factorial(3)) before a value ever reaches factorial(4), and by then it has already been multiplied three times.

Summary

Recursion solves a problem by having a function call itself on a strictly smaller version of the same problem, until a base case is reached that can be answered directly — then the answers combine on the way back out, one waiting call at a time, never skipping a layer. Every recursive function needs a base case (or it never terminates) and a recursive case that measurably shrinks the problem (or it never reaches the base case). The call stack is the mechanism that remembers every waiting call and resumes them in the correct order. Recursion shines on self-similar structures — factorials, tree-shaped branching like Fibonacci, strings being checked from both ends inward, and sorted lists being halved — but it isn't free: naive recursive Fibonacci recomputes identical subtrees millions of times over, and every recursive chain is bounded by how much call-stack depth is available before a RecursionError stops you. Knowing when a problem's structure genuinely calls for recursion, and when a plain loop is the better tool, is the real skill this chapter has been building toward.