The C language supports a capability known as recursive function. Recursive functions can be effectively used to succinctly and efficiently solve problems. They are commonly used in applications in which the solution to a problem can be expressed in terms of successively applying the same solution to subsets of the problem. One example might be in the evaluation of expressions containing nested sets of parenthesized expressions. Other common applications involve the searching and sorting of data structures called trees and lists.
Recursive functions are most commonly illustrated by an example that calculates the factorial of a number. Recall that the factorial of a positive integer n, written n!, is simply the product of the successive integers 1 through n. The factorial of 0 is a special case and is defined equal to 1. So 5! is calculated as follows:
5! = 5 x 4 x 3 x 2 x 1
= 120
and
6! = 6 x 5 x 4 x 3 x 2 x 1
= 720
Comparing the calculation of 6! to the calculation of 5!, observe that the former is equal to 6 times the latter; that is, 6! = 6 x 5!. In the general case, the factorial of any positive integer n greater than zero is equal to n multiplied by the factorial of n – 1:
n! = n x (n – 1)!
The expression of the value of n! in terms of the value of (n-1)! is called a recursive defi- nition because the definition of the value of a factorial is based on the value of another factorial. In fact, you can develop a function that calculates the factorial of an integer n according to this recursive definition. Such a function is illustrated in Program 8.16.
Program 8.16 Calculating Factorials Recursively
#include <stdio.h>
int main (void)
{
unsigned int j;
unsigned long int factorial (unsigned int n);
for ( j = 0; j < 11; ++j )
printf (“%2u! = %lu\n”, j, factorial (j));
return 0;
}
// Recursive function to calculate the factorial of a positive integer
unsigned long int factorial (unsigned int n)
{
unsigned long int result;
if ( n == 0 )
result = 1;
else
result = n * factorial (n – 1);
return result;
}
Program 8.16 Output
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
The fact that the factorial function includes a call to itself makes this function recur- sive. When the function is called to calculate the factorial of 3, the value of the formal parameter n is set to 3. Because this value is not zero, the following program statement
result = n * factorial (n – 1);
is executed, which, given the value of n, is evaluated as
result = 3 * factorial (2);
This expression specifies that the factorial function is to be called, this time to calcu- late the factorial of 2. Therefore, the multiplication of 3 by this value is left pending while factorial (2) is calculated.
Even though you are again calling the same function, you should conceptualize this as a call to a separate function. Each time any function is called in C—be it recursive or not—the function gets its own set of local variables and formal parameters with which to work. Therefore, the local variable result and the formal parameter n that exist when the factorial function is called to calculate the factorial of 3 are distinct from the vari- able result and the parameter n when the function is called to calculate the factorial of 2.
With the value of n equal to 2, the factorial function executes the statement
result = n * factorial (n – 1);
which is evaluated as
result = 2 * factorial (1);
Once again, the multiplication of 2 by the factorial of 1 is left pending while the factorial function is called to calculate the factorial of 1.
With the value of n equal to 1, the factorial function once again executes the state- ment
result = n * factorial (n – 1);
which is evaluated as
result = 1 * factorial (0);
When the factorial function is called to calculate the factorial of 0, the function sets the value of result to 1 and returns, thus initiating the evaluation of all of the pending expressions. So the value of factorial (0), or 1, is returned to the calling function (which happens to be the factorial function), multiplied by 1, and assigned to result. This value of 1, which represents the value of factorial (1), is then returned back to the calling function (once again the factorial function) where it is multiplied by 2, stored into result, and returned as the value of factorial (2). Finally, the returned value of 2 is multiplied by 3, thus completing the pending calculation of factorial (3). The resulting value of 6 is returned as the final result of the call to the factorial function, to be displayed by the printf function.
In summary, the sequence of operations that is performed in the evaluation of factorial (3) can be conceptualized as follows:
factorial (3) = 3 * factorial (2)
= 3 * 2 * factorial (1)
= 3 * 2 * 1 * factorial (0)
= 3 * 2 * 1 * 1
= 6
It might be a good idea for you to trace through the operation of the factorial func- tion with a pencil and paper. Assume that the function is initially called to calculate the factorial of 4. List the values of n and result at each call to the factorial function.
This discussion concludes this chapter on functions and variables. The program func-tion is a powerful tool in the C programming language. Enough cannot be said about the critical importance of structuring a program in terms of small, well-defined func- tions. Functions are used heavily throughout the remainder of this book. At this point, you should review any topics covered in this chapter that still seem unclear. Working through the following exercises will also help reinforce the topics that have been dis- cussed.
Source: Kochan Stephen G. (2004), Programming in C: A Complete Introduction to the C Programming Language, Sams; Subsequent edition.