Recursion & Tracing

A recursive function solves a problem by calling itself on a smaller version of the same problem — and stops when the input is small enough to answer directly. That stopping point is the base case. 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 — parsing nested JSON, traversing a file system, or scoring a decision tree all lean on exactly this.

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: draw the calls as a tree, push down to the base cases, then combine the returns as they bubble up. Step through this stack growing one frame per call and shrinking one frame per return:

The single most important habit: the result is built as the calls UNWIND. Nothing is “added up” on the way down — each call just spawns smaller calls. The combining (n * ..., or summing children) happens on the way back, when each call 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.

Trace it: 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, and asked 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: identify the base case, then hand-expand the calls and combine returns as they unwind. For a counting question, count one call per node/element the recursion touches.

Quick check