Definition 12.3.4.
The Fibonacci Number: \(F_N\text{,}\) for \(N \ge 0\text{.}\)
\begin{align}
F_0 \amp= 0,\tag{12.3.1}\\
F_1 \amp= 1,\tag{12.3.2}\\
F_N \amp= F_{N-1} + F_{N-2}\tag{12.3.3}
\end{align}
Section 12.3 Characterizing Recursion
Subsection 12.3.1 Accumulating Recursion
Similar to iteration, we can use a recursive technique to accumulate a result. Let’s consider the simple problem of summing a sequence of integers in a range [begin, end]. Listing 12.3.1 includes two methods to solve this problem: one iterative and one recursive. The
main(…) method tests both on the integer range [1, 10]. Both produce the correct value of 55.// Sums.java
public class Sums {
// Iterative solution to sum a sequence of integers
public static int iterativeSum(int begin, int end) {
int sum = 0; // Init accumulator variable
for (int i=begin; i<=end; i++) { // Generate all integers
sum += i; // Accumulate
}
return sum; // Return result
}
// Recursive solution to sum a sequence of integers
public static int recursiveSum(int begin, int end) {
// Base case when begin > end.
if (begin > end) {
return 0; // Sum is 0
// Recursive case
} else {
// Total sum is current number plus remaining sum
return begin + recursiveSum(begin+1, end);
}
}
// Test
public static void main(String[] args) {
System.out.println( "Iterative sum: " + iterativeSum( 1, 10) );
System.out.println( "Recursive sum: " + recursiveSum( 1, 10) );
}
}
Sums.javajavac Sums.java java Sums Iterative sum: 55 Recursive sum: 55
The
iterativeSum(…) method uses the obvious approach of generating the integers to sum with a for-statement. The sum variable is initialized to 0 and updated each time through the loop before returning the final result after the loop completes all iterations.The
recursiveSum(…) method reformulates the solution technique using a recursive approach. It recasts the solution description as return the first number in the sequence plus the sum of the remaining numbers in the sequence. The base case terminates the recursion when the first parameter, begin, is greater than the second parameter, end, returning a value of 0. The result computed with recursiveSum(…) is the same as iterativeSum(…) when the same initial parameter value is provided.An interesting distinction between these two methods is that the iterative technique accumulates the sum as the integer value in the range increases, whereas the recursive technique accumulates the sum after the base case is reached and each stack frame is popped off the call stack.
Subsection 12.3.2 All-pairs Comparison
Solving problems that require the comparison of element pairs to reach an answer also has a recursive formulation. One simple example is finding an overall maximum of a collection. Listing 12.3.2 includes an iterative and a recursive approach to finding the maximum value in a range of doubles. The
main(…) method tests both methods on an arbitrary array of doubles. Both produce the correct result of 9.8.// Max.java
public class Max {
public static double iterativeMax(double[] arr) {
// Assume max is first element
double max = arr[0];
// Check if any another value is better
for (int i=1; i<arr.length; i++) {
if (arr[i] > max) max = arr[i];
}
// Return max value
return max;
}
public static double recursiveMax(double[] arr) {
// Call method overload starting a index 0
return recursiveMax(arr, 0);
}
public static double recursiveMax(double[] arr, int idx) {
// Base case when only 1 item left in array.
if (idx == arr.length - 1) {
return arr[idx];
// Recursive case
} else {
// Compute max of remaining part of array
double max = recursiveMax(arr, idx+1);
// Compare item at idx with max and return greatest
if (arr[idx] > max) {
return arr[idx];
} else {
return max;
}
}
}
// Test
public static void main(String[] args) {
double[] arr = {2.1, 6.2, 5.9, 3.7, 9.8, 8.0};
System.out.println( iterativeMax(arr) );
System.out.println( recursiveMax(arr) );
}
}
Max.javaThe
iterativeMax(…) method starts by temporarily initializing the max variable to the first value in the array. A loop is used to compare this value to the remaining array values. If a better value is found, exceeding the current maximum, the max variable value is updated. The final value of max is returned as the overall maximum of the array.We use method polymorphism to overload the
recursiveMax(…) method with two implementations. The first overload takes only the double array as a parameter. This is a helper method, which is not recursive. It serves only to help us invoke the second overload, which is a recursive method. This second implementation takes the double array as well as the starting index (idx) in the array from which the maximum should be calculated in the remaining elements. The second overload starts by checking for a base case, which occurs when the index from which to start is the last index of the array. The maximum value of one remaining array element is that array element value, so this value is returned immediately. If idx is not the last index, the method is invoked recursively with the double array and a starting index of idx+1, which computes the the maximum value of the remaining elements in the array, excluding the first. The value returned from this recursive invocation is compared to the element at idx and the maximum of the two is returned. The main(…) method tests both methods on an arbitrary array of doubles. Both produce the correct result of 9.8.Compare
recursiveMax(…) to recursiveSum(…) and note the similarity in the two implementations. In both cases the computation is performed on a smaller version of the problem. The smaller version computes an intermediate result which is used to compute the solution to a larger version of the problem.Subsection 12.3.3 Direct and Indirect Recursion
All recursive methods we’ve explored thus far are examples of direct recursion, which occurs when a recursive method invokes itself directly. It is possible to write a program in which no individual method invokes itself, yet is considered recursive. In the simplest case, one method might invoke a second, and the second invokes the first, and so on. This is an example of indirect recursion. As long as an invoked method traces back to itself, the program is considered recursive.
Listing 12.3.3 is a simple demonstration of indirect recursion. The
left(…) method prints "left" and the right(…) method prints "right." Neither the left(…) nor the right(…) methods are recursive by themselves. But, because left(…) invokes right(…) and right(…) invokes left(…), the program is indirectly recursive. Both methods implement a base case that prints "arrived" and stops the recursion when the step count N reaches 0.// Walk.java
public class Walk {
// A journey of a thousand miles begins with a single step.
public static void main(String[] args) {
left(10); // Take the first step
}
// Left foot
public static void left(int N) {
if (N <= 0) {
System.out.println("arrived");
} else {
System.out.println("left");
right(N-1);
}
}
// Right foot
public static void right(int N) {
if (N <= 0) {
System.out.println("arrived");
} else {
System.out.println("right");
left(N-1);
}
}
}
Walk.javajavac Walk.java java Walk left right left right left right left right left right arrived
Subsection 12.3.4 Multiple Cases and Multiple Invocations
A recursive method must encode at least one base case and one recursive case to work properly. These cases may not always be obvious. For example, a base case of a
void method may simply be a scenario in which program control causes the method to exit because no recursive case condition is satisfied.A recursive method may have more than one base case and/or more than one recursive case. Multi-base and multi-recursive case methods encode multiple conditions that trigger different base cases or multiple conditions that trigger different recursive cases. We’ll refer to this scenario as multi-case recursion.
Another interesting variation on recursion occurs when the block of code that implements a single recursive case invokes multiple recursive methods or the same recursive method multiple times. We’ll refer to this scenario as multiple recursion.
A good example of both multi-case and multiple recursion is a naive implementation of the Fibonacci Number calculation. The mathematical definition of the Fibonacci Number is as follows, where \(F_N\) is the \(N^{th}\) Fibonacci number (see Table 12.3.5). Note how the definition of the Fibonacci number is recursive — it is defined in terms of itself. Other example quantities with definitions that are naturally recursive include Factorial 1 and the Euclidean algorithm 2 for computing Greatest Common Divisor 3 .
| \(F_0\) | \(F_1\) | \(F_2\) | \(F_3\) | \(F_4\) | \(F_5\) | \(F_6\) | \(F_7\) | \(F_8\) | \(F_9\) | \(F_{10}\) |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 |
Let’s explore two ways to calculate Fibonacci number: \(F_N\text{.}\) To help compare these implementations, we’ll measure and report a few metrics, including recursion/iteration count as well as elapsed wall-clock time.
// Fibonacci.java
public class Fibonacci {
public static long count = 0L; // Counter
public static long start = 0L; // Start time
public static long recursiveFibonacci( int N ) {
// Count recursive invocations
count++;
// Two base cases
if (N == 0) {
return 0;
} else if (N == 1) {
return 1;
}
// One base case - multiple recursion
// Return Fibonacci number F[N]
else {
return recursiveFibonacci(N - 1) + recursiveFibonacci(N - 2);
}
}
public static void main(String[] arg) {
int N = 50;
count = 0; // Reset metrics
start = System.currentTimeMillis();
long FN = recursiveFibonacci(N);
System.out.println( "F(" + N + ") = " + FN );
System.out.println("recursion count: " + count
+ ", elapsed time: " + (System.currentTimeMillis() - start) + " ms");
}
}
Fibonacci.java (version 1)
Listing 12.3.6 is a classic implementation of the recursive definition of the Fibonacci number. The program includes the recursive
recursiveFibonacci(…) method. Note that this method has two base cases, one each for the two definitions F[0] = 0 and F[1] = 1. Also note that the recursive case invokes recursiveFibonacci(…) twice. This method demonstrates both multi-case recursion due to its two base cases and multiple recursion, due to it multiple recursive calls in one case.The
Fibonacci class has two static variables used for tracking metrics. The count long will be used to count the number of recursive calls or iterations in a method, and the start long will hold the moment in time a method starts execution measured as milliseconds since 00:00 on January 1, 1970. The value of start is subtracted from a second measurement of milliseconds after a method completes which estimates the method’s execution duration in milliseconds. The built-in static Java utility method System.currentTimeMillis() returns the number of milliseconds that have elapsed since January 1, 1970 at 00:00. It is a convenient tool to use to calculate elapsed time. The first line in recursiveFibonacci(…) increments the count variable so it will hold the total number of times the method was invoked.main() in Listing 12.3.6 resets both count and start and then it invokes recursiveFibonacci(…) with an N parameter of 50. It then prints the computed Fibonacci number, the recursion count, and it computes and prints the elapsed time.In the following console session using a laptop computer, you will see that the Fibonacci number computed was 12586269025, the computation took over 51 seconds to complete, and the number of recursive calls was well over 40 billion!
javac Fibonacci.java java Fibonacci F(50) = 12586269025 recursion count: 40730022147, elapsed time: 51248 ms
Subsection 12.3.5 Dynamic Programming
If you dig in to the details of Fibonacci number calculation, you will see that the naive implementation of the recursive definition is very inefficient. To compute \(F_{10}\) we must compute \(F_9\) and \(F_8\text{.}\) To compute \(F_9\) we first (recursively) compute \(F_8\) and \(F_7\text{.}\) We need \(F_8\) to compute \(F_{10}\text{,}\) but we are computing it for \(F_9\) as well, and then throwing it away! We are forced to recompute \(F_8\) twice: once for \(F_{10}\) and a second time for \(F_9\text{.}\) For \(F_8\) we need \(F_7\) and \(F_6\text{,}\) but again, we are computing \(F_7\) for \(F_8\) and throwing it away, but we need it for \(F_9\text{.}\) The result is a highly inefficient compounding and repetition of the same computation over and over, as you proceed down the chain of dependencies. It certainly seems it would be more efficient to cache intermediate Fibonacci numbers and look them up if they are needed again for subsequent calculations.
When a subproblem in a recursive computation is repeated, it may be worth saving intermediate results and looking them up when needed instead of recomputing them. This idea is at the heart of dynamic programming. With over 40 billion recursions required to calculate \(F_{50}\) recursively, calculating the Fibonacci number appears to be a good candidate for dynamic programming.
With the Fibonacci number, we can do one better. We know that to compute
F[N] we must compute all F[i] for i from 2 up to and including N, so why not just perform that computation from the start. That is, when we want the value of F[N], let’s declare an array named F[] of size N+1, initialize the base case values F[0] = 0 and F[1] = 1, and then use iteration to compute F[2] up to F[N], storing intermediate results in the F[] array, and return F[N] as the result?
Listing 12.3.7 adds a second method to our
Fibonacci.java program named iterativeFibonacci(…) that implements this alternative version of the Fibonacci number calculation. To the main() method we add a second test by calling our new method with an iteration count and a measurement of the elapsed time.// Fibonacci.java
public class Fibonacci {
public static long count = 0L; // Counter
public static long start = 0L; // Start time
public static long recursiveFibonacci( int N ) {
// ...
}
// Iterative Fibonacci number calculation using Dynamic Programming
public static long iterativeFibonacci(int N) {
long[] F = new long[N+1]; // Array for all intermediate values
F[0] = 0L; // Init first two by definition
F[1] = 1L;
for (int i=2; i<=N; i++) { // Calculate remaining
Fibonacci.count++; // Count iterations
F[i] = F[i-1] + F[i-2]; // Fibonacci number calculation
}
return F[N]; // Return F[N]
}
public static void main(String[] arg) {
int N = 50;
count = 0; // Reset metrics
start = System.currentTimeMillis();
long FN = recursiveFibonacci(N);
System.out.println( "F(" + N + ") = " + FN );
System.out.println("recursion count: " + count
+ ", elapsed time: " + (System.currentTimeMillis() - start) + " ms");
count = 0; // Reset metrics
start = System.currentTimeMillis();
FN = iterativeFibonacci(N);
System.out.println( "F(" + N + ") = " + FN );
System.out.println("iteration count: " + count
+ ", elapsed time: " + (System.currentTimeMillis() - start) + " ms");
}
}
Fibonacci.java (version 2)javac Fibonacci.java java Fibonacci F(50) = 12586269025 recursion count: 40730022147, elapsed time: 51264 ms F(50) = 12586269025 iteration count: 49, elapsed time: 0 ms
The elapsed time to execute the
iterativeFibonacci(50) method is less that 1 millisecond with an iteration count of 49. That is much more efficient than the recursive method, which takes more than 51 seconds and 40 billion recursions to complete.When a recursive solution repeats the computation of its subproblems over and over, reformulating a solution using dynamic programming is often a better option.
en.wikipedia.org/wiki/Factorialen.wikipedia.org/wiki/Euclidean_algorithmen.wikipedia.org/wiki/Greatest_common_divisor
