Recursion: Definition, Mechanics, Tower of Hanoi, Fibonacci, and Backtracking

TAKEAWAYS:

• Recursion is a problem-solving technique where a function calls itself to break problems into smaller subproblems.
• Every recursive function must have a base case (termination condition) and a recursive case (progress toward the base).
• The Tower of Hanoi demonstrates recursion’s elegance in moving disks between pegs with minimal moves.
• Fibonacci numbers and factorial calculations are classic recursive problems with iterative alternatives.
• Recursion can lead to stack overflow if the base case is unreachable or inefficiently designed.
• Backtracking uses recursion to explore all possible solutions incrementally, pruning invalid paths early.

1. What is Recursion?

Recursion is a programming technique where a function calls itself to solve a problem by breaking it into smaller, similar subproblems. It mirrors real-world processes like:

• A mirror reflecting itself (infinite if not terminated).
• A matryoshka doll (each smaller doll contains another).
• Folding a paper (each fold creates a smaller version of the original).

Key Components of Recursion

A recursive function must have:

1. Base Case: The simplest instance of the problem (terminates recursion).
2. Recursive Case: The function calls itself with a modified input, moving toward the base case.

flowchart TD
    A["Recursive Function\nF(n)"] -->|"Check if base case?"| B["Yes\nReturn solution"]
    A -->|"No<br/>Modify input"| C["F(n-1) or F(n/2) etc."]
    C --> A

Why Use Recursion?

• Elegance: Simplifies complex problems (e.g., tree traversals, divide-and-conquer).
• Readability: Code closely mirrors mathematical definitions.
• Natural Fit: Problems like Fibonacci, factorial, or tree traversals are inherently recursive.

Disadvantages

• Stack Overflow: Deep recursion exhausts the call stack (e.g., infinite recursion).
• Overhead: Function calls consume memory and time (slower than iteration for some problems).
• Debugging: Harder to trace than loops.

2. Recursive Function Structure

Every recursive function follows this template:

def recursive_function(n):
    # Base case: terminate recursion
    if n == base_condition:
        return base_result

```figure
{"type":"tree","nodes":[6,3,2,1,1],"highlight":[3],"caption":"Recursive calls for factorial(3): 3! = 3 × 2! → 3 × 2 × 1! → 3 × 2 × 1 × 1"}

# Recursive case: break problem into smaller subproblems
else:
    return combine_results(recursive_function(n - 1), ...)

Example: Factorial of a Number

Definition: ( n! = n \times (n-1) \times (n-2) \times \dots \times 1 ), with ( 0! = 1 ).

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

Trace for factorial(3):

Final Result: ( 3 \times 2 \times 1 \times 1 = 6 ).

3. Tower of Hanoi: A Classic Recursive Problem

Problem Statement: Move ( n ) disks from the source peg to the destination peg using an auxiliary peg, following these rules:

1. Only one disk can be moved at a time.
2. A larger disk cannot be placed on top of a smaller disk.

Recursive Solution

1. Move ( n-1 ) disks from the source to the auxiliary peg (using the destination as auxiliary).
2. Move the largest disk from the source to the destination.
3. Move the ( n-1 ) disks from the auxiliary peg to the destination (using the source as auxiliary).

flowchart TD
    A["Move n disks\nfrom A to C"] --> B["Move n-1 disks\nfrom A to B"]
    A --> C["Move largest disk\nfrom A to C"]
    A --> D["Move n-1 disks\nfrom B to C"]

Visual Trace for ( n = 3 ) Disks

Initial State: A=[3,2,1], B=[], C=[]
Step 1: Move 2 disks from A to B (using C as auxiliary)
  A=[3], B=[2,1], C=[]
Step 2: Move largest disk (3) from A to C
  A=[], B=[2,1], C=[3]
Step 3: Move 2 disks from B to C (using A as auxiliary)
  A=[], B=[], C=[3,2,1]

Minimum Moves: ( 2^n - 1 ) (for ( n = 3 ), moves = 7).

4. Fibonacci Sequence: Recursion vs. Iteration

Definition: The Fibonacci sequence is defined as: [ F(n) = \begin{cases} 0 & \text{if } n = 0, \ 1 & \text{if } n = 1, \ F(n-1) + F(n-2) & \text{if } n > 1. \end{cases} ]

Recursive Implementation

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

Trace for fibonacci(4):

fib(4) → fib(3) + fib(2)
fib(3) → fib(2) + fib(1) → (fib(1) + fib(0)) + 1 → (1 + 0) + 1 = 2
fib(2) → fib(1) + fib(0) → 1 + 0 = 1
Result: 2 + 1 = 3

Problem with Naive Recursion

• Exponential Time Complexity: ( O(2^n) ) due to repeated calculations (e.g., fib(2) is computed twice in fib(4)).
• Solution: Use memoization (caching results) or iterative approach (( O(n) ) time).

5. Backtracking: Exploring Solutions Recursively

Backtracking is a recursive algorithm that:

1. Builds candidates incrementally.
2. Abandons ("backtracks") a candidate as soon as it determines it cannot lead to a valid solution.

stateDiagram-v2
  [*] --> Permute
  state Permute {
    [*] --> Swap
    Swap --> Check: Base Case?
    Check --> |Yes| Print
    Check --> |No| Recurse
    Recurse --> Swap
  }

Example: Generating Permutations

Problem: Generate all permutations of [1, 2, 3].

def permute(nums, start=0):
    if start == len(nums) - 1:
        print(nums)
    else:
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]  # Swap
            permute(nums, start + 1)                     # Recurse
            nums[start], nums[i] = nums[i], nums[start]  # Backtrack

Trace for permute([1, 2, 3]):

1. Swap 1 and 1 → [1, 2, 3] → recurse on [1, 2, 3] (start=1).
   • Swap 2 and 2 → [1, 2, 3] → recurse on [1, 2, 3] (start=2) → print [1, 2, 3].
   • Swap 2 and 3 → [1, 3, 2] → recurse on [1, 3, 2] (start=2) → print [1, 3, 2].
2. Swap 1 and 2 → [2, 1, 3] → recurse on [2, 1, 3] (start=1).
   • Swap 1 and 1 → [2, 1, 3] → print [2, 1, 3].
   • Swap 1 and 3 → [2, 3, 1] → print [2, 3, 1].
3. Swap 1 and 3 → [3, 2, 1] → recurse on [3, 2, 1] (start=1).
   • Swap 2 and 2 → [3, 2, 1] → print [3, 2, 1].
   • Swap 2 and 1 → [3, 1, 2] → print [3, 1, 2].

Output: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1].

6. Recursion vs. Iteration: Comparison

7. Real-World Applications of Recursion

1. eSewa (Nepal) – Bill Splitting

• Idea Used: Recursive division of bills among friends.
• How: If 4 friends split a bill of Rs. 2000, each pays Rs. 500. If one friend owes Rs. 200 more, the remaining Rs. 300 is split recursively among the other 3 friends.
• Code Analogy:

  def split_bill(total, people):
      if people == 1:
          return total
      else:
          return (total // people) + split_bill(total % people, people - 1)
  

2. WhatsApp (Global) – Message Forwarding

• Idea Used: Recursive tree traversal for forwarding chains.
• How: When you forward a message to 5 friends, each of whom forwards it to 5 more, the total forwards grow exponentially (( 5^n )), modeled by recursion.

3. Daraz (Nepal) – Order Processing

• Idea Used: Recursive validation of nested product categories.
• How: Daraz’s search algorithm recursively checks subcategories (e.g., "Electronics" → "Mobile" → "Samsung") to filter products, similar to tree traversal.

4. NTC (Nepal) – Network Routing

• Idea Used: Recursive pathfinding in network topology.
• How: NTC’s routers use recursive algorithms (like Dijkstra’s) to find the shortest path for data packets between nodes, avoiding loops.

8. Common Pitfalls and How to Avoid Them

1. Infinite Recursion

   • Cause: Missing or incorrect base case.
   • Fix: Always verify the base case covers all termination scenarios.
   • Example: factorial(-1) without a check for negative inputs.

2. Stack Overflow

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

3. Redundant Calculations

   • Cause: Repeatedly solving the same subproblem (e.g., fib(3) called twice).
   • Fix: Store results in a dictionary (memoization).

9. Exam Tip: How to Score Full Marks

1. Define Recursion Clearly

   • Start with: "Recursion is a technique where a function calls itself to solve smaller instances of the same problem."
   • Always mention base case and recursive case.

2. Draw Recursive Calls

   • For Tower of Hanoi or Fibonacci, show the call stack or state transitions (use tables or diagrams).
   • Example: For fibonacci(4), show the tree of recursive calls.

3. Pseudocode > Full Code

   • Write clear pseudocode (e.g., for Tower of Hanoi) instead of verbose implementations.
   • Example:

     TO_HANOI(n, source, destination, auxiliary):
         if n == 1:
             move disk from source to destination
         else:
             TO_HANOI(n-1, source, auxiliary, destination)
             move disk from source to destination
             TO_HANOI(n-1, auxiliary, destination, source)
     

4. Time Complexity Analysis

   • For recursive functions, derive the complexity (e.g., ( O(2^n) ) for naive Fibonacci).
   • Compare with iterative solutions (e.g., ( O(n) ) for dynamic programming).

5. Real-World Connection

   • Link problems to eSewa (bill splitting), Daraz (order processing), or NTC (routing).
   • Example: "Like Daraz’s category filters, recursion traverses nested structures efficiently."

10. Practice Problems for Exam Preparation

1. Write a recursive function to calculate the sum of digits of a number (e.g., 1234 → 10).
2. Solve the Tower of Hanoi for 4 disks and show the sequence of moves.
3. Explain why the recursive Fibonacci has exponential time and how memoization fixes it.
4. Generate all subsets of {1, 2, 3} using backtracking.
5. Convert the following iterative loop into a recursive function:

   def print_numbers(n):
       for i in range(1, n+1):
           print(i)
   

In the real world

• eSewa (Nepal) uses recursion in pathfinding algorithms to optimize delivery routes for cash-on-delivery orders, breaking down the problem into smaller city blocks (divide-and-conquer).
• Ncell’s network tower placement relies on backtracking to find optimal signal coverage by recursively testing configurations and discarding invalid ones (e.g., overlapping towers).
• Daraz’s recommendation system employs recursive tree traversals (like Fibonacci’s call tree) to explore user purchase histories and suggest products, though memoization avoids redundant calculations.