Previous Section
 < Free Open Study > 
Next Section


7.1 What Is Recursion?

You may have seen a set of gaily painted Russian dolls that fit inside one another. Inside the larger 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 definition is like such a set of Russian dolls. It reproduces itself in the form of smaller and smaller versions of itself until a version is reached that can no longer be subdivided-that is, until the smallest doll is reached. The recursive algorithm is implemented by using a function that makes recursive calls to itself, which is analogous to taking the dolls apart one by one. The solution often depends on passing back larger and larger subsolutions from the recursive calls, which is analogous to putting the dolls back together again.

Recursive call A function call in which the function being called is the same as the one making the call

Click To expand

In C++, any function can invoke another function. A function can even invoke itself! When a function invokes itself, it makes a recursive call. The word recursive means "having the characteristic of coming up again, or repeating." In this case, a function invocation is repeated by the function itself. This type of recursion is sometimes called direct recursion, because the function directly calls itself. All of the examples in this chapter involve direct recursion. Indirect recursion occurs when function A calls function B, and function B calls function A; the chain of function calls could be even longer, but if it eventually leads back to function A, then it involves indirect recursion.

Direct recursion When a function directly calls itself

Indirect recursion When a chain of two or more function calls returns to the function that originated the chain

Recursion is a powerful programming technique, but you must be careful when using it. Recursive solutions can be less efficient than iterative solutions to the same problem. In fact, some of the examples used in this chapter are better suited to iterative methods. Nevertheless, many problems lend themselves to simple, elegant, recursive solutions and are exceedingly cumbersome to solve iteratively. Some programming languages, such as early versions of FORTRAN, BASIC, and COBOL, do not allow recursion. Other languages are especially oriented to recursive approaches-LISP, for example. C++ lets us make a choice; we can implement both iterative and recursive algorithms in C++.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)