[ Data Structures with Java ] Section 6.3 : Evaluating Recursion

Preface : 
The value of using a recursive method depends upon the problem. Sometimes, recursion is not appropriate, because a far more efficient iterative version exists. For some problem, like the Towers of Hanoi, a recursive solution is elegant and easier to code than the corresponding iterative solution. In this section, we use the Fibonacci numbers to compare and contrast iterative and recursive methods. Our discussion will outline some of the advantages and disadvantages of recursion. 
Fibonacci numbers are sequence of integers beginning at position n=0. By definition, the first two terms are 0 and 1. Each subsequent term, beginning at n=2 is the sum of the two previous terms. For instance, fib(2) = fib(0) + fib(1) = 0+1=1. 
The term fib(n) in the Fibonacci sequence can be evaluated recursive. The terms fib(0) and fib(1) are 0 and 1, respectively. From that point on, each term is the sum of previous two terms : 
 

Fibonacci Methods : 
In an effort to evaluate recursion, we present recursive and iterative version of methods that evaluate a Fibonacci number. An analysis of the algorithms provides the Big-o running time of the methods. 
- The Recursive method fib() 
The recursive method fib() takes a single argument n and returns the Fibonacci number fib(n) : 

- 函式 fib(n) 範例代碼 :

view plaincopy to clipboardprint?

1. public static int fib(int n) {  
2.     if(n<2) {  
3.         return n;  
4.     } else {  
5.         return fib(n-1)+fib(n-2);  
6.     }  
7. }  

The implementation of fib() is a simple and straightforward translation of the recursive definition for terms in the Fibonacci sequence. The execution of the method is far from straightforward. Computing fib(5) requires 15 recursive calls. Below figure show a hierarchy tree of nodes representing the calls to fib() for n = 5,4,3,2,1 and 0. For the recursive step, a node spawn two other nodes corresponding to the statement fib(n-1) and fib(n-2). Nodes at the bottom of the tree identify stopping conditions : 
 

The fib() method makes multiple calls to itself with the same argument. This creates enormous redundancy. The evaluation of fib(5) computes fib(3) two times and fib(1) five times, the total number of recursive calls to evaluate nth Fibonacci number is directly related to the value fib(n). Let numCall(n) be the number of method calls required to evaluate fib(n). The sample code as below : 

- 函式 numCall() 範例代碼 :

view plaincopy to clipboardprint?

1. public static int myNumCall(int n) {  
2.     if(n<2) {  
3.         return 1;  
4.     } else if(n==2){  
5.         return 3;  
6.     } else {  
7.         return numCall(n-1)+numCall(n-2)+1;  
8.     }  
9. }  

或者套用公式 numCall(n) = 2 * fib(n+1) - 1, For instance : 

For fib(5) : numCall(5) = 2*fib(6) - 1 = 2*8-1 = 15 (Need 15 times recursive calls)
For fib(35) : numCall(35) = 2*fib(36)-1 = 29,860,705

Because the Fibonacci numbers get large very quickly, it is clean that their recursive evaluation is not efficient. In fact, the recursive computation has exponential running time. 

- The Iterative Method fibiter() 
A iterative version of the method fib() uses a simple loop and two integer variables, oneback and twoback, that maintain a record of the last two Fibonacci numbers. Each iteration of the loop undates these variables. The iterative version has the name fibIter() : 

- 函式 fibIter() 範例代碼 :

view plaincopy to clipboardprint?

1. public static int fibIter(int n) {  
2.     int oneback=1, twoback=0, current=0;  
3.     if(n<2) {  
4.         return n;  
5.     } else {  
6.         for(int i=2; i<=n; i++) {  
7.             current = oneback + twoback;  
8.             twoback = oneback;  
9.             oneback = current;  
10.         }  
11.         return current;  
12.     }  
13. }  

The running time of iterative version is O(n). For n=35, the iterative form requires 34 additions, whereas the recursive method requires 29,860,703 method calls. The Fibonacci example illustrate a cruel irony for recursion. Often, recursion simplifies both the algorithm design and coding, only fail for lack of runtime efficiency. Below test show the exactly spending time while calculate Fibonacci sequence with n=20 : 

- Running time efficiency testing :

view plaincopy to clipboardprint?

1. public static void main(String[] args) {  
2.     long st = System.currentTimeMillis();  
3.     int rst = fib(35);  
4.     long wt = System.currentTimeMillis() - st;  
5.     System.out.println("Recursive version take time "+wt+" ms.("+rst+")");  
6.     st = System.currentTimeMillis();  
7.     rst = fibIter(35);  
8.     wt = System.currentTimeMillis() - st;  
9.     System.out.println("Iterative version take time "+wt+"ms.("+rst+")");  
10. }  

Output : 

Recursive version take time 100 ms.(9227465)
Iterative version take time 0ms.(9227465) // Now you know how poor running time-efficiency for recursive version of Fibonacci.

Criteria for Using Recursion : 
The example of Fibonacci numbers should alert you to potential problems with recursion. With the overhead of method calls, a simple recursive method can significantly deteriorate runtime performance. In the case of the Fibonacci numbers, use the O(n) iterative solution in preference to the recursive version. 
With the above warnings noted, recursion remains an important design and programming tool. Main algorithms naturally lead themselves to a recursive implementation that distinguishes the stopping conditions and recursive steps. The Towers of Hanoi is a good example. In Chapter 29, we use recursive to solve the 8-Queens problem. This is an elegant algorithm that demonstrates how recursion can solve difficult problems. Equivalent iterative algorithms would be more difficult to devise. Also it allows the programmer to manager the key components in the algorithm while hiding some of the complex implementation details. There is no simple rule describing when to use recursion. Use it when it enhance the algorithm design and provides a method implementation that runs with reasonable space and time efficiency.