Recursion

Introduction to Recursion

Recursion is a programming technique where a function calls itself directly or indirectly to solve a problem. It is a powerful concept in computer science and is particularly useful for solving problems that can be broken down into smaller, similar subproblems.

In recursion, a complex problem is divided into smaller instances of the same problem until a base case is reached. The base case is a simple scenario that can be solved directly without further recursion. Once the base case is reached, the solutions to the smaller problems are combined to solve the original problem.

Key Components of Recursion

• Base Case: A condition that stops the recursion. Without a base case, the recursion would continue indefinitely, leading to a stack overflow.
• Recursive Case: The part where the function calls itself with a simpler version of the problem.
• Progress Toward Base Case: Each recursive call should move closer to the base case to ensure that the recursion eventually terminates.

Example: Factorial Calculation

A classic example of recursion is calculating the factorial of a number. The factorial of a non-negative integer n, denoted as n!, is the product of all positive integers less than or equal to n.

Mathematically, factorial is defined as:

• 0! = 1
• n! = n × (n-1)! for n > 0

Here's a recursive implementation of factorial in C++:

#include <iostream>
using namespace std;

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

int main() {
    int n = 5;
    cout << "Factorial of " << n << " is " << factorial(n) << endl;
    return 0;
}
                    

In this example:

• The base case is when n = 0, which returns 1.
• The recursive case is when n > 0, which returns n multiplied by the factorial of (n-1).
• Each recursive call decreases n by 1, moving closer to the base case.

factorial(5)
├── 5 * factorial(4)
│   ├── 4 * factorial(3)
│   │   ├── 3 * factorial(2)
│   │   │   ├── 2 * factorial(1)
│   │   │   │   ├── 1 * factorial(0)
│   │   │   │   │   └── return 1
│   │   │   │   └── return 1 * 1 = 1
│   │   │   └── return 2 * 1 = 2
│   │   └── return 3 * 2 = 6
│   └── return 4 * 6 = 24
└── return 5 * 24 = 120
                        

Recurrence

A recurrence relation is an equation that defines a sequence recursively. In the context of algorithms, recurrence relations are often used to describe the running time or space complexity of recursive algorithms.

Common Forms of Recurrence Relations

• Linear Recurrence: T(n) = T(n-1) + f(n)
• Divide and Conquer Recurrence: T(n) = aT(n/b) + f(n)
• Binary Recursion: T(n) = T(n-1) + T(n-2) + f(n)

Solving Recurrence Relations

There are several methods to solve recurrence relations:

1. Substitution Method

In this method, we guess a solution and then use mathematical induction to prove that our guess is correct.

2. Recursion Tree Method

We draw a tree representing the recursive calls and sum up the costs at each level of the tree.

3. Master Theorem

The Master Theorem provides a direct way to solve recurrence relations of the form T(n) = aT(n/b) + f(n), where a ≥ 1, b > 1, and f(n) is a given function.

Example: Recurrence Relation for Binary Search

Binary search is a classic divide-and-conquer algorithm. Its recurrence relation is:

T(n) = T(n/2) + c

where c is a constant representing the time for comparison and other operations.

Using the Master Theorem, we can determine that the time complexity of binary search is O(log n).

Use of Stack in Recursion

When a function is called, the system allocates memory for its local variables and parameters on the stack. This memory allocation is known as a stack frame or activation record. In recursion, each recursive call creates a new stack frame, which is pushed onto the call stack.

How the Call Stack Works in Recursion

1. When a function is called, a new stack frame is created and pushed onto the call stack.
2. The stack frame contains the function's local variables, parameters, and the return address (where to return after the function completes).
3. When the function returns, its stack frame is popped from the call stack, and control returns to the calling function.
4. In recursion, multiple stack frames of the same function can exist simultaneously on the call stack, each representing a different recursive call.

Initial Call: factorial(3)

Call Stack after factorial(3) is called:
┌───────────────┐
│ factorial(3)  │ ← Top
└───────────────┘

Call Stack after factorial(2) is called from factorial(3):
┌───────────────┐
│ factorial(2)  │ ← Top
├───────────────┤
│ factorial(3)  │
└───────────────┘

Call Stack after factorial(1) is called from factorial(2):
┌───────────────┐
│ factorial(1)  │ ← Top
├───────────────┤
│ factorial(2)  │
├───────────────┤
│ factorial(3)  │
└───────────────┘

Call Stack after factorial(0) is called from factorial(1):
┌───────────────┐
│ factorial(0)  │ ← Top
├───────────────┤
│ factorial(1)  │
├───────────────┤
│ factorial(2)  │
├───────────────┤
│ factorial(3)  │
└───────────────┘

factorial(0) returns 1, its stack frame is popped:
┌───────────────┐
│ factorial(1)  │ ← Top
├───────────────┤
│ factorial(2)  │
├───────────────┤
│ factorial(3)  │
└───────────────┘

factorial(1) returns 1*1=1, its stack frame is popped:
┌───────────────┐
│ factorial(2)  │ ← Top
├───────────────┤
│ factorial(3)  │
└───────────────┘

factorial(2) returns 2*1=2, its stack frame is popped:
┌───────────────┐
│ factorial(3)  │ ← Top
└───────────────┘

factorial(3) returns 3*2=6, its stack frame is popped:
[Empty Call Stack]

Final result: 6
                        

Stack Overflow in Recursion

One of the main limitations of recursion is the risk of stack overflow. If the recursion is too deep (i.e., there are too many recursive calls), the call stack may run out of space, leading to a stack overflow error.

To avoid stack overflow, it's important to:

• Ensure that the recursion has a proper base case.
• Make sure that each recursive call moves closer to the base case.
• Consider using tail recursion or iterative solutions for problems with deep recursion.

Variants of Recursion

Recursion can take various forms depending on how the recursive calls are structured. Here are some common variants:

1. Linear Recursion

In linear recursion, each recursive call makes at most one recursive call. The factorial function we saw earlier is an example of linear recursion.

int factorial(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);  // Single recursive call
    }
}
                    

2. Binary Recursion

In binary recursion, each recursive call makes at most two recursive calls. The Fibonacci function is a classic example of binary recursion.

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);  // Two recursive calls
    }
}
                    

3. Multiple Recursion

In multiple recursion, each recursive call makes more than two recursive calls. The Tower of Hanoi problem with more than three pegs is an example of multiple recursion.

4. Mutual Recursion

In mutual recursion, two or more functions call each other in a cycle. This is also known as indirect recursion.

bool isEven(int n) {
    if (n == 0) {
        return true;
    } else {
        return isOdd(n - 1);  // Call to another function
    }
}

bool isOdd(int n) {
    if (n == 0) {
        return false;
    } else {
        return isEven(n - 1);  // Call back to the first function
    }
}
                    

5. Nested Recursion

In nested recursion, the parameter of a recursive call is itself a recursive call. The Ackermann function is a famous example of nested recursion.

int ackermann(int m, int n) {
    if (m == 0) {
        return n + 1;
    } else if (n == 0) {
        return ackermann(m - 1, 1);
    } else {
        return ackermann(m - 1, ackermann(m, n - 1));  // Nested recursive call
    }
}
                    

6. Tail Recursion

In tail recursion, the recursive call is the last operation in the function. Tail recursion can be optimized by compilers to use constant stack space, effectively converting it to iteration.

// Non-tail recursive factorial
int factorial(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);  // Not tail recursive (multiplication after recursive call)
    }
}

// Tail recursive factorial
int factorialTail(int n, int acc = 1) {
    if (n == 0) {
        return acc;
    } else {
        return factorialTail(n - 1, n * acc);  // Tail recursive (no operation after recursive call)
    }
}
                    

Execution of Recursive Calls

Understanding how recursive calls are executed is crucial for writing correct and efficient recursive functions. Let's examine the execution of recursive calls in detail.

Phases of Recursive Execution

The execution of a recursive function can be divided into two phases:

1. Winding Phase (or Calling Phase)

During the winding phase, the function makes recursive calls until it reaches the base case. Each recursive call creates a new stack frame and pushes it onto the call stack.

2. Unwinding Phase (or Returning Phase)

During the unwinding phase, the function returns from the base case and works its way back through the recursive calls, computing the final result. Each return pops a stack frame from the call stack.

Example: Execution of factorial(3)

Let's trace the execution of factorial(3) step by step:

Memory Usage in Recursive Calls

Each recursive call consumes memory on the call stack. The amount of memory used depends on the number of recursive calls and the size of each stack frame.

For example, in the factorial function, each recursive call uses a constant amount of memory (for the parameter n and the return address). The total memory usage is proportional to the depth of recursion, which is O(n) for factorial(n).

In contrast, for the binary recursive Fibonacci function, the memory usage can be much higher due to the exponential number of recursive calls. This is one reason why the naive recursive implementation of Fibonacci is inefficient.

Recursive Functions

Let's explore some common recursive functions and their implementations in C++.

1. Factorial

We've already seen the factorial function. Here it is again for reference:

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

2. Fibonacci

The Fibonacci sequence is defined as follows: F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1.

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}
                    

Note that this naive recursive implementation of Fibonacci is inefficient due to the repeated calculations. A more efficient approach would use dynamic programming or memoization.

3. Greatest Common Divisor (GCD)

The GCD of two integers is the largest positive integer that divides both numbers without a remainder. The Euclidean algorithm is a recursive method to find the GCD.

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}
                    

4. Tower of Hanoi

The Tower of Hanoi is a classic problem that demonstrates the power of recursion. The goal is to move a stack of disks from one peg to another, with the constraint that a larger disk cannot be placed on top of a smaller disk.

void towerOfHanoi(int n, char source, char auxiliary, char destination) {
    if (n == 1) {
        cout << "Move disk 1 from " << source << " to " << destination << endl;
        return;
    }
    
    towerOfHanoi(n - 1, source, destination, auxiliary);
    cout << "Move disk " << n << " from " << source << " to " << destination << endl;
    towerOfHanoi(n - 1, auxiliary, source, destination);
}
                    

5. Binary Search

Binary search is a divide-and-conquer algorithm that finds the position of a target value within a sorted array.

int binarySearch(int arr[], int left, int right, int target) {
    if (right >= left) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        }
        
        if (arr[mid] > target) {
            return binarySearch(arr, left, mid - 1, target);
        }
        
        return binarySearch(arr, mid + 1, right, target);
    }
    
    return -1;  // Element not found
}
                    

6. Merge Sort

Merge sort is a divide-and-conquer sorting algorithm that divides the input array into two halves, recursively sorts them, and then merges the sorted halves.

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    // Create temporary arrays
    int* L = new int[n1];
    int* R = new int[n2];
    
    // Copy data to temporary arrays
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }
    
    // Merge the temporary arrays back into arr[left..right]
    int i = 0;  // Initial index of first subarray
    int j = 0;  // Initial index of second subarray
    int k = left;  // Initial index of merged subarray
    
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    // Copy the remaining elements of L[], if there are any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    // Copy the remaining elements of R[], if there are any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
    
    delete[] L;
    delete[] R;
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        // Sort first and second halves
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        
        // Merge the sorted halves
        merge(arr, left, mid, right);
    }
}
                    

7. Quick Sort

Quick sort is another divide-and-conquer sorting algorithm that picks an element as a pivot and partitions the array around the pivot.

int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // Choose the rightmost element as pivot
    int i = low - 1;  // Index of smaller element
    
    for (int j = low; j < high; j++) {
        // If current element is smaller than or equal to pivot
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi is partitioning index, arr[pi] is now at right place
        int pi = partition(arr, low, high);
        
        // Recursively sort elements before and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
                    

Iteration versus Recursion

Both iteration and recursion are control structures that allow us to perform repetitive tasks. Let's compare these two approaches:

Advantages of Recursion

• Simplicity: Recursive solutions can be more elegant and easier to understand for problems that are naturally recursive (e.g., tree traversal, divide-and-conquer algorithms).
• Reduced Code Size: Recursive solutions often require fewer lines of code.
• Easier to Prove Correctness: Recursive solutions can be easier to prove correct using mathematical induction.

Disadvantages of Recursion

• Memory Overhead: Each recursive call adds a new frame to the call stack, which can lead to stack overflow for deep recursion.
• Performance Overhead: Function calls have overhead (pushing arguments, return address, etc.), which can make recursion slower than iteration.
• Difficulty in Debugging: Recursive functions can be harder to debug due to the multiple levels of function calls.

When to Use Recursion

• When the problem can be naturally divided into similar subproblems.
• When the problem has a recursive mathematical definition (e.g., factorial, Fibonacci).
• When traversing hierarchical data structures (e.g., trees, graphs).
• When implementing divide-and-conquer algorithms (e.g., merge sort, quick sort).

When to Use Iteration

• When the problem can be solved using simple loops.
• When memory efficiency is a concern.
• When performance is critical.
• When the recursion depth might be large, risking stack overflow.

Converting Recursion to Iteration

Many recursive functions can be converted to iterative functions to improve performance and avoid stack overflow. This often involves using an explicit stack data structure to simulate the call stack.

Let's see how to convert the factorial function from recursive to iterative:

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

// Iterative factorial
int factorialIterative(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}
                    

Similarly, let's convert the Fibonacci function from recursive to iterative:

// Recursive Fibonacci (inefficient)
int fibonacciRecursive(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
    }
}

// Iterative Fibonacci
int fibonacciIterative(int n) {
    if (n <= 1) {
        return n;
    }
    
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}
                    

Summary

In this section, we covered recursion, a powerful programming technique where a function calls itself to solve a problem:

• Introduction to recursion and its key components: base case, recursive case, and progress toward base case.
• Recurrence relations and methods to solve them.
• How the call stack is used in recursion and the risk of stack overflow.
• Various variants of recursion: linear, binary, multiple, mutual, nested, and tail recursion.
• Detailed execution of recursive calls, including the winding and unwinding phases.
• Common recursive functions: factorial, Fibonacci, GCD, Tower of Hanoi, binary search, merge sort, and quick sort.
• Comparison of iteration and recursion, including when to use each approach.
• Techniques for converting recursive functions to iterative functions.

Recursion is a fundamental concept in computer science and is particularly useful for solving problems that can be broken down into smaller, similar subproblems. Understanding recursion is essential for implementing efficient algorithms and data structures.