Recursive Algorithms

Recursive algorithms are powerful problem-solving techniques where a function or algorithm solves a problem by calling itself as a sub-routine. This approach is particularly elegant for problems that can be broken down into smaller, similar subproblems.

1. Understanding Recursive Algorithms

At its core, a recursive algorithm is an algorithm that invokes itself within its own definition. This self-referential property allows complex problems to be expressed in concise and understandable ways. For a recursive algorithm to work correctly and terminate, it must have two fundamental parts:

Base Case: This is the condition that stops the recursion. When the base case is met, the algorithm provides a direct solution without making any further recursive calls. It defines the smallest instance of the problem that can be solved trivially. Without a base case, a recursive algorithm would fall into an infinite loop, leading to a stack overflow.
Recursive Step: This is the part of the algorithm where the function calls itself. Each recursive call typically works on a smaller or simpler version of the original problem. The idea is to break down the original problem into one or more subproblems that are identical in nature but smaller in scope, until they reach the base case.

Consider the simple example of calculating the factorial of a number $n$ , denoted as $n!$ . The mathematical definition is:

n! = \begin{cases} 1 & \text{if } n = 0 \\ n \times (n-1)! & \text{if } n > 0 \end{cases}

Here, $n=0$ is the base case, and $n \times (n-1)!$ is the recursive step.

2. Types of Recursion

Recursive algorithms can be categorized based on how they invoke themselves:

2.1. Direct Recursion

An algorithm exhibits direct recursion if it calls itself explicitly within its own body. This is the most common form of recursion.

Pseudocode Example (Direct Recursion):

plaintext

Algorithm factorial(n)
{
    if (n == 0) then
    {
        return 1; // Base case
    }
    else
    {
        return n * factorial(n - 1); // Recursive step (direct call)
    }
}

2.2. Indirect Recursion

Indirect recursion occurs when an algorithm calls another algorithm, which in turn calls the first algorithm back, forming a cycle. This chain can involve two or more algorithms.

Pseudocode Example (Indirect Recursion):

plaintext

Algorithm A(x)
{
    // ...
    B(y); // Calls Algorithm B
    // ...
}
 
Algorithm B(z)
{
    // ...
    A(w); // Calls Algorithm A, completing the cycle
    // ...
}

Indirect recursion can express complex processes clearly, but it can be harder to trace and debug due to the multiple layers of calls.

3. Example: Tower of Hanoi

The Tower of Hanoi is a classic mathematical game or puzzle that beautifully demonstrates the power of recursive algorithms.

3.1. Puzzle Description and Rules

The puzzle consists of:

Three towers (or rods), typically labeled Source, Auxiliary (or Helper), and Destination.
A number of disks of different sizes, which can slide onto any tower.
The disks are initially stacked on the Source tower in decreasing size from bottom to top (i.e., the largest disk at the bottom, smallest at the top).

The objective is to move the entire stack of disks from the Source tower to the Destination tower, following these rules:

Only one disk can be moved at a time.
Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or an empty rod.
No larger disk may be placed on top of a smaller disk.

3.2. Recursive Solution

The problem can be solved recursively by breaking it down into three simpler steps:

Let $n$ be the number of disks to move from Source to Destination using Auxiliary.

Move $n-1$ disks from Source to Auxiliary using Destination as a temporary helper.
Move the largest ( $n$ -th) disk from Source to Destination.
Move the $n-1$ disks from Auxiliary to using as a temporary helper.

The base case for this recursion is when $n=1$ , where you simply move the single disk from Source to Destination.

Pseudocode for Tower of Hanoi:

plaintext

Algorithm TowerOfHanoi(n, source, destination, auxiliary)
{
    if (n >= 1)
    {
        // Step 1: Move n-1 disks from Source to Auxiliary
        TowerOfHanoi(n - 1, source, auxiliary, destination);
 
        // Step 2: Move the nth disk from Source to Destination
        write("Move disk ", n, " from tower ", source, " to tower ", destination);
 
        // Step 3: Move n-1 disks from Auxiliary to Destination
        TowerOfHanoi(n - 1, auxiliary, destination, source);
    }
}

3.3. C++ Implementation

cpp

#include <iostream>
#include <string>
 
// Function to solve the Tower of Hanoi puzzle recursively
void towerOfHanoi(int n, char source, char destination, char auxiliary) {
    // Base case: If there's only one disk, move it directly
    if (n == 1) {
        std::cout << "Move disk 1 from " << source << " to " << destination << std::endl;
        return;
    }
 
    // Recursive step 1: Move n-1 disks from source to auxiliary,
    // using destination as the temporary pole.
    towerOfHanoi(n - 1, source, auxiliary, destination);
 
    // Recursive step 2: Move the nth (largest) disk from source to destination.
    std::cout << "Move disk " <<

3.4. Tracing for $n=2$ Disks

Let's trace towerOfHanoi(2, 'A', 'C', 'B'):

towerOfHanoi(2, 'A', 'C', 'B')
- Calls towerOfHanoi(1, 'A', 'B', 'C') (move disk 1 from A to B using C)
  - Base case: n=1. Prints "Move disk 1 from A to B".
- Prints "Move disk 2 from A to C".
- Calls towerOfHanoi(1, 'B', 'C', 'A') (move disk 1 from B to C using A)
  - Base case: n=1. Prints "Move disk 1 from B to C".

Output for $n=2$ :

text

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

This trace shows that the puzzle is solved in 3 moves.

3.5. Time Complexity

The number of moves $M(n)$ for $n$ disks follows the recurrence relation:

M(n) = 2 M(n-1) + 1 \quad \text{for } n > 1

with the base case $M(1) = 1$ .

Expanding this: $M(1) = 1$ $M(2) = 2 M(1) + 1 = 2(1) + 1 = 3$

In general, the number of moves is $M(n) = 2^n - 1$ . This implies that the time complexity of the Tower of Hanoi problem is $O(2^n)$ , which is exponential.

4. Performance Analysis of Recursive Algorithms

Analyzing the performance of recursive algorithms involves determining their time complexity (how long they take to run) and space complexity (how much memory they use). Unlike iterative algorithms where performance can often be determined by counting loops and operations, recursive algorithms often require recurrence relations to describe their complexity.

Space Complexity: Recursive calls utilize the call stack. Each recursive call adds a new frame to the stack. The maximum depth of the recursion directly impacts the space complexity, as it determines the maximum number of active frames on the call stack at any given time.
Time Complexity: This is typically described by a recurrence relation that relates the time taken for a problem of size $n$ to the time taken for its subproblems.

5. Recurrence Relations

A recurrence relation is an equation or inequality that describes a function in terms of its values on smaller inputs. They are fundamental tools for analyzing the running time of recursive algorithms. Solving a recurrence relation means finding a closed-form expression for the function $T(n)$ , which gives the time complexity.

Common methods for solving recurrence relations include:

Substitution Method: Guessing a solution and verifying it by induction.
Iteration Method: Expanding the recurrence repeatedly until a pattern is observed and summing the terms.
Recursion Tree Method: Visualizing the recursive calls as a tree and summing the costs at each level.
Master Method: Providing a "cookbook" solution for specific forms of recurrences.

5.1. Substitution Method

The substitution method involves two main steps:

Guess the form of the solution: Based on observation or prior experience.
Use mathematical induction to find constants and show that the solution works.

Example: Calculating $x^n$ recursively Consider the recursive algorithm power(x, n):

plaintext

Algorithm power(x, n)
{
    if (n == 0) then
        return 1; // Base case
    else
        return x * power(x, n - 1); // Recursive step
}

Let $T(n)$ be the time complexity for power(x, n). The recurrence relation would be: $T(n) = T(n-1) + c$ (for the recursive call and constant operations) $T(0) = c_0$ (for the base case)

By repeated substitution: $T(n) = T(n-1) + c$ $T(n) = (T(n-2) + c) + c = T(n-2) + 2c$ ...

Let $n-k = 0 \Rightarrow k = n$ . $T(n) = T(0) + nc = c_0 + nc$ . Thus, .

Example: Recursive Fibonacci Series The standard recursive algorithm for Fibonacci numbers:

\text{Fib}(n) = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ \text{Fib}(n-1) + \text{Fib}(n-2) & \text{if } n > 1 \end{cases}

The recurrence relation for its time complexity $T(n)$ is: $T(n) = T(n-1) + T(n-2) + c$ for ,

This recurrence is similar to the Fibonacci sequence itself. A loose upper bound can be approximated: $T(n) \approx T(n-1) + T(n-1) + c = 2T(n-1) + c$ Expanding this, we get . A more precise analysis reveals , where (phi) is the golden ratio . This is still exponential, indicating that a naive recursive Fibonacci implementation is highly inefficient due to repeated calculations of the same subproblems.

5.2. Recursion Tree Method

The recursion tree method visualizes the costs of a recursive algorithm by drawing a tree where each node represents the cost of a single subproblem. By summing the costs at each level of the tree and then summing the costs of all levels, we can determine the total time complexity.

Example: $T(n) = T(n/4) + T(n/2) + n^2$

Let's visualize the recursion tree:

text

                                n^2                      (Cost at root)
                             /      \
                            /        \
                           /          \
                        T(n/4)       T(n/2)              (Costs of subproblems)
                       /   \         /   \
                      /     \       /     \
                     /       \     /       \
                 T(n/16) T(n/8) T(n/8) T(n/4)          (Costs of sub-subproblems)
                 ...                                   (Continues until base case)

Now let's calculate the cost at each level:

Level 0: $n^2$ Level 1: $(n/4)^2 + (n/2)^2 = n^2/16 + n^2/4 = (1/16 + 4/16)n^2 = (5/16)n^2$ Level 2:

Notice that $25/256 < 5/16 < 1$ . The sum of costs at each level is geometrically decreasing. The total cost will be approximately the cost of the root, $n^2$ , because the costs decrease rapidly as we go down the tree.

The total cost is $T(n) = n^2 + \frac{5}{16}n^2 + (\frac{5}{16})^2 n^2 + \dots + \Theta(1)$ This is a geometric series with ratio . The sum of such a series is , where is the first term. So, .

Therefore, $T(n) = \Theta(n^2)$ . The recursion tree method helps in deriving such closed-form solutions by summing up the work done at each level.

Summary

Recursive algorithms solve problems by calling themselves with smaller instances of the same problem.
They consist of a base case (termination condition) and a recursive step (self-invocation).
Direct recursion occurs when an algorithm calls itself; indirect recursion involves a chain of calls between multiple algorithms.
The Tower of Hanoi puzzle is a classic example of a problem elegantly solved with direct recursion, demonstrating exponential time complexity ( $O(2^n)$ ).
Analyzing recursive algorithm performance involves recurrence relations, which describe the time/space complexity in terms of smaller subproblems.
The Substitution Method and Recursion Tree Method are common techniques for solving recurrence relations to find closed-form time complexities.

Assessed progress

Recursive Algorithms

Recursive Algorithms

1. Understanding Recursive Algorithms

2. Types of Recursion

2.1. Direct Recursion

2.2. Indirect Recursion

3. Example: Tower of Hanoi

3.1. Puzzle Description and Rules

3.2. Recursive Solution

3.3. C++ Implementation

3.4. Tracing for $n=2$ Disks

3.5. Time Complexity

4. Performance Analysis of Recursive Algorithms

5. Recurrence Relations

5.1. Substitution Method

5.2. Recursion Tree Method

Summary

Key Concepts

Recursive Algorithm

Base Case

Recursive Step

Direct Recursion

Recurrence Relation

Quick Check

Advanced Data Structures

Advanced Data Structures