< Free Open Study > |
You must consider several factors in deciding whether to use a recursive solution to a problem. The main issues are the clarity and the efficiency of the solution. Let's focus on efficiency first.
In general, a recursive solution is more costly in terms of both computer time and space. (This is not an absolute decree; it really depends on the computer and the compiler.) A recursive solution usually requires more "overhead" because of the nested recursive function calls, in terms of both time (the function prologues and epilogues must be run for each recursive call) and space (an activation record must be created). A call to a recursive routine may hide many layers of internal recursive calls. For instance, the call to an iterative solution to Factorial involves a single function invocation, causing one activation record to be put on the run-time stack. Invoking the recursive version of Factorial, however, requires N + 1 function calls and N + 1 activation records to be pushed onto the run-time stack, where N represents the formal parameter number. That is, the depth of recursion is O(N). For some problems, the system may not have enough space in the run-time stack to run a recursive solution.
As an extreme example, consider the original version of the recursive function ValueInList. Every time it is invoked, it saves copies of the parameters, including the entire list that is passed as a value parameter. As we search farther and farther in the list, nesting more and more levels of recursive calls, the amount of memory needed for the run-time stack becomes considerable. If the list contains 100 elements and the item we are seeking is not in the list, we end up saving 100 copies of the 100-element list. Eventually we use up so much memory that we may run out of space altogether! This case is an extreme example of one of the "overhead" problems associated with recursive calls. In this particular instance, we might make the list be a reference parameter (something generally not done in value-returning functions) so that every invocation of ValueInList would not generate new copies of the array-based list. (The address of the one and only copy of list would be passed instead.) Even so, the level of recursion is O(N) and the iterative solution is about the same length and just as clear. Thus ValueInList is a poor use of recursion.
Another potential problem is the possibility that a particular recursive solution might be inherently inefficient. Such inefficiency is not a reflection of how we choose to implement the algorithm; rather, it is an indictment of the algorithm itself. For instance, look back at the function Combinations, which we discussed earlier in this chapter. The example of this function illustrated in Figure 7.2, Combinations(4, 3) seems straightforward enough. But consider the execution of Combinations (6, 4), as illustrated in Figure 7.6. The inherent problem with this function is that it calculates the same values over and over. Combinations (4, 3) is calculated in two different places, and Combinations (3 , 2) is calculated in three places, as are Combinations (2, 1) and Combinations (2, 2). It is unlikely that we could solve a combinatorial problem of any large size using this function. The problem is that the program runs "forever"- or until it exhausts the capacity of the computer; it is an exponential-time, O(2^{N}) solution to a linear time, O(N), problem. Although our recursive function is very easy to understand, it was not a practical solution. In such cases, you should seek an iterative solution.
The issue of the clarity of the solution remains an important factor, however. For many problems, a recursive solution is simpler and more natural for the programmer to write. The total amount of work required to solve a problem can be envisioned as an iceberg. By using recursive programming, the applications programmer may limit his or her view to the tip of the iceberg. The system takes care of the great bulk of the work below the surface. Compare, for example, the recursive and nonrecursive versions of the function RevPrint. In the recursive version, the system takes care of the stacking that we had to do explicitly in the nonrecursive function. Thus recursion can act as a tool to help reduce the complexity of a program by hiding some of the implementation details. With the cost of computer time and memory decreasing and the cost of a programmer's time rising, it is worthwhile to use recursive solutions to such problems.
To summarize, it is good to use recursion when:
The depth of recursive calls is relatively "shallow," some fraction of the size of the problem. For instance, the level of recursive calls in the BinarySearch function is O(log_{2}N); it is a good candidate for recursion. The depth of recursive calls in the Factorial and ValueInList routines, however, is O(N).
The recursive version does roughly the same amount of work as the nonrecursive version. You can compare the Big-O approximations to determine this relationship. For instance, we have determined that the O(2^{N}) recursive version of Combinations is a poor use of recursion, compared to an O(N) iterative version. Both the recursive and iterative versions of BinarySearch, however, are O(log_{2}N). BinarySearch is a good example of a recursive function.
The recursive version is shorter and simpler than the nonrecursive solution. By this rule, Factorial and ValueInList represent poor uses of recursive programming. They illustrate how to understand and write recursive functions, but they could more efficiently be written iteratively-without any loss of clarity in the solution. RevPrint is a better use of recursion. Its recursive solution is very simple to understand, and the nonrecursive equivalent is much less elegant.
< Free Open Study > |
Converted from CHM to HTML with chm2web Pro 2.85 (unicode) |