If this is the way that you choose to solve factorials, then your friend will employ the same method. To compute 9!, he or she will call up yet another friend, asking for the value of 8!. That friend will call up yet another friend for 7!, and this process will continue until somebody is asked for the value of 1!.
When asked to compute 1!, there is no need to ask for help. The answer is 1.
This idea can be used in computer programs. A function can call itself. When it does, it really is calling a clone of itself. As many clones as are needed will be created (up to the capacity of the computer to store them).
For example, here is a definition (and contract) for a function that computes factorials.
//////////////////////////////// // factorial // //////////////////////////////// // factorial(n) returns n!. // //////////////////////////////// long factorial(long n) { if(n == 1) return 1; else return factorial(n-1) * n; }The factorial function calls itself. This is called recursion. When factorial calls factorial, it is said to do a recursive call.
Asking a friend to compute x^(n-1) can be done in the function implementation by letting the function call itself. Remember that what it really does is call a copy of itself. Here is the power function.
///////////////////////////////////////////// // power // ///////////////////////////////////////////// // power(x,n) returns x to the n-th power. // // // // Requirement: n must be a positive // // integer. // ///////////////////////////////////////////// double power(double x, int n) { if(n == 1) return x; else return x * power(x, n-1); }
This improvement is very easy to add to the recursive implementation of the power function. Notice that the contract does not change, since we are computing the same function, but doing so more efficiently.
///////////////////////////////////////////// // power // ///////////////////////////////////////////// // power(x,n) returns x to the n-th power. // // // // Requirement: n must be a positive // // integer. // ///////////////////////////////////////////// double power(double x, int n) { if(n == 1) return x; else if(n % 2 == 0) { double p = power(x,n/2); return p*p; } else return x * power(x, n-1); }It might be useful to see whether you can implement the same thing using a loop instead of recursion. It can be done, but it is much more difficult.
input | output | |
7 | 15 | |
9 | 4 | |
4 | 9 | |
15 | 7 | |
0 |
There is a simple case where you don't need to ask for help. If the input contains only a 0, then you don't need to print anything at all. These ideas are implemented in the following function definition.
//////////////////////////////////////////////////// // PrintReverse // //////////////////////////////////////////////////// // PrintReverse() reads numbers up to a 0, and // // prints the numbers read in reverse order, // // one number per line, excluding the 0. For // // example if the input is a shown below, the // // output would be as shown. // // // // input output // // ----- ------ // // 7 15 // // 9 4 // // 4 9 // // 15 7 // // 0 // //////////////////////////////////////////////////// void PrintReverse() { int x; cin >> x; if(x != 0) { PrintReverse(); cout << x << endl; } }
A recursive function generally starts with an if statement, which determines whether the current case is so simple that no recursion is required, or is sufficiently complex that recursion should be used. Look at the example. They all do such an if statement.
In some function definitions, there are more than two cases. The improved power function is an example.