RECURSION - Java Programming: From Problem Analysis to Program Design - page 883

In this statement, the first number is 2 , the second number is 3 , and we want to determine
the 5 th Fibonacci number of the sequence. Figure 13-5 traces the execution of the
expression rFibNum(2, 3, 5) . The value returned is 13 , which is the 5th Fibonacci
number of the sequence whose first number is 2 and whose second number is 3 .

return 13

rFibNum(2,3,5)

a 2 b 3 n 5

return rFibNum(2,3,4) + rFibNum(2,3,3)

return 8 return 5

rFibNum(2,3,4) rFibNum(2,3,3)

a 2 b 3 n 4

a 2 b 3 n 3

return rFibNum(2,3,3) + rFibNum(2,3,2) return rFibNum(2,3,2) + rFibNum(2,3,1)

return 2

return 3

return 3

return 5

rFibNum(2,3,3)

rFibNum(2,3,2) rFibNum(2,3,2) rFibNum(2,3,1)

a 2 b 3 n 3 a 2 b 3 n 2 a 2 b 3 n 2 a 2 b 3 n 1

return rFibNum(2,3,2) + rFibNum(2,3,1) return b return b return a

return 3

return 2

rFibNum(2,3,2) rFibNum(2,3,1)

a 2 b 3 n 2 a 2 b 3 n 1

return b return a

FIGURE 13-5 Execution of rFibNum(2, 3, 5)

From Figure 13-5, we can conclude that the recursive version of the program to calculate
a Fibonacci number is not as efficient as the nonrecursive version. In the recursive version,
some values are calculated more than once. For example, to calculate rFibNum(2, 3, 5) ,
the value rFibNum(2, 3, 2) is calculated three times. So a recursive method may be
easier to write, but may not be very efficient. The section Recursion or Iteration?,
presented later in this chapter, discusses the differences between these two alternatives.
The following Java program uses the method rFibNum :
//Recursion: Fibonacci Number

1
3

import java.util.*;

public class FibonacciNumber
{

static Scanner console = new Scanner(System.in);