A recursive function is one that invokes itself.
Many mathematical functions are defined using recursion. We begin with a simple example that illustrates recursion.
The factorial of a number n can be recursively defined as follows:
0! = 1;
n! = n x (n – 1)!; n > 0
How do you find n! for a given n? It is easy to find 1! because you know that 0! is 1 and 1! is 1 x 0!. Assuming you know that (n – 1)!, n! can be obtained immediately using n x (n – 1)!. Thus, the problem of computing n! is reduced to computing (n – 1)!. When computing (n – 1)!, you can apply the same idea recursively until n is reduced to 0.
Let factorial(n) be the function for computing n!. If you call the function with n = 0, it immediately returns the result. The function knows how to solve the simplest case, which is referred to as the base case or the stopping condition. If you call the function with n > 0, it reduces the problem into a subproblem for computing the factorial of n – 1. The subproblem is essentially the same as the original problem but is simpler or smaller than the original. Because the subproblem has the same property as the original, you can call the function with a different argument, which is referred to as a recursive call.
The recursive algorithm for computing factorial(n) can be simply described as follows:
if (n == 0)
return 1;
else
return n * factoria1(n – 1);
A recursive call can result in many more recursive calls, because the function is dividing a subproblem into new subproblems. For a recursive function to terminate, the problem must eventually be reduced to a stopping case. At this point the function returns a result to its caller. The caller then performs a computation and returns the result to its own caller. This process continues until the result is passed back to the original caller. The original problem can now be solved by multiplying n by the result of factorial(n – 1).
Listing 17.1 is a complete program that prompts the user to enter a nonnegative integer and displays the factorial for the number.
Listing I7.I ComputeFactorial.cpp
1 #include <iostream>
2 using namespace std;
3
4 // Return the factorial for a specified index
5 int factorial(int);
6
7 int main()
8 {
9 // Prompt the user to enter an integer
10 cout << “Please enter a non-negative integer: “;
11 int n;
12 cin >> n;
13
14 // Display factorial
15 cout << “Factorial of ” << n << ” is ” << factorial(n);
16
17 return 0;
18 }
19
20 // Return the factorial for a specified index
21 int factorial(int n)
22 {
23 if (n == 0) // Base case
24 return 1;
25 else
26 return n * factorial(n – 1); // Recursive call
27 }
Figure 17.3 When factorial(4) is being executed, the factorial function is called recursively, causing memory space to dynamically change.
Source: Liang Y. Daniel (2013), Introduction to programming with C++, Pearson; 3rd edition.