Recursion

Recursion is self-reference. An recursive algorithm may refer to itself directly or indirectly to solve a different instance of the same problem being solved by the algorithm. The following self-reference is trivial but not algorithmic:

It is recursive but doesn’t terminate and so cannot be an algorithm. So the self-reference has to be invoked on different instances so that it may terminate. Typically, the self-references are used to solve smaller instances which guarantees termination.

Recursive minimum #

Consider the following algorithm to compute the minimum of an array of \(n\) elements.

int min(int a[], int n)
{
    if (n == 1) { return a[0]; }
    int b = min(a, n-1);
    if (b < a[n-1]) { return b; }
    return a[n-1];
}

Notice that the algorithm refers to itself to compute the minimum of a[0 ... n-2], the sub-array of the first \(n-1\) elements. This algorithm is based on the following inductive definition of the minimum element in a sequence.

The minimum element of a non-empty sequence denoted \(\min(a_0, \dotsc, a_{n-1})\) is:

• \(a_0\) if \(n=1\).
• \(\min(\min(a_0, \dotsc, a_{n-2}), a_{n-1})\) otherwise.

The proof of correctness of such algorithms are usually inductive.

The time complexity of recursive algorithms are usually expressed as a recurrence. For the min function, we can express the running time \(t\) as a function of the number of elements in the input array.

• \(t(1) = O(1)\).
• \(t(n) = t(n-1) + O(1)\) otherwise.

Solving, we obtain \(t(n) = O(n)\).

Indirect self-reference #

Self-reference can also be indirect. For example, here is a definition of odd and even numbers using indirect self-references.

• 0 is even.
• 1 is odd.
• \(n\) is even if \(n-1\) is odd.
• \(n\) is odd if \(n-1\) is even.

The above can be translated into C as:

int odd(int n);

int even(int n)
{
    if (n == 0) { return true; }
    if (n == 1) { return false; }
    return odd(n-1);
}

int odd(int n)
{
    if (n == 0) { return false; }
    if (n == 1) { return true; }
    return even(n-1);
}

Here, even refers to itself through odd and odd refers to itself through even. Notice that each recursive call is to an instance that is strictly smaller. This guarantees termination as long as all base cases terminate.

Eliminating recursion #

Compilers for imperative languages such as C does not offer good support for recursive definitions. So programmers prefer to convert recursive algorithms into algorithms with loops. While a recursion starts from large instances, moves to smaller ones, and then propagate the information from smaller instances to larger instances, a loop would typically solve larger and larger instances progressively with each iteration. An iteration would use the information from the previous iteration which solved a smaller instance to solve the larger instance.

In the following implementation of min with loops, each iteration computes the minimum of the sub-array a[0...i] into the variable m.

int min(int a[], int n)
{
    int m = a[0];
    for (int i = 1; i < n; ++i) {
        if (a[i] < m) { m = a[i]; }
    }
    return m;
}

In the following implementation of even, each iteration computes whether i is even or odd into the variable is_even.

int even(int n)
{
    int is_even = 1;
    for (int i = 0; i < n; ++i) {
        is_even = 1 - is_even;
    }
    return is_even;
}

Exercise #

1. Express Euclid’s GCD algorithm using recursion.

2. The modular exponentiation problem is defined as:

   • Name: MODEXP
   • Input: Natural numbers \(n\), \(m\), and \(p \neq 0\).
   • Output: \(n^m \mod p\).

   Devise a polynomial time algorithm for this problem using recursion. Note that there is always an \(m\) such that \(n^m > n^k+k\) for any fixed \(k\). So we cannot assume that \(n^m\) will fit into a single word.

3. Implement the recursive algorithm for MODEXP using a loop.

4. In the min algorithms, what happens if n is zero? Is there a sensible value to be returned when the array has no elements?

5. Prove the correctness of min and even with loops using appropriate invariants.