Recursive Solutions and Algorithm Implementation

Consider the difference between iteration and recursion. Iteration uses loops (like for or while) to repeat a block of code until a condition is met. Recursion, instead, uses the structure of the function calls themselves to drive the repetition. While recursion can make complex logic much clearer, it is important to note that it carries overhead due to the constant creation of stack frames. If a problem has a simple, efficient iterative solution, it is often better to use iteration instead of recursion.

Worked Example: The Factorial of $n$

The factorial of a non-negative integer $n$ (denoted as $n!$) is a classic example used to demonstrate both iterative and recursive approaches.

Iterative Approach

In an iterative solution, we use a loop to multiply numbers from 1 up to $n$:

int factItr(int n) {
    int fc = 1;
    for(int i = 1; i <= n; ++i) {
        fc *= i;
    }
    return fc;
}

Recursive Approach

In a recursive solution, we define $n!$ based on the definition of $(n-1)!$:

• Base Case: If $n = 0$, the factorial is $1$.
• Recursive Step: If $n > 0$, $n! = n \times (n-1)!$.

int factRec(int n) {
    if (n == 0) return 1; // Base Case
    else return n * factRec(n - 1); // Recursive Call
}

To prove the correctness of this recursive function, we can use mathematical induction. We show that the property holds for the base case ($n=0$), assume it holds for $n=k$, and then prove it must hold for $n=k+1$.

Searching Algorithms: Binary Search and Beyond

Recursion is highly effective in searching through structured data. One of the most efficient methods is Binary Search, which uses a "divide-and-conquer" strategy.

Binary Search

To find a target value $T$ in a sorted array $A$ of size $n$, binary search does not check every element. Instead, it:

1. Finds the middle element of the current range.
2. If the target matches the middle, the search is complete.
3. If the target is smaller than the middle, it recursively searches the left half.
4. If the target is larger, it recursively searches the right half.

The base case for a binary search occurs when the search range becomes empty (i.e., the first index exceeds the last index), indicating the target is not present.

Recursive Search and Backtracking

In more complex scenarios, such as finding a path through a network of cities (an airline route), a simple recursive search might fail if it hits a dead end or enters a loop. To solve this, we use backtracking.

Backtracking is a combination of recursion and iteration. When the algorithm reaches a "dead end" (a base case indicating no solution exists along the current path), it "backs up" to the previous step and tries a different path. This is often referred to as a Depth-First Search.

Advanced Recursive Patterns

Divide-and-Conquer

Many recursive algorithms follow the Divide-and-Conquer paradigm, which consists of three steps:

1. Divide: Break the problem into smaller sub-problems of the same type.
2. Conquer: Solve the sub-problems recursively. If they are small enough, solve them directly.
3. Combine: Merge the solutions of the sub-problems to form the final solution.

A prime example is Merge Sort, which divides an array into two halves, sorts them recursively, and then merges the two sorted halves back together.

The Towers of Hanoi

The Towers of Hanoi is a classic puzzle that demonstrates how recursion can solve problems that are difficult to conceptualize iteratively. The goal is to move $n$ disks from a source pole to a destination pole using a spare pole, following the rule that a larger disk can never be placed on a smaller one.

The recursive logic for $n$ disks is:

1. Move $n-1$ disks from the source to the spare pole.
2. Move the largest disk from the source to the destination pole (the base case for a single disk).
3. Move the $n-1$ disks from the spare pole to the destination pole.

The number of moves required for $n$ disks follows the mathematical pattern: $\text{moves}(n) = 2^n - 1$.

Summary Note: While recursion provides elegant and clear solutions for problems like Merge Sort or the Towers of Hanoi, always weigh the clarity of the code against the memory overhead of the function call stack.