Practical C Programming, 3rd Edition

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.