Recursion & Backtracking: Definitions, Factorial, Fibonacci, Tail Recursion, Backtracking Basics

TAKEAWAYS:

• Recursion breaks problems into smaller subproblems using a base case and recursive case, visualized via call stack growth.
• Tail recursion optimizes stack usage by moving computations to the base case, but compilers must support it.
• Backtracking systematically explores all possibilities by undoing choices (e.g., permutations, maze solving).
• Time complexity of recursive algorithms often follows $O(n)$ or $O(2^n)$ patterns, depending on branching.
• Real-world uses include eSewa’s transaction validation (recursive state checks) and Pathao’s route optimization (backtracking).
• Always trace recursive calls step-by-step to avoid stack overflow or infinite loops.

Core Concepts: Recursion

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

1. Base Case: The simplest instance that can be solved directly (terminates recursion).
2. Recursive Case: The function calls itself with a modified input, moving toward the base case.

How Recursion Works: Call Stack Visualization

graph TD
    A["factorial(3)"] --> B["factorial(2) + 3*factorial(2)"]
    B --> C["factorial(1) + 2*factorial(1)"]
    C --> D["factorial(0) = 1"]
    D -->|"returns"| C
    C -->|"returns"| B
    B -->|"returns"| A

Example: Factorial of 3 The call stack grows until the base case (factorial(0) = 1) is reached. Each frame holds:

• Function name (factorial)
• Parameters (n)
• Return address (next instruction)
• Local variables (e.g., intermediate results).

Trace Table for factorial(3)

Code Example (Python)

def factorial(n):
    if n == 0:  # Base case
        return 1
    else:
        return n * factorial(n - 1)  # Recursive case

Tail Recursion: Optimization

Definition: A recursive call is tail-recursive if it is the last operation in the function. Compilers can optimize this to reuse the stack frame, avoiding overflow.

Example: Tail-Recursive Factorial

def factorial_tail(n, accumulator=1):
    if n == 0:
        return accumulator
    else:
        return factorial_tail(n - 1, n * accumulator)  # Tail call

Trace Table

Advantages:

• Constant stack space (no growth).
• Faster execution (no pending operations).

Disadvantages:

• Not all languages optimize tail calls (e.g., Python does not).

Backtracking: Exploring Possibilities

Backtracking is a brute-force search that:

1. Makes a choice.
2. Recursively explores consequences.
3. Undoes choices if they lead to dead ends.

Example: Generating Permutations

graph TD
    A["Permute([1,2,3])"] --> B["Fix 1, Permute([2,3])"]
    B --> C["Fix 1,2, Permute([3])"]
    C --> D["Fix 1,2,3 → [1,2,3]"]
    C --> E["Fix 1,3, Permute([2])"]
    E --> F["Fix 1,3,2 → [1,3,2]"]
    B --> G["Fix 1,3,2 → [1,3,2]"]
    A --> H["Fix 2, Permute([1,3])"]
    H --> I["Fix 2,1,3 → [2,1,3]"]
    H --> J["Fix 2,3,1 → [2,3,1]"]
    A --> K["Fix 3, Permute([1,2])"]
    K --> L["Fix 3,1,2 → [3,1,2]"]
    K --> M["Fix 3,2,1 → [3,2,1]"]

Code Example (Python)

def permute(nums):
    def backtrack(start, end):
        if start == end:
            result.append(nums.copy())
        else:
            for i in range(start, end):
                nums[start], nums[i] = nums[i], nums[start]  # Swap
                backtrack(start + 1, end)                    # Recurse
                nums[start], nums[i] = nums[i], nums[start]  # Undo
    result = []
    backtrack(0, len(nums))
    return result

Trace for permute([1,2])

## In the Real World

1. eSewa Transaction Validation

   • Idea Used: Recursion to validate nested transaction dependencies (e.g., a bill payment may trigger a fine payment, which may require another approval).
   • How: Each transaction is checked recursively until all dependencies resolve to a base case (e.g., "user has sufficient balance").

2. Pathao’s Route Optimization

   • Idea Used: Backtracking to explore all possible delivery routes and select the fastest one without traffic jams.
   • How: The algorithm tries every possible path, backtracks when a route hits a dead end (e.g., a closed road), and keeps the shortest valid path.

3. Nepal Rastra Bank’s Loan Amortization

   • Idea Used: Recursion to calculate monthly payments for loans with compound interest.
   • Worked Example:
     • Problem: A loan of ₹1,000,000 at 10% annual interest, repaid in 5 years.
     • Recursive Formula: $\text{monthly\_payment}=\frac{P\times r\times (1+r{)}^n}{(1+r{)}^n-1}$ where $P=1,000,000$, $r=0.1/12$, $n=60$.
     • Trace: The bank’s system recursively computes each month’s principal and interest, reducing the loan balance until it reaches zero.

Comparison Table: Recursion vs. Iteration

Common Pitfalls and Exam Tips

1. Infinite Recursion

   • Cause: Missing or incorrect base case.
   • Fix: Always verify the base case covers the smallest input.
   • Example: factorial(-1) would recurse infinitely without a check for n < 0.

2. Stack Overflow

   • Cause: Deep recursion (e.g., fibonacci(1000) without memoization).
   • Fix: Use tail recursion or iteration for large n.

3. Backtracking Inefficiency

   • Cause: Exploring all possibilities without pruning.
   • Fix: Add constraints early (e.g., skip permutations with duplicate elements).

4. Tail Recursion Misconception

   • Mistake: Assuming all recursive functions are tail-recursive.
   • Truth: Only the last call in the function qualifies. Example:

     def bad_tail(n):
         if n == 0: return 1
         return n + bad_tail(n - 1)  # Not tail-recursive (pending `n + ...`)
     

## Exam Tip

1. For Algorithm Questions:

   • Always write the base case first, then the recursive case.
   • Use pseudocode if coding isn’t required, but show the recursive call clearly.
   • Trace 2–3 steps in your answer to demonstrate understanding (e.g., factorial(4)).

2. For Backtracking Questions:

   • Draw a decision tree (like the permutation example above) to show how choices are explored.
   • Highlight the undo step (e.g., swapping back in permutations).

3. For Tail Recursion:

   • Explicitly state whether the function is tail-recursive and why.
   • If asked to convert to tail recursion, show the accumulator variable.

4. Time Complexity:

   • Recursive algorithms often have $O(n)$ time (e.g., factorial) or $O(b^n)$ (e.g., permutations with branching factor b).
   • Memoization can reduce $O(2^n)$ to $O(n)$ (e.g., Fibonacci).

Visual Summary

mindmap
  root((Recursion & Backtracking))
    Concepts
      Recursion
        Base Case
        Recursive Case
        Call Stack
      Tail Recursion
        Optimization
        Accumulator
    Applications
      Factorial
      Fibonacci
      Permutations
      N-Queens
    Real-World
      eSewa
      Pathao
      Bank Loans
    Pitfalls
      Infinite Recursion
      Stack Overflow
      Inefficient Backtracking