1. Overview
In this tutorial, we’ll look at the Fibonacci series.
Specifically, we’ll implement three ways to calculate the nth term of the Fibonacci series, the last one being a constant-time solution.
2. Fibonacci Series
The Fibonacci series is a series of numbers in which each term is the sum of the two preceding terms. It’s first two terms are 0 and 1.
For example, the first 11 terms of the series are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and 55.
In mathematical terms, the sequence Sn of the Fibonacci numbers is defined by the recurrence relation:
S(n) = S(n-1) + S(n-2), with S(0) = 0 and S(1) = 1
Now, let’s look at how to calculate the nth term of the Fibonacci series. The three methods we’ll be focusing on are recursive, iterative, and using Binet’s formula.
2.1. Recursive Method
For our first solution, let’s simply express the recurrence relation directly in Java:
public static int nthFibonacciTerm(int n) {
if (n == 1 || n == 0) {
return n;
}
return nthFibonacciTerm(n-1) + nthFibonacciTerm(n-2);
}
As we can see, we check whether n is equal to 0 or 1. If it true, then we return that value. In any other case, we recursively call the function to calculate the (n-1)th term and (n-2)th term and return their sum.
Although the recursive method is simple to implement, we see that this method does a lot of repeated calculations. For instance, in order to calculate the 6th term, we make calls to calculate the 5th and the 4th term. Moreover, the call to calculate the 5th term makes a call to calculate the 4th term again. Because of this fact, the recursive method does a lot of redundant work.
As it turns out, this makes its time complexity exponential; O(Φn) to be exact.
2.2. Iterative Method
In the iterative method, we can avoid the repeated calculations done in the recursive method. Instead, we calculate the terms of the series and store the previous two terms to calculate the next.
Let’s take a look at its implementation:
public static int nthFibonacciTerm(int n) {
if(n == 0 || n == 1) {
return n;
}
int n0 = 0, n1 = 1;
int tempNthTerm;
for (int i = 2; i <= n; i++) {
tempNthTerm = n0 + n1;
n0 = n1;
n1 = tempNthTerm;
}
return n1;
}
Firstly, we check whether the term to be calculated is the 0th term or 1st term. If that is the case, we return the initial values. Otherwise, we compute the 2nd term using n0 and n1. Then, we modify the values of n0 and n1 variables to store the 1st term and 2nd term respectively. We keep on iterating until we have calculated the required term.
The iterative method avoids repetitive work by storing the last two Fibonacci terms in variables. The time complexity and space complexity of the iterative method is O(n) and O(1) respectively.
2.3. Binet’s Formula
We have only defined the nth Fibonacci number in terms of the two before it. Now, we will look at Binet’s formula to calculate the nth Fibonacci number in constant time.
The Fibonacci terms maintain a ratio called golden ratio denoted by Φ, the Greek character pronounced ‘phi’**.**
First, let’s look at how the golden ratio is calculated:
Φ = ( 1 + √5 )/2 = 1.6180339887...
Now, let’s look at Binet’s formula:
Sn = Φⁿ–(– Φ⁻ⁿ)/√5
Actually, this means that we should be able to get the nth Fibonacci number with just some arithmetic.
Let’s express this in Java:
public static int nthFibonacciTerm(int n) {
double squareRootOf5 = Math.sqrt(5);
double phi = (1 + squareRootOf5)/2;
int nthTerm = (int) ((Math.pow(phi, n) - Math.pow(-phi, -n))/squareRootOf5);
return nthTerm;
}
We first calculate the squareRootof5 and phi and store them in variables. Later, we apply Binet’s formula to get the required term.
Since we’re dealing with irrational numbers here, we’ll only get an approximation. Consequently, we’ll need to hold onto more decimal places for higher Fibonacci numbers to account for round-off error.
We see that the above method calculates the nth Fibonacci term in constant time, or O(1).
3. Conclusion
In this brief article, we looked at the Fibonacci series. We looked at a recursive and an iterative solution. Then, we applied Binet’s formula to create a constant-time solution.
As always, the full source code of the working examples is available over on GitHub.