It's been a long time since I have discussed a coding problem in this blog. So, I am going to start with probably the oldest one of them, how do you find the nth number in a Fibonacci sequence? or how do you find the Fibonacci number in Java? or maybe printing the Fibonacci series. If you are a regular reader of this blog then you might know that I have already discussed both recursive and iterative algorithms for printing the Fibonacci series but never really discussed especially writing a program to return the Nth Fibonacci number in Java. Don't worry the wait is over as in this article, we'll solve this common problem and learn a bit more about problem-solving, recursion, iteration, and some basic algorithm skills.
But, to start with let's get the requirements and problem statement correct:
Fibonacci
Write the fib method to return the Nth term in the Fibonacci series. We start counting from:
fib(0) = 0
fib(1) = 1.
Examples
0 -> 0
6 -> 8
This means the zeroth Fibonacci number is zero and the 6th Fibonacci number is 8, and you have to come up with a formula for calculating the Nth Fibonacci number and code that into Java or your favorite programming language like Python or JavaScript or maybe Scala.
Nth term in Fibonacci Sequence
In order to solve this problem, you first need to know what is a Fibonacci sequence. It's a sequence of integral numbers defined by the following formula:
fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)
If you look at this formula then you know that the nth term in the Fibonacci sequence is equal to some of the previous two Fibonacci numbers. Once you know that, all you need to do is write code, which we'll see in the next section. Fibonacci series is also a good example of Dynamic Programming, a popular technique to solve coding problems.
Dynamic Programming problems are also very common in coding interviews and present great challenges to many developers. They are the toughest problems to solve during coding interviews hence practicing Dynamic programming based problems like the Fibonacci series is a great way to prepare for coding interviews.
If you are preparing for coding interviews then I also suggest you double down on Dynamic Programming and solve problems like Knapsack and the longest common subsequences. If you need a course then I highly recommend the Master the Art of Dynamic Programming course by Ajay Prakash on Udemy. You will learn also things like backtracking which is another good technique to solve coding problems.
And this is how the Fibonacci sequence looks like when you draw it on board:
Recursive Solution for Nth Fibonacci Number
There are two main ways to calculate the Nth term in the Fibonacci series, with recursion, and without recursion. Since the Fibonacci sequence is naturally recursive, it's easier to write and understand a recursive solution, hence, we'll see that first.
Why Fibonacci series is naturally recursive? Well, because, you can divide the problem into sub-problems and can solve it in a similar way. For example, for finding the Nth Fibonacci number, you can find the N-1th Fibonacci number and N-2 Fibonacci number in the same way and combine the result.
But, how do you start? Well, for beginners, I know that starting is the most difficult part, but if you look at the problem statement you will find that you need to write a function, which takes an integer argument (nth term) and returns an integer value, the nth Fibonacci number. This is enough to start with.
Next, for writing a recursive solution, you need to first find a base case, In recursion, the problem is divided into sub-problems until you can solve them and a base case refers to the smallest sub-problem you know how to solve. This technique is also known as the divide and conquer technique. You can further see Data Structures and Algorithms: Deep Dive Using Java course on Udemy to learn more about divide-and-conquer and different techniques to solve algorithms problems.
For the Nth Fibonacci number, we have two base cases fib(0) = 0 and fib(1) = 1 which means we already know how to write this function for two inputs 0 and 1.
Once you solve the problem for the base case, remaining is to know how to solve a bigger problem by combining the solution of a smaller problem that's the recursive code, where a function calls itself.
For the Nth Fibonacci series, the recursive code is
fib(n) = fib(n-1) + fib(n-2);
Done, that's all is required, now our recursive function is ready for testing.
Here is the recursive solution for calculating the Nth Fibonacci number in Java.
import org.junit.Assert;
/** * Fibonacci Write the fib method to return the N’th term. We start counting * from: fib(0) = 0 fib(1) = 1. Examples 0 -> 0 6 -> 8 * */
public class CodingProblem {
public static int fib(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
return fib(n - 1) + fib(n - 2);
}
public static void main(String args[]) {
Assert.assertEquals(0, fib(0));
Assert.assertEquals(1, fib(1));
Assert.assertEquals(1, fib(2));
Assert.assertEquals(2, fib(3));
Assert.assertEquals(3, fib(4));
Assert.assertEquals(5, fib(5));
}
}You can see that our test program is testing the fib() method for different inputs like 0, 1, 2, 3, 4, and 5. You can pass any number to calculate the Nth Fibonacci number. For example, for calculating the 20th Fibonacci number, you can call fib(2).
I haven't printed anything on this program but I have used assert statement, which means if your Fibonacci function is correct then when you run this problem it runs just fine without throwing any error, but if the program is not working as expected then it will return different values and our assert statement will fail, throwing errors in the console.
This is a better approach than printing in the console as by looking at the asserting statement you know that what is expected from function and output is automatically checked by assert statement rather than you checking it manually.
Source: java67
The Tech Platform