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

Suppose that we want to determine the following:
1.

rFibNum(2, 5, 4)
Here, a = 2 , b = 5 , and n = 4 . That is, we want to determine the fourth
Fibonacci number of the sequence whose first number is 2 and whose
second number is 5 . Because n is 4 > 2 :

rFibNum(2, 5, 4) = rFibNum(2, 5, 3) + rFibNum(2, 5, 2)
Next, we determine rFibNum(2, 5, 3) and rFibNum(2, 5, 2) . Let's
first determine rFibNum(2, 5, 3) . Here, a = 2 , b = 5 , and n is 3 .
Because n is 3 :
1.a. rFibNum(2, 5, 3) = rFibNum(2, 5, 2) + rFibNum(2, 5, 1)

This statement requires that we determine rFibNum(2, 5, 2) and
rFibNum(2, 5, 1) .In rFibNum(2, 5, 2) , a = 2 , b = 5 ,and n = 2 .
Therefore, from the definition given in Equation 13-3, it follows that:
1.a.1. rFibNum(2, 5, 2) = 5

To find rFibNum(2, 5, 1) , note that a = 2 , b = 5 , and n = 1 .
Therefore, by the definition given in Equation 13-3:

1.a.2. rFibNum(2, 5, 1) = 2

We substitute the values of rFibNum(2, 5, 2) and rFibNum(2, 5, 1)
into (1.a) to get:
rFibNum(2, 5, 3) = 5 + 2 = 7

Next, we determine rFibNum(2, 5, 2) . As in (1.a.1), rFibNum(2, 5,
2) = 5 . We can substitute the values of rFibNum(2, 5, 3) and
rFibNum(2, 5, 2) into (1) to get:

rFibNum(2, 5, 4) = 7 + 5 = 12
The following recursive method implements this algorithm:
public static int rFibNum( int a, int b, int n)
{

if (n == 1)
return a;
else if (n == 2)
return b;
else
return rFibNum(a, b, n - 1) + rFibNum(a, b, n - 2);

}
Let's trace the execution of the following statement:
System.out.println(rFibNum(2, 3, 5));