Welcome To Sora Park

Before diving into proving that a recursive algorithm is correct, the following page is recommended to read through in order to understand what the recursive algorithm is and how it works:

2021.08.25 - [Algorithms] - Recursive Algorithm 재귀 알고리즘

Mathematical induction, and its variant strong induction, can be used to prove the correctness of a recursive algorithm.

# Example 1: powers of real numbers

Method: mathematical induction

• Basis step:
  If n = 0, the first step of the algorithm is that power(a, 0) = 1. This is correct because a^0 = 1 for every nonzero real number a.
• Inductive step:
  The inductive hypothesis is the statement that power(a, k) = a^k for all a ≠ 0 for an arbitrary nonnegative integer k. That is, the inductive hypothesis is the statement that the algorithm correctly computes a^k. If the inductive hypothesis is true, the algorithm correctly computes a^(k+1).
  
  Because k+1 is a positive integer, when the algorithm computes a^(k+1), the algorithm sets power(a, k+1) = a * power(a, k). By the inductive hypothesis,
  - power(a, k) = a^k, so
  - a * power(a, k) = a * a^k = a^(k+1)
  This completes the inductive step!

Hence, the algorithm always computes a^n correctly when a ≠ 0 and n is a non-negative integer.

# Example 2: modular powers

Method: strong induction

• Basis step:
  Let b be an integer and m an integer with m ≥ 2.
  When n = 0, the algorithm sets mpower(b, n, m) equal to 1 (m ≥ 2). This is correct because b^0 mod m = 1.
• Inductive step:
  The inductive hypothesis is the statement that mpower(b, j, m) = b^j mod m for all integers 0 ≤ j < k whenever b is a positive integer and m is an integer with m ≥ 2. If the inductive hypothesis is correct, mpower(b, k, m) = b^k mod m.
  
  Because the recursive algorithm handles odd and even values of k differently, the inductive step should be split into two cases:
  - When k is even, mpower(b, k, m) =
  (mpower(b, k/2, m))^2 mod m =
  (b^(k/2) mod m)^2 mod m = 
  b^k mod m
  where the inductive hypothesis was used to replace mpower(b, k/2, m) = b^k mod m.
  - When k is odd, mpower(b, k, m) =
  (((mpower(b, floor(k/2), m))^2 mod m * b mod m) mod m =
  (((b^(floor(k/2)) mod m)^2 mod m * b mod m) mod m = 
  b^(2 * floor(k/2) + 1) mod m =
  b^k mod m
  because 2 * floor(k/2) + 1 = 2 * (k-1) / 2 + 1 = k when k is odd.
  The inductive hypothesis was used to replace mpower(b, floor(k/2), m) by b^(floor(k/2)) mod m.

Both steps have been completed by strong induction, so this algorithm is correct! 

Generally, to prove that recursive algorithms are correct, strong induction is more often used rather than just mathematical induction.

void test(int input)
{
    if (input > 0)
    {
        printf("%d, ", input);
        test(input - 1);
        printf("%d, ", input);
    }
}

The test function will give the following output back once called:

"3, 2, 1, 1, 2, 3, "

The first print function completes printing out the given input value three times before the second one is called.

This is how the recursive algorithm works!

Recursive algorithms solve a problem by reducing it to an instance of the same problem with smaller input.

Here is a recursive algorithm for computing n factorial (n!):

int test(int input)
{
    printf("%d, ", input);
    if (input == 0)
    {
        return 1;
    }
    else
    {
        return input * test(input - 1);
    }
}

The output is as follows:

"3, 2, 1, 0, "

# Recursive function for exponentiation

The below definition would be very helpful to solve the problem!

a^(n+1) = a * a^n for n > 0 and the initial condition a^0 = 1.

To find a^n, successively use the recursive step to reduce the exponent until it becomes zero.

int test(int base, int input)
{
    if (input > 0)
    {
        test(base, input - 1);
    }

    ans = (input == 0 ? 1 : base * ans);
    printf("%d, ", ans);

    return ans;
}

The output of the function is "1, 2, 4, 8, ".

If someone doesn't want to see the output in the terminal, the below method would be more explicit to understand how the algorithm works:

int test(int base, int input)
{
	if (input == 0)
    {
    	return 1;
    }
    else
    {
    	return base * test(base, input - 1);
    }
}

# Recursive modular exponentiation

The method is based on the fact below:

b^2 mod m = (b * b^(n-1) mod m)) mod m and the initial condition b^0 mod m = 1

However, there is a much more efficient recursive algorithm based on the observation that

In case that n is even, b^n mod m = (b^(n/2) mod m)^2 mod m
In case that n is odd, b^n mod m = ((b^(floor(n/2)) mod m)^2 mod m * b mod m) mod m

int test(int b, int n, int m)
{
    if (n == 0)
    {
        return 1;
    }
    else if (n % 2 == 0)
    {
        ans = pow(test(b, n / 2, m), 2);
        return ans % m;
    }
    else
    {
        ans = pow(test(b, floor(n / 2), m), 2);
        return (ans % m * b % m) % m;
    }
}

# Recursive linear search algorithm

This algorithm is designed to search for the first occurrence of x in the sequence.

int test(int i, int x)
{
    if (arr[i] == x)
    {
        return i;
    }
    else if (i == arr.size() - 1)
    {
        return -1;
    }
    else
    {
        return test(i + 1, x);
    }
}

# Recursive binary search algorithm

This approach is to find the location of x in the sequence of integers in increasing order.

To perform a binary search, it begins by comparing x with the middle term,

a[floor(n+1) / 2]

int test(int i, int j, int x)
{
    m = floor((i + j) / 2);
    if (arr[m] == x)
    {
        return m;
    }
    else if (x < arr[m] && i < m)
    {
        return test(i, m - 1, x);
    }
    else if (x > arr[m] && j > m)
    {
        return test(m + 1, j, x);
    }
    else
    {
        return -1;
    }
}