Recursion — Call Stack Mechanics, Base Cases & Inductive Problem Solving

Layered Deep-Dive: This chapter reconstructs Recursion in Python from first principles. We explore the call stack frame lifecycle, the strict anatomy of base and recursive cases, how return values bubble up through activation records, why missing a return produces None, and the common recursive tracing traps featured in IIT Madras Quiz 3 and OPP examinations.

1. Orientation & Intuition: Structural Self-Similarity

• A folder on your computer contains files and other folders.
• A list is an element followed by another list.
• Factorial $n!$ is $n$ multiplied by $(n-1)!$.

              factorial(4)
               = 4 * factorial(3)
                       = 3 * factorial(2)
                               = 2 * factorial(1)
                                       = 1 (Base Case reached!)
                               <-- Unwinding begins

The Inductive Contract

1. Base Case: There must be at least one terminal condition that returns immediately without recursing.
2. Progress: Each recursive call must strictly advance the state toward the base case (e.g., $n \to n - 1$ or lst[1:]).
3. Combination: The return value from the sub-problem must be correctly combined to produce the solution to the original problem.

2. Terminology & Memory Model: The Call Stack

Stack Growth during factorial(3):
[Push] factorial(3) -> waits for factorial(2)
  [Push] factorial(2) -> waits for factorial(1)
    [Push] factorial(1) -> returns 1 immediately
  [Pop]  factorial(2) -> calculates 2 * 1 = 2, returns 2
[Pop]    factorial(3) -> calculates 3 * 2 = 6, returns 6

3. Core Recursion Archetypes

3.1 Linear Reduction: Counting and Summing

python
Run Inline
def sum_digits(n: int) -> int:
    """Computes the sum of digits of a non-negative integer n."""
    # Base case: single digit
    if n < 10:
        return n
    # Recursive step: last digit + sum of remaining digits
    return (n % 10) + sum_digits(n // 10)

# Trace: sum_digits(347)
# = 7 + sum_digits(34)
# = 7 + (4 + sum_digits(3))
# = 7 + (4 + 3) = 14

3.2 List Reduction

python
Run Inline
def recursive_reverse(lst: list) -> list:
    """Reverses a list recursively without mutating the original."""
    # Base case: empty list or single-element list
    if len(lst) <= 1:
        return lst
    # Recursive step: reverse tail, append head
    return recursive_reverse(lst[1:]) + [lst[0]]

3.3 Branching / Tree Recursion: Fibonacci

python
Run Inline
def fib(n: int) -> int:
    """Returns the nth Fibonacci number (0-indexed)."""
    # Two base cases
    if n == 0:
        return 0
    if n == 1:
        return 1
    # Two recursive calls create a binary execution tree
    return fib(n - 1) + fib(n - 2)

4. State Passing: Return Bubbling vs Accumulator Arguments

Pattern A: Return Value Bubbling (Functional)

python
Run Inline
def list_length(lst: list) -> int:
    if not lst:
        return 0
    return 1 + list_length(lst[1:])

Pattern B: Accumulator Passing (Tail-Recursive Form)

python
Run Inline
def list_length_acc(lst: list, current_len: int = 0) -> int:
    if not lst:
        return current_len
    return list_length_acc(lst[1:], current_len + 1)

5. Worked Exam Dissections

Dissection 1: Mystery Recursive Function Output

python
Run Inline
def mystery(a: int, b: int) -> int:
    if b == 0:
        return a
    return mystery(b, a % b)

1. Call 1: mystery(24, 18). $b = 18 \neq 0$. Next call: mystery(18, 24 % 18) $\implies$ mystery(18, 6).
2. Call 2: mystery(18, 6). $b = 6 \neq 0$. Next call: mystery(6, 18 % 6) $\implies$ mystery(6, 0).
3. Call 3: mystery(6, 0). $b = 0$. Base case triggers! Returns $a = 6$.
4. Call 2 receives 6 and returns 6.
5. Call 1 receives 6 and returns 6.

Dissection 2: The "Forgot the Return" Trap

python
Run Inline
def f(n):
    if n == 0:
        return 1
    f(n - 1) * n   # Notice: NO return keyword!

1. f(3) evaluates f(2) * 3.
2. To compute that, f(2) evaluates f(1) * 2.
3. To compute that, f(1) evaluates f(0) * 1.
4. f(0) hits the base case and returns 1.
5. Inside frame f(1), 1 * 1 = 1 is computed as an expression, but there is no return statement.
6. In Python, a function that finishes without an explicit return automatically returns None.
7. Back in frame f(2): receives None, then tries to execute None * 2 $\implies$ raises TypeError: unsupported operand type(s) for *: 'NoneType' and 'int'!

6. Common Pitfalls & Traps in IITM Python Exams

1. The Missing return Bug: In recursive steps, you must write return recursive_call(...). If you only write recursive_call(...), the frame discards the result and returns None.
2. Missing Base Case or Moving Away From Base Case: Writing countdown(n + 1) when base is $n = 0$ moves forever away from zero, terminating only when Python raises RecursionError: maximum recursion depth exceeded in comparison.
3. List Slicing Overhead: Passing lst[1:] creates a shallow copy of the remainder of the list on every frame, taking $O(n)$ time and memory per step. For large collections, pass an index pointer idx instead of slicing.
4. Default Mutable Arguments in Recursive Accumulators: Never write def collect(tree, acc=[]):. Because default lists are created once at definition time, repeated external calls to collect() will retain dirty elements from earlier executions. Use acc=None and initialize if acc is None: acc = [].

7. Practice & Quiz Questions

Question 1 (MCQ)

python
Run Inline
def q(n):
    if n <= 1:
        return 1
    if n % 2 == 0:
        return q(n // 2) + 1
    return q(n - 1) + 2

• (A) 3
• (B) 4
• (C) 5
• (D) 6

1. q(6): 6 is even $\implies$ return q(3) + 1
2. q(3): 3 is odd $\implies$ return q(2) + 2
3. q(2): 2 is even $\implies$ return q(1) + 1
4. q(1): hits base case $n \le 1 \implies$ returns 1
5. Unwinding:
   • q(2) = 1 + 1 = 2
   • q(3) = 2 + 2 = 4
   • q(6) = 4 + 1 = 5 Wait! Let's re-verify: q(1) = 1 q(2) = q(1) + 1 = 2 q(3) = q(2) + 2 = 4 q(6) = q(3) + 1 = 5 Correct Answer is (C) 5!

Question 2 (MSQ)

• (A) Finding the maximum element in a non-empty numeric list.
• (B) Reversing a string.
• (C) Generating all $2^n$ subsets (power set) of a set of size $n$.
• (D) Computing the greatest common divisor (GCD) of two integers.

• (A), (B), and (D) only require a single recursive subproblem invocation per step ($O(n)$ or $O(\log n)$ call depth).
• (C) Generating power sets requires binary branching at each element (include vs exclude), which is a multi-branching tree recursion.

8. Active Recall Flashcards

1. What exception is raised when Python exceeds its call stack frame ceiling? Answer: RecursionError: maximum recursion depth exceeded.
2. What does a Python recursive function return if the recursive call executes without the return statement? Answer: It returns None.
3. What are the two mandatory components of any well-formed recursive function? Answer: (1) At least one base case that stops recursion, and (2) a recursive step that moves arguments strictly toward that base case.
4. Why is lst[1:] inefficient in recursive list traversals? Answer: Each slice allocates a new list in memory, leading to an overall $O(n^2)$ time and space penalty.