Skip to the content of the web site.

Lesson 3.02: Recursive functions

All of the examples here are on repl.it, and you are welcome to complete the unimplemented ones.

Up to this point, we have described functions in C++, how a function can call itself, and also how function calls are facilitated through the call stack. Next, we are going to discuss a special class of functions: those that necessarily call themselves to solve a problem.

When solving a problem, in some cases, it may be possible to solve a similar but simpler problem, and to then use that solution to the simpler problem to solve the more difficult problem.

Here is a nice example by Kent Fredric:
Suppose you have a breakout of a disease in a city. In trying to contain the disease, you may first attempt to find Patient 0; for example, a person who was ill on an flight into the city. You could then try to contact everyone who came in contact with Patient 0, and determine whether or not those individuals were infected. For those who are or are displaying symptoms of infection, you may then try to contact everyone who came into contact with those individuals, and so on. This potentially solves the larger problem of containing an outbreak.

As another example, when the Dean of Engineering is preparing a strategic plan for the faculty, the Dean does not speak to individual faculty members. Instead, the Dean will query the six departmental chairs and two school directors for feedback. The chairs and directors will then recursively query the faculty members in each department. The responses will be collated into a single report, and then the dean will receive a total of eight reports, which will then be incorporated into the strategic plan.

Recursion in mathematics

Now, the problems we are trying to solve will often mathematical in nature. In each case, if you are breaking a problem down into simpler sub-problems, then at some point there must be some solutions that need no longer require recursion for solving.

Example: factorial

For example, consider calculating $6!$. One definition of the factorial function is $n! = n \cdot (n - 1)!$. We already know that $0! = 1$, so $3! = 3 \cdot 2!$, but $2! = 2 \cdot 1!$, and $1! = 1 \cdot 0! = 1 \cdot 1 = 1$, so $2! = 2$ and thus $3! = 3$.

Sorting a pile of examinations

Imagine you are trying to sort 320 final examinations by the uWaterloo Student ID Number. Trying to sort these by hand may be very difficult, but consider the following:

Suppose you had four piles of 80 examinations, each of which is sorted. In this case, you could lay all four piles in front of you, and you could easily merge them into a single sorted pile by always picking the examination whose uWaterloo Student ID Number is lowest of the four that you see. Now, you somehow have to sort four separate piles of 80 examinations.

Well, you could divide the 320 examinations into four piles of 80 examinations, and then take each of the four piles of 80 examinations and break them down into four piles of 20 examinations. Now, sorting 20 examinations is quite easy—it probably takes less than a minute. Then, given four piles of 20 examinations, you could merge these into a single sorted pile of 80 examinations. Having done this four times, you now have four piles of 80 examinations which you can then merge into a single sorted pile of 320 examinations.

Let us say that it takes one minute to sort nineteen examinations. At the same time, if you are trying to merge $n$ examinations in four sorted piles into one sorted pile, it may take three seconds to find and select the next smallest examination. Thus, merging $n$ examinations requires $3n$ seconds. Thus, sorting 320 examinations would require sorting sixteen piles of 20 examinations, which would be sixteen minutes in total. Then, merging four piles of 20 examinations would require another $4 \times 20 \times 3$ or four minutes each, and finally merging four piles of 80 examinations each would require $4 \times 80 \times 3$ seconds or sixteen minutes. This is a total of 48 minutes.

While this may not be a great use of one hour, it is still reasonable and better than trying to sort all 320 examinations at once.

What is nice about this method is that if you wanted to sort four times as many examinations again (1280), this would only take you 5⅓ times longer than sorting 320 examinations: sorting four times as many times takes not much more than four times as much time.

Recursion

We have already seen how one function can call itself. For example,

double fast_sin( double x ) {
    if ( x < 0.0 ) {
        return -fast_sin( -x );
    }

    return ((
        -0.11073981636184074*x - 0.057385341027109429
    )*x + 1.0)*x;
}

Factorial function

The factorial function, can however be defined recursively:

$n! = \left\{ \begin{matrix} 1 & n = 0\\ n\cdot(n - 1)! & n \ge 1 \end{matrix} \right.$.

The second condition describes the recursion, but the first case is necessary, as it describes a known value, or base case. If we did not have the base case, it would not be possible to compute the factorial, for $1! = 1 \times 0!$, but $0!$ would thus be defined as $0! = 0 \cdot (-1)!$, and so on. Each time we implement a recursively defined function, we must determine the base cases and deal with them.

// Calculate n! using recursion
unsigned int factorial( unsigned int n ) {
    // The base case
    if ( n == 0 ) {
        return 1;
    }

    // The recursive step...
}

For the recursive step, we note that $n! = n \cdot (n - 1)!$, so calculating $(n - 1)!$ is just another call to the factorial function:

// Calculate n! using recursion
unsigned int factorial( unsigned int n ) {
    // The base case
    if ( n == 0 ) {
        return 1;
    }

    return n * factorial( n - 1 );
}

Thus, when you call factorial( 5 ), the last step will call factorial( 4 ), and when that result is finally returned, it will multiply that result by 5 and return that value.

Binomial coefficients

The binomial coefficient $n \choose k$ is equal to the number of ways that $k$ objects can be chosen from $n$ unique objects. In your mathematics courses, you saw that this could be shown to be equal to:

${n \choose k} = \frac{n!}{k! (n - k)!}$

and so if we implemented the factorial function, we could also implement a function that calculates the binomial coefficients:

// Calculate n choose k
unsigned int binomial( unsigned int n, unsigned int k ) {
    return factorial( n )/factorial( k )/factorial( n - k );
}

This, however, can cause problems, for ${100 \choose 2} = 4950$, but to calculate this, you must first determine that

$100! = 9332621\cdots\text{ 150 missing digits }\cdots0$

and that

$98! = 942\cdots\text{ 150 missing digits }0$.

You must then divide these two and then divide that result by two. While we have not discussed this yet, there simply isn't enough memory in the processor to compute this efficiently, and so we will use a different approach:

A recursive definition of the binomial coefficients is:

${n \choose k} = \left\{ \begin{matrix} 1 & k = 0 \vee k = n\\ {n - 1 \choose k} + {n - 1 \choose k - 1} & 0 < k < n \end{matrix} \right.$.

The $\vee$ indicates the or, so either $k = 0$ or $k = n$.

In this example, there are many base cases: whenever $k = 0$ or $k = n$, we have a solution:

// Calculate n choose k
unsigned int binomial( unsigned int n, unsigned int k ) {
    // The base cases:
    //  - there is only one way to choose either 0 or n
    //    objects from n objects
    if ( (k == 0) || (k == n) ) {
        return 1;
    }

    // The recursive step...
}

The recursive step requires us to call this function twice:

// Calculate n choose k
unsigned int binomial( unsigned int n, unsigned int k ) {
    // The base cases:
    //  - there is only one way to choose either 0 or n
    //    objects from n objects
    if ( (k == 0) || (k == n) ) {
        return 1;
    }

    // Ensure that 0 < k < n
    assert( (0 < k) && (k < n) );

    return binomial( n - 1, k ) + binomial( n - 1, k - 1 );
}

This algorithm does not run into the same issues we had previously: there is no overflow of values, although there may still be values we cannot calculate because they are too large; however, this will be able to calculate $100 \choose 2$.

As an aside, one may note that there are no ways of choosing 10 objects from a collection of nine unique objects, and therefore we could return zero instead:

// Calculate n choose k
unsigned int binomial( unsigned int n, unsigned int k ) {
    // The base cases:
    //  - there is only one way to choose either 0 or n
    //    objects from n objects
    if ( (k == 0) || (k == n) ) {
        return 1;
    } else if ( k > n ) {
        return 0;
    }

    // Ensure that 0 < k < n
    assert( (0 < k) && (k < n) );

    return binomial( n - 1, k ) + binomial( n - 1, k - 1 );
}

In this case, the recursive step is to cal

Greatest common divisor

The

Indirect recursion

In some cases, a function can be recursively defined in terms of another function, which then calls the original function, and so on. A simple example are two functions:

bool is_even( unsigned int n );
bool is_odd( unsigned int n );

Here, n == 0 is the base case for both of these functions, the first returning true and the second returning false.

For other values of n, n is even if is_odd( n - 1 ), and n is odd if is_even( n - 1 ). Implement both of these functions.

Bonus: In this course, we have stressed the need for the function declarations to appear first before any function definitions appear. When you are finished, see if you can get your code to compile if you do not include either function declaration.

Questions and practice:

1. The Fibonacci numbers are defined as $F_0 = 0$ and $F_1 = 1$, after which $F_n = F_{n - 1} + F_{n - 2}$. Now, it is better to think of these as a function of an integer argument, so F(0) == 0 and F(1) == 1.

Implement and test this function:

unsigned int fibonacci( unsigned int n );

2. The Ackermann function for positive integers is defined as

$A(m,n) = \left\{ \begin{matrix} n + 1 & m = 0 \\ A(m - 1, 1) & m \ge 1 \wedge n = 0 \\ A(m - 1, A(m, n - 1)) & m \ge 1 \wedge n \ge 1 \end{matrix} \right.$.

The hat $\wedge$ should be read as and. Implement this function:

unsigned int ackermann( unsigned int m, unsigned int n );

You will not be able to calculate too many values, as these numbers become very large very quickly. For example, $A(4,3) = 125$ while $A(3,4) = 2^{2^{65536}} - 3$. You should test your function by testing some of the values returned in the Wikipedia page.

3. For an argument $x$, we define $x^0 = 1$, and then for an integer power $n > 0$, we define $x^n = x \cdot x^{n - 1}$. This should already look familiar, as it is similar to the definition of the factorial. There is only one difference: we also have to calculate negative powers, but this is remedied quite easily: $x^n = \frac{1}{x^{-n}}$. Thus, we only need check for this special case, and then return appropriately. Implement this function:

double pow_simp( double x, long n );

We will need very large values of n, so we will use long, which can store values as large as 9 quintillion, while int can only store values as large as 2 billion.

Question: how long does it take you to execute the following code?

	std::cout << pow_simp( 1.000000001, 1000000000 ) << std::endl;

You may notice that the answer looks familiar, as it does actually look a lot like $e \approx 2.7182818$.

4. Continuing from Question 3, we will redefine the recursive step into two different cases:

  • If $n = 2m$ (or $n$ is even), we will calculate $y = x^m$ and then return $y^2$.
  • Otherwise, $n = 2m + 1$ (or $n$ is odd), we will calculate $y = x^m$ and then return $xy^2$.

This will require a local variable. Implement this function:

double pow_div( double x, long n );

Question: how long faster does this execute the following instruction when compared to pow_simp(...)?

	std::cout << pow_div( 1.000000001, 1000000000 ) << std::endl;

5. Go back to the $\Gamma$ function and calculate the following:

$\Gamma(1)$, $\Gamma(2)$, $\Gamma(3)$, $\Gamma(4)$, and $\Gamma(5)$. Do you recognize these values?

6. Implement the Hofstadter G sequence where:

$G(n) = \left\{ \begin{matrix} 0 & n = 0 \\ n - G(G(n - 1)) & n \ge 1 \end{matrix} \right.$.

Sequence: 0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, ...

7. Implement the Hofstadter H sequence where

$H(n) = \left\{ \begin{matrix} 0 & n = 0 \\ n - H(H(H(n - 1))) & n \ge 1 \end{matrix} \right.$.

Sequence: 0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 10, 10, ...

8. Implement the Hofstadter F and M sequences where

$F(n) = \left\{ \begin{matrix} 1 & n = 0 \\ n - M(F(n - 1)) & n \ge 1 \end{matrix} \right.$.
$M(n) = \left\{ \begin{matrix} 0 & n = 0 \\ n - F(M(n - 1)) & n \ge 1 \end{matrix} \right.$.

This is an example of indirect recursion where one function calls another which then calls the first, etc.

9. Implement the Hofstadter Q sequence where

$Q(n) = \left\{ \begin{matrix} 1 & n = 1 \vee n = 2 \\ Q(n - Q(n - 1)) + Q(n - Q(n - 2)) & n \ge 3 \end{matrix} \right.$.

Sequence: 1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 11, 11, ...

10. Consider the following implementation of the factorial function:

// Pre-processor include directives
#include <iostream>
#include <cassert>

// Function declarations
int main();
double factorial( unsigned int n );
double factorial_internal( unsigned int n, double solution );

// Function definitions
int main() {
    std::cout << " 10! =     3628800 = " << factorial(  10 ) << std::endl;
    std::cout << "100! = 9.33262e157 = " << factorial( 100 ) << std::endl;

    return 0;
}

// The user interface allows the user to call factorial( n )
// when the user wishes to calculate n!
//  - this will call the internal factorial function that
//    implements a version that allows tail recursion to be used
//  - 21! > 2^64, so we use double
double factorial( unsigned int n ) {
    assert( n <= 170 );
    return factorial_internal( n, 1.0 );
}

// function--all information that is required is passed onto
//      n    solution      equivalence
//    ------------------------------------
//     10          1
//      9         10
//      8         90     = 10x9
//      7        720     = 10x9x8
//      6       5040
//      5      30240
//      4     151200     = 10x9x8x7x6x5
//      3     604800
//      2    1814400     = 10x9x8x7x6x5x4x3
//      1    3628800
double factorial_internal( unsigned int n, double solution ) {
    } else {
        return factorial_internal( n - 1, n*solution );
    }
}

You can run this code on repl.it.

This is an implementation of the factorial function that allows for tail recursion, as all information for the solution is passed onto the subsequent function call. Could you re-implement any other function described in this section in such a way so as to allow for tail recursion?