CHAPTER 14 ■ RECURSION- Repetitive mathematical functions, such as a factorial, a sum of digits, the
Fibonacci sequence, and many others - Any problem in which the depth of processing is hard to predict (e.g., processing
files and other data streams) - Certain kinds of searches (such as finding all the instances of a substring within a
string and finding all the instances of a particular data element in a tree structure) - Fractal images (which I'll focus on later in the chapter).
Without further ado, I’ll get to the fun stuff: coding solutions to problems that are a good fit for
recursion.
Calculating the Fibonacci Sequence
The Fibonacci sequence (named after Italian mathematician Leonardo Bigollo, also known as Fibonacci)
is a sequence of numbers consisting of 0, 1, and numbers that are each the sum of the previous two.
Thus, the Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, and so on for as long as one cares
to do the math.
While the Fibonacci sequence can be calculated with a loop, it's commonly used as an example
when folks discuss recursion. I’ll stir up my own code for it:
Listing 14-3. Recursively Calculating the Fibonacci Sequence
package com.bryantcs.examples.fibonacci;
public class Fibonacci {
private int calculate(int length) {
if (length < 0) {
throw new IllegalArgumentException("Input must be 0 or greater");
}
if (length <= 1) {
return length;
} else {
return calculate(length - 1) + calculate(length - 2);
}
}
public static void main(String[] args) {
Fibonacci fibonacci = new Fibonacci();
for (int i = 0; i < 10; i++){
System.out.println(fibonacci.calculate(i));
}
}
}