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

7.1. Understanding Recursion

Recursion is most 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 routine performs a task in part by calling itself to perform the subtasks. At some point, the routine encounters a subtask that it can perform without calling itself. This case, in which the routine does not recurse, is called the base case; the former, in which the routine calls itself to perform a subtask, is referred to as the recursive case.

Recursive algorithms have two types of 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 essentially 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 determining the value of n!, and the subtask is determining the value of (n – 1)! In the recursive case, when n is greater than 1, the routine 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 routine simply returns 1. Rendered in any C-like language, 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 ...