Recursion & Backtracking: Algorithms, Stacks, and Problem-Solving

TAKEAWAYS:

• Recursion replaces loops by breaking problems into smaller subproblems, using a call stack to track state.
• Backtracking systematically explores solutions by undoing choices (e.g., N-Queens, Sudoku).
• The Tower of Hanoi illustrates recursion’s elegance with $O(2^n)$ time and $O(n)$ space.
• Recursion vs. iteration: recursion simplifies code but risks stack overflow for deep recursion.
• Memoization (caching) optimizes recursive Fibonacci from $O(2^n)$ to $O(n)$.
• Real-world uses: Pathao’s route optimization, Ncell’s call forwarding, and Daraz’s inventory checks.

1. Recursion: Definition and Mechanics

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

• Base case: Terminates recursion (e.g., fib(0) = 0).
• Recursive case: Breaks the problem into subproblems (e.g., fib(n) = fib(n-1) + fib(n-2)).

How Recursion Works Under the Hood

Every recursive call adds a stack frame (variables, return address) to the call stack. When the base case is reached, frames pop off, returning results upward.

flowchart TD
    A["Main Function"] --> B["Call fib(3)"]
    B --> C["Call fib(2)"]
    C --> D["Call fib(1)"]
    D --> E["Call fib(0)"] -->|"Base case"| F["Return 0"]
    F --> D --> E --> C -->|"fib(1)=1"| D
    D --> B -->|"fib(2)=1"| C
    C --> B -->|"fib(3)=2"| A

Figure 1: Call stack for fib(3) (each node is a stack frame with local variables).

2. Recursive vs. Iterative Approaches

Example: Fibonacci sequence.

# Recursive (inefficient)
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

# Iterative (optimal)
def fib_iter(n):
    a, b = 0, 1
    for _ in range(n): a, b = b, a + b
    return a

Trace for fib(4):

3. Tower of Hanoi: A Classic Recursive Problem

Problem: Move n disks from the source peg to the destination peg, using an auxiliary peg, with the constraint that a larger disk cannot be placed on a smaller one.

Algorithm Steps

1. Move n-1 disks from source to auxiliary (recursive call).
2. Move the largest disk from source to destination.
3. Move n-1 disks from auxiliary to destination (recursive call).

flowchart TD
    A["TOH(n, source, dest, aux)"] --> B["TOH(n-1, source, aux, dest)"]
    B --> C["Move disk from source to dest"]
    C --> D["TOH(n-1, aux, dest, source)"]
    C -->|"Note: Largest disk"| E["Disk n"]

Figure 2: Recursive calls for Tower of Hanoi (n=3).

Worked Example: n=3

Step 1: Move disk 1 (A→C)
Step 2: Move disk 2 (A→B)
Step 3: Move disk 1 (C→B)
Step 4: Move disk 3 (A→C)
Step 5: Move disk 1 (B→A)
Step 6: Move disk 2 (B→C)
Step 7: Move disk 1 (A→C)

Minimum moves: $2^n-1$ (for n disks).

4. Backtracking: Exploring All Possibilities

Backtracking is a systematic search technique that:

1. Makes a choice.
2. Recursively explores consequences.
3. Backtracks (undoes choices) if a dead end is reached.

Applications:

• Solving Sudoku (constraint satisfaction).
• Finding N-Queens solutions (placing n queens on a chessboard without threats).
• Pathao’s route optimization (backtracking to avoid traffic jams).

N-Queens Example (n=4)

flowchart TD
    A["Place queen in row 1"] --> B["Check conflicts"]
    B -->|"Conflict"| C["Backtrack to row 0"]
    B -->|"Safe"| D["Place queen in row 2"]
    D --> E["Check row 2"]
    E -->|"Conflict"| C
    E -->|"Safe"| F["Place queen in row 3"]
    F --> G["Check row 3"]
    G -->|"Conflict"| C
    G -->|"Safe"| H["Place queen in row 4"] -->|"Solution"| I["Valid configuration"]
    I -->|"Example"| J["[[0,1],[1,3],[2,0],[3,2]]"]

Figure 3: Backtracking for N-Queens (n=4).

5. Optimizations: Memoization and Dynamic Programming

Recursion can be exponentially slow (e.g., Fibonacci). Memoization caches results to avoid redundant calculations.

Memoized Fibonacci

def fib_memo(n, memo={}):
    if n in memo: return memo[n]
    if n <= 1: return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

Time complexity: $O(n)$ (linear time).

6. Real-World Applications

1. Pathao’s Route Optimization

• Idea: Backtracking explores all possible routes to find the fastest path from Kathmandu to Pokhara, avoiding traffic.
• Algorithm: Dijkstra’s (non-recursive) or A* (recursive heuristic) to backtrack and select the optimal path.

2. Ncell’s Call Forwarding

• Idea: Recursion handles nested call forwarding rules (e.g., "If busy, forward to X; if X is busy, forward to Y").
• Example:

  def forward_call(number, rules):
      if rules[number] == "busy":
          return forward_call(rules["next"], rules)
      else:
          return "ring"
  

3. Daraz’s Inventory Management

• Idea: Backtracking checks all possible stock locations for a missing item (e.g., "Item not in warehouse A? Check warehouse B").
• Pseudocode:

  def find_item(item, warehouses):
      for warehouse in warehouses:
          if item in warehouse:
              return warehouse
          else:
              continue  # Backtrack to next warehouse
  

7. Advantages and Disadvantages

8. Exam Tips

1. Define recursion clearly: Mention base case + recursive case.
2. Draw the call stack: For fib(n) or TOH, show stack frames growing/ shrinking.
3. Compare recursive vs. iterative: Highlight tradeoffs (e.g., Fibonacci time complexity).
4. Practice backtracking: Solve N-Queens or Sudoku on paper; explain backtracking steps.
5. Memoization is key: For Fibonacci, show how caching reduces time complexity.
6. Real-world link: Relate TOH to Ncell’s call forwarding or Pathao’s route planning.