Recursion: Definition, Mechanics, Applications & Analysis

What is Recursion?

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

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

Why Use Recursion?

• Elegance: Simplifies complex problems (e.g., tree traversals, factorial calculation).
• Divide-and-conquer: Breaks problems into smaller subproblems (e.g., merge sort, binary search).
• Natural fit: Matches problems with recursive definitions (e.g., Fibonacci sequence, directory structures).

Key Components of Recursion

1. Base Case

The termination condition that stops further recursive calls. Without it, the function recurses infinitely (stack overflow).

2. Recursive Case

The function calls itself with a smaller or simpler input, progressing toward the base case.

3. Recursive Call Stack

Each recursive call adds a stack frame (local variables, return address). The call stack unwinds when the base case is reached.

How Recursion Works: A Step-by-Step Trace

Example: Factorial of a Number $n!=n\times (n-1)!$

Definition:

• Base case: $0!=1$
• Recursive case: $n!=n\times (n-1)!$

Trace for $4!$:

flowchart TD
    A["factorial(4)"] --> B["4 × factorial(3)"]
    B --> C["factorial(3)"]
    C --> D["3 × factorial(2)"]
    D --> E["factorial(2)"]
    E --> F["2 × factorial(1)"]
    F --> G["factorial(1)"]
    G --> H["1 × factorial(0)"]
    H --> I["factorial(0) = 1 (base case)"]
    I -->|"Unwind"| J["factorial(1) = 1 × 1 = 1"]
    J -->|"Unwind"| K["factorial(2) = 2 × 1 = 2"]
    K -->|"Unwind"| L["factorial(3) = 3 × 2 = 6"]
    L -->|"Unwind"| M["factorial(4) = 4 × 6 = 24"]

Code Implementation (C):

#include <stdio.h>

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

int main() {
    printf("4! = %d\n", factorial(4)); // Output: 24
    return 0;
}

Step-by-Step Execution:

Types of Recursion

1. Direct Recursion

A function calls itself directly. Example: Factorial, Fibonacci sequence.

2. Indirect Recursion

Function A calls function B, which eventually calls A again. Example:

void A() { B(); }
void B() { if (condition) A(); }

3. Tail Recursion

The recursive call is the last operation in the function. Can be optimized by compilers to avoid stack growth. Example:

int factorial_tail(int n, int accumulator) {
    if (n == 0)
        return accumulator;
    else
        return factorial_tail(n - 1, n * accumulator); // Tail call
}

Recursion vs. Iteration

Real-World Applications of Recursion

1. eSewa (Nepal) – Bill Payment Hierarchy

• Idea Used: Tree-like recursive traversal of service categories (electricity, phone, insurance).
• How: When you select a service (e.g., "Electricity Bill"), eSewa recursively drills down to subcategories (e.g., "Nepal Electricity Authority") until you reach the exact bill type. This mirrors recursive menu navigation in GUI applications.

2. Pathao (Ride-Hailing) – Optimal Route Calculation

• Idea Used: Divide-and-conquer recursion for pathfinding.
• How: Pathao’s algorithm (similar to Dijkstra’s) uses recursion to explore all possible routes from the pickup to destination location. Each recursive call evaluates a smaller subproblem (e.g., "shortest path from A to B via C").

3. Nepal Stock Exchange (NEPSE) – Market Tree Traversal

• Idea Used: Recursive in-order traversal of stock categories.
• How: NEPSE’s website categorizes stocks into sectors (e.g., Banking, Hydropower, FMCG). When you expand a sector (e.g., "Banking"), it recursively loads subcategories (e.g., "Commercial Banks") and individual stocks. This is implemented as a binary tree traversal in the backend.

Worked Example: Tower of Hanoi

Problem: Move $n$ disks from the source rod to the destination rod using an auxiliary rod, 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 rod.
2. Move the $n$-th disk from the source to the destination.
3. Move the $n-1$ disks from the auxiliary to the destination.

Code (C):

#include <stdio.h>

void hanoi(int n, char source, char dest, char aux) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", source, dest);
    } else {
        hanoi(n - 1, source, aux, dest);      // Step 1
        printf("Move disk %d from %c to %c\n", n, source, dest); // Step 2
        hanoi(n - 1, aux, dest, source);      // Step 3
    }
}

int main() {
    hanoi(3, 'A', 'C', 'B'); // Move 3 disks from A to C
    return 0;
}

Trace for $n=3$:

flowchart TD
    A["hanoi(3, A, C, B)"] --> B["hanoi(2, A, B, C)"]
    B --> C["hanoi(1, A, C, B)"]
    C --> D["Move disk 1 from A to C"]
    D --> E["hanoi(1, B, C, A)"]
    E --> F["Move disk 2 from A to B"]
    F --> G["hanoi(2, B, C, A)"]
    G --> H["hanoi(1, B, A, C)"]
    H --> I["Move disk 1 from B to A"]
    I --> J["hanoi(1, C, A, B)"]
    J --> K["Move disk 1 from C to A"]
    K --> L["hanoi(1, B, C, A)"]
    L --> M["Move disk 2 from B to C"]
    M --> N["hanoi(1, A, C, B)"]
    N --> O["Move disk 1 from A to C"]

Output:

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to A
Move disk 3 from A to C
Move disk 1 from A to B
Move disk 2 from B to C
Move disk 1 from B to C

Recursion in Data Structures

1. Binary Trees

Recursion is natural for tree traversals:

• In-order: Left → Root → Right
• Pre-order: Root → Left → Right
• Post-order: Left → Right → Root

Example: In-order Traversal

void inorder(Node* root) {
    if (root != NULL) {
        inorder(root->left);   // Recurse left
        printf("%d ", root->data); // Visit root
        inorder(root->right);  // Recurse right
    }
}

2. Linked Lists

Recursive functions can traverse or search linked lists:

int search(Node* head, int key) {
    if (head == NULL) return 0; // Base case: not found
    if (head->data == key) return 1;
    return search(head->next, key); // Recurse
}

Advantages and Disadvantages of Recursion

Advantages:

1. Simplicity: Often shorter and easier to understand than iterative solutions.
2. Elegance: Matches problems with recursive definitions (e.g., Fibonacci, tree traversals).
3. Divide-and-conquer: Efficient for problems like merge sort, quicksort.

Disadvantages:

1. Stack Overflow: Deep recursion can exhaust the call stack (e.g., factorial(10000)).
2. Performance Overhead: Function calls are slower than loops.
3. Debugging: Harder to trace than iterative code.

When to Use Recursion?

Exam Tip

Common Exam Questions on Recursion:

1. Trace the execution of a recursive function (e.g., factorial(5), fibonacci(4)).

   • Tip: Draw the call stack at each step. Show the order of function calls and returns.

2. Write recursive functions for:

   • Factorial, Fibonacci, binary search, tree traversals.
   • Tip: Always define the base case first, then the recursive case.

3. Convert recursion to iteration (and vice versa).

   • Tip: Use a stack (LIFO) to simulate recursion iteratively.

4. Analyze time/space complexity of recursive algorithms.

   • Tip: Recursive calls often lead to exponential time (e.g., naive Fibonacci is $O(2^n)$).

5. Identify tail recursion and explain its optimization.

   • Tip: Tail-recursive functions can be converted to loops by the compiler.

High-Scoring Strategies:

• Draw the call stack for traces (visuals score extra marks).
• Compare recursion vs. iteration in a table (show trade-offs).
• Relate to real-world examples (e.g., "How does Pathao use recursion for route optimization?").
• Mention tail recursion and its advantages in interviews/exams.

Summary Checklist

Before the exam, ensure you can:

1. Define recursion and its two key components (base case, recursive case).
2. Trace the execution of a recursive function step-by-step.
3. Write recursive functions for factorial, Fibonacci, and tree traversals.
4. Convert a recursive function to an iterative one (and vice versa).
5. Explain the advantages/disadvantages of recursion.
6. Recognize tail recursion and its optimization.
7. Apply recursion to real-world scenarios (e.g., menu systems, pathfinding).