9.5 Recursion

Recursion occurs when a function calls itself directly or indirectly. Some programming functions lend themselves naturally to recursive algorithms, such as the factorial.

A recursive function must follow two basic rules:

• It must have an ending point.

• It must reduce the amount of work to be done each time it's called.

A definition of factorial is:

fact(0) 	= 1 
fact(n) 	= n * fact(n-1) 

In C++, this definition translates to:

int fact(int number) 
{ 
    if (number == 0) 
        return (1); 
    /* else */ 
    return (number * fact(number-1)); 
} 

This satisfies the two rules. First, it has a definite ending point (when number == 0). Second, it reduces the amount of work to be done because computing fact(number-1) is simpler than fact(number).

Factorial is legal only for number >= 0. But what happens if we try to compute fact( -- 3)? The program aborts with a stack overflow or similar message. fact( -- 3) calls fact( -- 4) calls fact( -- 5) and so on. There is no ending point. This is called an infinite recursion error . In this case it was caused by a bad parameter. We should check for that:

int fact(int number) 
{ 
    assert(number >= 0);
    if (number == 0) 
        return (1); 
    /* else */ 
    return (number * fact(number-1)); 
} 

Many things we do iteratively can be done recursively, like summing the elements of an array. You can define a function to add elements m through n of an array as follows:

If you have only one element, the sum is simple.

Otherwise, it is the sum of the first element and the sum of the rest.

In C++ this is:

int sum(const int first, const int last, const int array[], 
        const int array_size) 
{ 
    assert((first > 0) && (first < array_size));
    assert((last > 0) && (last < array_size));

    if (first == last) 
        return (array[first]); 
    /* else */ 
        return (array[first] + sum(first + 1, last, array)); 
} 

For example:

Sum(1 8 3 2) =

1 + Sum(8 3 2) =

8 + Sum(3 2) =

3 + Sum(2) =

2

3 + 2 = 5

8 + 5 = 13

1 + 13 = 14

Answer = 14

This is not to say that this is the clearest or fastest way to sum a loop. In this case, a loop would be much faster. But it does illustrate how recursion can be used to create a nontraditional solution to a problem.