1
2
3
4
5
6

type recursion(int p_n)                 // p_n is the parameter for the current recursion
{
    if(base_condition) return solve;     // solve is the solution under the base condition
    recursion(p_n-1);                   // p_n-1 is the parameter for the next recursion
    ......                              // other operations
}

From the pseudocode, we can deduce the basic execution logic of a recursive algorithm: the outer function continually calls deeper into inner layers until it hits the base condition, and then executes and returns layer by layer. The resulting execution process begins at the innermost (or bottom) function call, returning successively to the outer (or upper) layers. The following diagram illustrates this execution process:

As can be seen, before the outer function executes its functional portion, it first enters inner layers for execution until hitting the base condition (\(sum(1)\) in the figure above), and then executes the actual functional operations from the bottom up.

The advantage of recursive algorithms lies in their concise and easy-to-understand code, enabling bottom-up traversal and execution without using conventional loops. The disadvantage is lower space efficiency, as each recursive call allocates new space in memory; moreover, excessive recursion depth can lead to stack overflow issues.

1.2 Divide and Conquer Algorithm

Note: Divide-and-conquer is an application of recursion, but not all divide-and-conquer algorithms require recursive implementations.

The so-called "divide and conquer" means decomposing a large-scale problem that is complex to solve directly into multiple smaller-scale subproblems that can be solved directly using the same simple method. From this, we can see that the mindset of this algorithm is to repeatedly solve smaller subproblems, and then merge the answers of the subproblems into the answer to the large problem. The decomposition structure is shown in the figure below.

It is easy to see that the order of solving problems can follow a "bottom-up" approach. Therefore, recursive methods can be used to solve them.

Referring to the figure above, let \(n\) be the problem scale, and suppose each step divides into \(k\) subproblems until the subproblem scale is 1. Then the time complexity of merging these problems is \(O(n)\). Thus \(T(n)=kT(n/k)+O(n)\), and the overall time complexity can be reduced to \(O(n\log{n})\).

It should be noted that divide-and-conquer algorithms require the problem to meet the following conditions:

• Each time the problem is divided, the division conditions cannot overlap (they must be mutually exclusive);
• The union of the division conditions must cover all cases of the original problem.

2. Algorithm Applications

Here are several algorithmic applications of recursion and divide-and-conquer strategies.

2.1 Binary Search

Binary search is a typical application of divide-and-conquer algorithms. In a given sorted array, by comparing the target element with the middle element of the array, the sub-interval containing the target is determined. This operation is then repeated on that sub-interval until the target element is found or the interval becomes empty. Taking searching for the element 47 in a sorted array as an example, the process is shown below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

template<class Type>
int binary_search(Type *arr, const Type &target, int n) // Search for target in arr[0,n-1]

// Returns index if found, otherwise returns -1
{
    int left = 0, right = n - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (arr[mid] == target) 
            return mid;
        else if (arr[mid] > target) 
            right = mid - 1;
        else 
            left = mid + 1;
    }
    return -1;
}

1
2
3
4
5
6
7
8
9
10
11

// X, Y are two large integers, n is the number of digits, k is the base.
// Choose numeric types according to actual circumstances
int big_data_multiple(int X,int Y,int n,int k)
{
    if(n==1) return X*Y;
    int A=X/pow(k,n/2),B=X%pow(k,n/2);
    int C=Y/pow(k,n/2),D=Y%pow(k,n/2);
    int AC=big_data_multiple(A,C,n/2);
    int BD=big_data_multiple(B,D,n/2);
    return AC*pow(k,n)+((A-B)*(D-C)+AC+BD)*pow(,n/2)+BD;
}

1
2
3
4
5
6
7
8
9
10
11
12

template <class Type>
void MergeSort(Type *arr, int left, int right) // Sort arr[left,right]
{
    if (left <right)
    {
        int mid = (left + right) / 2;
        MergeSort(arr, left, mid);
        MergeSort(arr, mid + 1, right);
        Merge(arr, left, mid, right);
        Copy(arr, left, right);                 // Copy the sorted result back to the original array
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

template <class Type>
void MergeSort(Type *a, int n)
{
    Type *b = new Type[n];
    int seg = 1;
    while (seg < n)
    {
        MergePass(a, b, seg, n);        // Merge into array b
        seg += seg;
        MergePass(b, a, seg, n);        // Merge into array a
        seg += seg;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

template <class Type>
void QuickSort(Type *a, int p, int r)   // Main algorithm function
{
    if (p < r)
    {
        int q = Partition(a, p, r);     // Get pivot position
        QuickSort(a, p, q - 1);         // Sort left elements
        QuickSort(a, q + 1, r);         // Sort right elements
    }
}

template <class Type>
int Partiton(Type *a, int p, int r)
{
    int i = p, j = r+1;
    Type x = a[p];                      // Pivot element
    while (true)
    {
        while (a[++i] < x && i < r);    // Find first element greater than x from left to right
        while (a[--j] > x);             // Find first element less than x from right to left
        if (i >= j) break;              // Exit loop if the two pointers meet
        swap(a[i], a[j]);               // Swap two elements
    }
    a[p] = a[j];                        // Place pivot in correct position
    a[j] = x;
    return j;                           // Return pivot position
}

1
2
3
4
5
6
7

template <class Type>
int RandomizedPartition(Type *a, int p, int r)
{
    int i = p + rand() % (r - p + 1);   // Randomly select pivot element
    swap(a[i], a[p]);
    return Partition(a, p, r);
}

1
2
3
4
5
6
7
8
9
10
11
12

template <class Type>
int RandomizedSelect(Type *a, int p, int r, int k)
{
    if (p == r) 
        return a[p];
    int i = RandomizedPartition(a, p, r);
    int j = i - p + 1;
    if (k <= j) 
        return RandomizedSelect(a, p, i, k);
    else 
        return RandomizedSelect(a, i + 1, r, k - j);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

template <class Type>
Type Select(Type *a,int p, int r, int k)
{
    if(r-p<75)
    {
        Sort a[p:r];
        return a[p+k-1];
    }
    for(int i = 0; i <= (r-p-4)/5; i++)
    {
        Swap the 3rd smallest element of a[p+5*i] to a[p+5*i+4] with a[p+i];
        Type x = Select(a,p,p+(r-p-4)/5,(r-p-4)/10);    // Find median of medians
        int i = Partition(a,p,r,x),
            j = i-p+1;
        if(k<=j) 
            return Select(a,p,i,k);
        else
            return Select(a,i+1,r,k-j);
    }
}