Recursion & Tracing

The last lesson ended with a riddle: a function is allowed to call itself, so what stops it from looping forever? The answer is a single, disciplined idea. A recursive function solves a problem by calling itself on a smaller version of the same problem, and it stops the moment the input is small enough to answer outright. That stopping point is the base case, and it is what keeps the tower of calls from growing without end.

GATE DA rarely asks you to invent recursion; it asks you to trace it — given the code and an input, what does it return, and how many calls does it make? The same tree-walking pattern is everywhere in real data work too: parsing nested JSON, walking a file system, and scoring a decision tree all lean on exactly this shape.

The two parts of every recursion

1. Base case — the input is small enough to answer with no further calls.
2. Recursive case — shrink the input toward the base case and call yourself.

The classic example is factorial:

def fact(n):
    if n <= 1:          # base case
        return 1
    return n * fact(n - 1)   # recursive case: n shrinks by 1

fact(4) calls fact(3), which calls fact(2), which calls fact(1). At n = 1 the base case fires and returns 1. Then the answers combine on the way back up as each call finishes: 1 → 2 → 6 → 24.

Trace by expanding the call tree

The reliable way to trace recursion is to draw the calls as a tree: push down to the base cases, then combine the returns as they bubble back up. Step through this stack — it grows one frame per call and shrinks one frame per return, which is recursion’s whole shape in motion:

The single most important habit: the result is built as the calls UNWIND. Nothing is “added up” on the way down — each call only spawns smaller calls. The combining (n * ..., or summing children) happens on the way back, when each call finally has its children’s answers in hand.

Recursion over a dict-encoded tree

GATE DA likes to encode a tree as a dictionary mapping each node to its list of children, then ask you to recurse over it. Here a node has no children when its list is empty — that empty list is the base case (the sum over no children is 0).

Each call returns 1 for itself plus the counts of all its children. The combining happens as the recursion unwinds — leaves return 1, internal nodes add their children’s totals.

tree = {0: [1, 2], 1: [3, 4], 2: [], 3: [], 4: []}

def count(t, node):
    return 1 + sum(count(t, c) for c in t[node])   # 1 (self) + children

print("count(tree, 0) =", count(tree, 0))

prints:

count(tree, 0) = 5

Trace it by hand: count(0) = 1 + count(1) + count(2). count(2) = 1 (empty children). count(1) = 1 + count(3) + count(4) = 1 + 1 + 1 = 3. So count(0) = 1 + 3 + 1 = 5. Notice each of the 5 nodes is visited exactly once, so the function also makes 5 calls — one per node.

How GATE asks this

A 2024 question gave exactly this style: a tree encoded as a dict of children and a near-identical count-style recursion, asking for the returned node count (its larger tree counted to 9). The same paper also showed a recursive in-place swap that reverses a list segment — swap a[i] with a[j], then recurse inward on (i+1, j-1) until the indices meet:

def rev(a, i, j):
    if i >= j:               # base case: pointers met or crossed
        return
    a[i], a[j] = a[j], a[i]  # swap the ends
    rev(a, i + 1, j - 1)     # recurse on the inner segment

a = [1, 2, 3, 4, 5]
rev(a, 0, 4)                 # a becomes [5, 4, 3, 2, 1]

The pattern is always the same: identify the base case, then hand-expand the calls and combine the returns as they unwind. And for a counting question, count one call per node or element the recursion touches.

A question to carry forward

Tracing recursion trained you to be the machine — to follow each call precisely, frame by frame, and never guess. But recursion is only one of the shapes GATE asks you to execute by hand. Just as often it hands you plain iterative pseudocode: loops, counters, swaps, written in a notation that is nobody’s real programming language. Here is the thread onward: how do you become an even more careful machine — tracking every variable through every loop iteration in that language-agnostic pseudocode, so you can predict the exact final output without ever running it?

In one breath

• A recursive function calls itself on a smaller input and stops at a base case — no base case (or one never reached) ⇒ infinite recursion (RecursionError).
• Trace by expanding the call tree down to base cases, then combining returns as the calls UNWIND — nothing is computed on the way down.
• fact(n) = n·fact(n−1), base fact(1)=1; 1→2→6→24 assembles on the way up.
• Dict-encoded tree: count(node) = 1 + sum(count(child)); empty children = base case. The 5-node tree returns 5 and makes 5 calls (one per node).
• Counting calls = counting nodes/elements the recursion touches. GATE DA 2024 tested this and a recursive in-place reversal.

Practice