Programming Interviews Exposed: Secrets to Landing Your Next Job, 3rd Edition

Understanding Recursion

Recursion is useful for tasks that can be defined in terms of similar subtasks. For example, sort, search, and traversal problems often have simple recursive solutions. A recursive function performs a task in part by calling itself to perform the subtasks. At some point, the function encounters a subtask that it can perform without calling itself. This case, in which the function does not recurse, is called the base case; the former, in which the function calls itself to perform a subtask, is referred to as the recursive case.

NOTE Recursive algorithms have two cases: recursive cases and base cases.

These concepts can be illustrated with a simple and commonly used example: the factorial operator. n! (pronounced “n factorial”) is the product of all integers between n and 1. For example, 4! = 4 × 3 × 2 × 1 = 24. n! can be more formally defined as follows:

n! = n (n – 1)!

0! = 1! = 1

This definition leads easily to a recursive implementation of factorial. The task is to determine the value of n!, and the subtask is to determine the value of (n – 1)! . In the recursive case, when n is greater than 1, the function calls itself to determine the value of (n – 1)! and multiplies that by n. In the base case, when n is 0 or 1, the function simply returns 1. Rendered in code, this looks like the following:

int factorial( int n ){
    if (n > 1) {    /* Recursive case */
        return factorial(n-1) * n;
    } else {        /* Base case */
        return 1;
    }
}

Figure 7-1 illustrates the operation ...