|
|
|
|
|
|
|
In C++, any function can call another function. A function can even call itself! When a function calls itself, it is making a recursive call. The word recursive means having the characteristic of coming up again, or repeating. In this case, a function call is being repeated by the function itself. Recursion is a powerful technique that can be used in place of iteration (looping). |
|
|
|
|
|
|
|
|
Recursive solutions are generally less efficient than iterative solutions to the same problem. However, some problems lend themselves to simple, elegant, recursive solutions and are exceedingly cumbersome to solve iteratively. Some programming languages, like early versions of FORTRAN, BASIC, and COBOL, do not allow recursion. Other languages are especially oriented to recursive algorithmsLISP is one of these. C++ lets us take our choice: we can implement both iterative and recursive algorithms in C++. |
|
|
|
|
|
|
|
|
Our examples are broken into two groups: problems that use only simple variables and problems that use structured variables. If you are studying recursion before reading Chapter 11 on structured data types, then cover only the first set of examples and leave the rest until you have completed the chapters on structured data types. |
|
|
|
|
|
|
|
|
You may have seen a set of gaily painted Russian dolls that fit inside one another. Inside the first doll is a smaller doll, inside of which is an even smaller doll, inside of which is yet a smaller doll, and so on. A recursive algorithm is like such a set of Russian dolls. It reproduces itself with smaller and smaller examples of itself until a solution is foundthat is, until there are no more dolls. The recursive algorithm is implemented by using a function that makes recursive calls to itself. |
|
|
|
 |
|
|
|
|
Recursive Call A function call in which the function being called is the same as the one making the call. |
|
|
|
|
|
|
|
|
In Chapter 8, we wrote a function named Power, which calculates the result of raising an integer to a positive power. If X is an integer and N is a positive integer, the formula for XN is |
|
|
|
|
|
|
|
|
We could also write this formula as |
|
|
|
|
|
