C++ Tutorial: Intro to Recursion

May 26th, 2015


Recursion is an important concept in computer science, yet it is often challenging for beginners to wrap their minds around. Don’t worry; it makes a lot of sense once you get it. Follow along with this tutorial, and I will help you master recursion!

In a nutshell, recursion is a divide­-and-­conquer method for solving certain kinds of problems. In this tutorial, we will use recursion to perform simple calculations such as computing n factorial. We will also use recursion to compute the nth term of the Fibonacci sequence. In real­-world applications, recursion is used for tasks like traversing through file directories.

Prerequisites

In order to benefit from this tutorial, you need a basic understanding of functions in C++ or some other semantically-­similar language such as Java or JavaScript.

What is Recursion?

In English, the word “recur” means to happen again. In computer science, recursion is a technique used to solve a problem in which a function calls itself. It might sound strange, perhaps like a snake eating its own tail, but it actually works!

By calling itself, a recursive function can solve a problem with minimal code. With each self­-referential call, the problem is solved in parts. Eventually, the function will stop calling itself. When the function reaches its base case, it will return a value for every function call. The return values of those function calls will be rolled into one, large return value.

The Recursive Case

In order for a function to be recursive, it needs a special conditional statement called the recursive case. When executed, the recursive case will have the function call itself.

The functions below perform the same task, which is computing n­-factorial (n! = n * (n­1) * (n­2) ** 1, where 0! = 1). Function A uses iteration, or looping, while function B uses recursion.

/**
 * Computes n factorial, n!, using iteration.
 * n! = n * (n - 1) * (n - 2) * ... * 1.
 * Assume that 0! = 1.
 * @param {Integer} n: a nonnegative integer
 * @return {Integer} a positive integer, n factorial.
 */
int A(int n)
{
    // Keep the input size reasonable
    if (n < 0 || n > MAX) n = 0;

    // Iteratively compute n!
    int result = 1;
    while (n > 0)
    {
        result = result * n;
        n = n - 1;
    }
    return result;
}
/**
 * Computes n factorial, n!, using recursion.
 * n! = n * (n - 1) * (n - 2) * ... * 1.
 * Assume that 0! = 1.
 * @param {Integer} n: a nonnegative integer
 * @return {Integer} a positive integer, n factorial.
 */
int B(int n)
{
    // Keep the input size reasonable
    if (n < 0 || n > MAX) n = 0;
    
    // Base Case
    if (n <= 0) return 1;
    
    // Recursive Case
    return n * B(n - 1);
}

The Base Case

Every recursive function requires an exit condition. Otherwise, the function would run forever. We call the exit condition the base case. When the base case evaluates to true, the function will return an actual value instead of calling itself.

The Memory Stack

In order to keep track of all of these function calls, the program uses a structure known as a memory stack. Function calls are pushed onto the stack and then popped off in the opposite order.

Although recursion generally uses less code than iteration, recursion tends to use a lot more memory than iteration does. This is true for imperative languages such as C, C++, Java, and Python. If the recursive chain is too long, the stack will run out of room to store programmatic instructions. When that happens, we get a stack overflow. This would probably crash your computer!

Stack Overflow!

If you would like to crash your computer, try entering a very large term in the following Fibonacci sequence function and try running it on your computer. (The function on the right contains a reference parameter for keeping track of the number of times the function is called. Since you may only return one value in a C++ function, updating a reference parameter is a handy little “cheat” that is a lot like returning two variables).

/**
 * Computes the nth term of the Fibonacci sequence.
 * Fibonacci Sequence: 1, 1, 2, 3, 5, 8, 13, 21, ...
 * @param {Integer} n: the term of the Fibonacci sequence
 * @return {Integer} the nth term of the Fibonacci sequence
 */
int fibonacci(int n)
{
    // Keep the input size reasonable
    if (n < 0 || n > MAX) n = 0;
    
    // Base Case
    if (n <= 0) return 1;
    
    // Recursive Case
    return fibonacci(n - 1) + fibonacci(n - 2);
}
/**
 * Computes the nth term of the Fibonacci sequence.
 * Keeps track of the number of fib function calls.
 * Fibonacci Sequence: 1, 1, 2, 3, 5, 8, 13, 21, ...
 * @param {Integer} n: the term of the Fibonacci sequence
 * @param {Integer &} &callOut;: for tracking call counts
 * @return {Integer} the nth term of the Fibonacci sequence
 */
int fib(int n, int &callCount;)
{
    // Keep the input size reasonable
    if (n < 0 || n > MAX) n = MAX;
    
    // Increment call count for each fib call
    callCount = callCount + 1;
    
    // Base Case
    if (n <= 0) return 1;
    
    // Recursive Call
    return fib(n - 1, callCount) + fib(n - 2, callCount);
}

Unlike the factorial function in the previous example, the Fibonacci sequence function will take up exponentially more memory as the input value increases by just one. Instead of forming a linear stack in the memory, the Fibonacci function will form a binary tree. That is because each recursive case in the Fibonacci function makes two calls.

If you want to compute the zeroth term of the fibonacci sequence, only one function call will be made since you are immediately exiting the function through the base case. If you want to compute the first term of the fibonacci sequence, you will make a total of three calls to the function since you would enter the recursive case, which calls the function twice. If you want to compute the second term in the fibonacci sequence, you would call the function five times.

In general, the number of function calls pushed to the stack for a recursive Fibonacci function call is 2^N + 1, where N represents the count of the Fibonacci term.

A Handy Trick

To save time and memory space, you can create an array that saves the terms of the Fibonacci sequence in order up to some maximum number of terms. You can run a modified version of the Fibonacci function just once and store all the terms of the sequence up to n. Then, whenever you need some term in the fibonacci sequence, you just retrieve it from the array instead of computing the result. Technically, the time it would take to retrieve an element from the array would be time O(1).

/**
 * Creates a map of Fibonacci terms from the 0th to nth term.
 * Fibonacci Sequence: 1, 1, 2, 3, 5, 8, 13, 21, ...
 * @param {Integer} n: the term of the Fibonacci sequence
 * @return {Integer *} a pointer to a dynamic array of Fibonacci terms
 */
int * fibonacciMap(int n)
{
    // Keep the input size reasonable
    if (n < 0 || n > MAX) n = MAX;
    
    // Create a dynamic array of size n
    int * map = new int[n];
    
    // Load the array with Fibonacci terms from 0 to n.
    for (int i = 0; i < n; i++) map[i] = fibonacci(i);
    
    // Return the array
    return map;
}
// As you can see, I like to comment the hell out of my code.
int main()
{ 
    // Variables needed to run the program:
    // - If quit is not zero, the loop will terminate.
    // - n is the number of Fibonacci terms to generate.
    // - i is an arbitray index in the array (between 0 and n-1).
    // - map is a pointer to an integer array.
    int quit = 0, n = 0, i = 0;
    int * map;
    
    // Prompt the user for input (the array size).
    cout << "How many Fibonacci terms do you want in your array? " << flush;
    cin >> n;
    
    // Keep the input size reasonable.
    if (n < 0 || n > MAX) n = MAX;
    
    // Create a dynamic array of n Fibonacci terms.
    cout << "Creating an array of " << n << " numbers..." << endl;
    map = fibonacciMap(n);
    
    // The loop will run indefinitely until the user indicates "quit."
    // Each time the loop runs, the user can retrieve a Fibonacci term in time O(1).
    while (quit == 0)
    {
        // Prompt the user for input (the array index).
        cout << "\n\nEnter a number between 0 and " << n << ": " << flush;
        cin >> i;
        
        // Keep the input size reasonable.
        if (i < 0 || i >= n) i = 0;
        
        // Fetch the ith term of the Fibonacci sequence. Print the result.
        cout << "Fibonacci(" << i << ") = " << map[i] << endl;
        
        // Ask the user whether to continue or quit the program.
        cout << "\nWould you like to try again? (0 = yes, 1 = no): " << flush;
        cin >> quit;
    }
    
    // Free up memory used for the dynamic array.
    delete [] map;
    return 0;
}

References


Categories: sciencetechnologytutorials