Recursion & Problem Solving: Techniques, Traces & Pitfalls

TAKEAWAYS:

• Recursion replaces loops by breaking problems into smaller subproblems with a base case and recursive case, but risks stack overflow if not bounded.
• Tail recursion optimizes stack usage by placing the recursive call last, but compilers must support it (GCC’s -O2 flag helps).
• Divide-and-conquer (e.g., merge sort) and backtracking (e.g., N-queens) are classic recursive strategies.
• Always trace recursive calls step-by-step to spot infinite loops or incorrect base cases.
• Memoization caches results of expensive recursive calls (e.g., Fibonacci) to avoid redundant work.
• Real-world systems (WhatsApp’s message forwarding, Daraz’s order routing) use recursion implicitly in tree/graph traversals.

Core Concepts: How Recursion Works

1. Definition and Key Terms

Recursion is a technique where a function calls itself to solve smaller instances of the same problem. It consists of:

• Base case: The simplest, non-recursive solution (terminates recursion).
• Recursive case: The function calls itself with modified inputs, moving toward the base case.

flowchart TD
    A["Recursive Function\nf(n)"] -->|"Check if n == base case?"| B["Yes\nReturn base result"]
    A -->|"No<br/>Compute f(n-1) or f(n/2)"| C["Recursive Call\nf(n-1) or f(n/2)"]
    C --> A

Why use recursion?

• Elegant code for problems with self-similar subproblems (e.g., tree traversals, factorial).
• Matches mathematical definitions (e.g., Fibonacci: $F_n=F_{n-1}+F_{n-2}$).

2. Stack Frames and Memory

Each recursive call adds a stack frame (local variables + return address). If the base case is never reached, the stack overflows (crash!).

Example: Factorial Recursion

int fact(int n) {
    if (n == 0) return 1;       // Base case
    return n * fact(n - 1);     // Recursive case
}

Trace for fact(3):

Visual:

In the Real World

1. WhatsApp Message Forwarding

   • When you forward a message to 5 friends, each friend forwards it to 5 more, creating a recursive tree of messages.
   • Idea used: Recursive traversal of a contact tree (each node = a user, edges = forwarded messages).
   • Risk: Without limits, this could crash servers (like the "Elon Musk Bitcoin tweet" meme).

2. Daraz Order Processing

   • Orders are routed through a recursive hierarchy: Daraz → Warehouse → Delivery Partner → Customer.
   • Idea used: Recursive function calls to validate each step (e.g., checkInventory() calls checkDeliveryPartner()).

3. Ncell’s Network Routing

   • Cell towers use recursive algorithms to find the shortest path for calls (similar to Dijkstra’s algorithm, which is recursive).
   • Idea used: Recursive pathfinding in graphs (towers = nodes, signal strength = edge weights).

4. Khalti’s Transaction Verification

   • When you pay via Khalti, the system recursively checks:
     • Is the merchant verified? → Check parent account.
     • Is the bank connected? → Recursive call to bank API.
   • Idea used: Recursive API calls for hierarchical verification.

Recursive Strategies

1. Divide-and-Conquer

Split the problem into smaller subproblems, solve them recursively, and combine results. Example: Binary Search

int binarySearch(int arr[], int left, int right, int key) {
    if (left > right) return -1;           // Base case: not found
    int mid = left + (right - left) / 2;
    if (arr[mid] == key) return mid;       // Base case: found
    if (key < arr[mid])
        return binarySearch(arr, left, mid - 1, key);  // Recursive left
    else
        return binarySearch(arr, mid + 1, right, key); // Recursive right
}

Trace for binarySearch([1,3,5,7], 0, 3, 5):

2. Backtracking

Explore all possible solutions by recursively making choices and undoing them if they fail. Example: N-Queens Problem

flowchart TD
    A["Place Queen at (0,0)"] --> B["Is safe?\nYes → Next row"]
    B --> C["Place Queen at (1,2)"]
    C --> D["Is safe?\nNo → Backtrack"]
    D --> E["Try (1,1)"]
    E --> F["Is safe?\nYes → Next row"]
    F --> G["... Continue until solution or all rows exhausted"]

Code Snippet (Pseudocode):

bool isSafe(int board[N][N], int row, int col) {
    // Check column and diagonals
}
bool solveNQueens(int board[N][N], int row) {
    if (row == N) return true;  // Base case: all queens placed
    for (int col = 0; col < N; col++) {
        if (isSafe(board, row, col)) {
            board[row][col] = 1;
            if (solveNQueens(board, row + 1)) return true;  // Recursive
            board[row][col] = 0;  // Backtrack
        }
    }
    return false;
}

Tail Recursion and Optimization

Tail recursion occurs when the recursive call is the last operation in the function. Compilers can optimize this to reuse the stack frame (no extra memory). Example: Tail-Recursive Factorial

int factTail(int n, int accumulator) {
    if (n == 0) return accumulator;  // Base case
    return factTail(n - 1, n * accumulator);  // Tail call
}

Trace for factTail(3, 1):

Advantage: No stack overflow for large n (if compiler optimizes). Disadvantage: Not all compilers optimize tail calls (e.g., default GCC does not; use -O2 flag).

Memoization: Caching Recursive Results

For problems with overlapping subproblems (e.g., Fibonacci), store results to avoid redundant calculations. Example: Memoized Fibonacci

#include <stdio.h>
#define MAX 100
int memo[MAX];

int fib(int n) {
    if (n <= 1) return n;                     // Base case
    if (memo[n] != -1) return memo[n];       // Return cached result
    memo[n] = fib(n - 1) + fib(n - 2);       // Compute and cache
    return memo[n];
}

int main() {
    for (int i = 0; i < MAX; i++) memo[i] = -1;
    printf("fib(10) = %d\n", fib(10));      // Output: 55
    return 0;
}

Time Complexity:

• Without memoization: $O(2^n)$ (exponential).
• With memoization: $O(n)$ (linear).

Visual:

Common Pitfalls and How to Avoid Them

Example: Broken Fibonacci

int fibWrong(int n) {
    if (n == 0) return 0;          // Correct
    return fibWrong(n) + fibWrong(n - 1);  // Infinite loop!
}

Fix: Change fibWrong(n) to fibWrong(n - 1).

Exam Tip

1. Always show the base case first in your code and explain it clearly.
2. Trace recursive calls for small inputs (e.g., n=3) in your answer.
3. Compare recursion vs. iteration:
   • Use recursion for natural recursive problems (trees, backtracking).
   • Use iteration for performance-critical loops (e.g., large n in factorial).
4. Memoization is a bonus point—mention it if the problem has overlapping subproblems (e.g., Fibonacci, knapsack).
5. Watch out for:
   • Questions asking to convert recursion to iteration (use a stack or accumulator).
   • Problems where recursion is inefficient (e.g., linear search → use loop).

Past Exam Question Analysis: Q: Write a program to display Fibonacci series up to the 15th term using recursion. Model Answer:

#include <stdio.h>
void fibonacci(int n, int a, int b) {
    if (n == 0) return;             // Base case: stop after 15 terms
    printf("%d ", a);
    fibonacci(n - 1, b, a + b);     // Tail-recursive call
}
int main() {
    fibonacci(15, 0, 1);            // Start with F0=0, F1=1
    return 0;
}

Output: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 Trace for n=3:

Key Formula to Remember: For a recursive function with depth d:

• Time: $O(d)$ if no redundant work (e.g., tail recursion).
• Space: $O(d)$ for stack frames (unless tail-call optimized).