How to find Nth Fibonacci Number in Java - Coding Problem with Solution

It's been a long time since I have discussed a coding problem in this blog. So, I am going to start with the 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 algorithm for printing 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 N'th term in the Fibonacci series. We start counting from:

fib(0) = 0
fib(1) = 1.

Examples
0 -> 0
6 -> 8

Which 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 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 nth term in the Fibonacci sequence is equal to some of the previous two Fibonacci number. Once you know that, all you need to do is write code, which we'll see in the next section.

And this is how the Fibonacci sequence looks like when you draw it on board:

Nth Fibonacci Number in Java - Coding Problem with Solution




Recursive Solution for Nth Fibonacci Number

There are two main ways to calculate Nth term in 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 Nth Fibonacci number, you can find 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 integer argument (nth term) and return 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 base case refers to the smallest sub-problem you know how to solve. This technique is also known as divide and conquer technique. You can 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.

 Nth Fibonacci Number in Java - Coding Problem with Solution


For 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 input 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 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 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 console.

This is a better approach than printing in the console as by looking at asserting statement you know that what is expected from function and output is automatically checked by assert statement rather than you checking it manually.

That's all about how to calculate Nth Fibonacci number in Java. As I have said, you can solve the problem using both recursion and iteration and we have looked at recursion first, as it's easier to write and understand. I'll explain the iterative code in the next article, till then you can try and run this program.

If you want, you can also find a problem in the above algorithms which is key for improvement. You can also calculate the Big(O) time complexity and how you can reduce that. If you can't wait here are some resource for further learning:

Further Learning
Algorithms and Data Structures - Part 1 and 2 
Data Structure and Algorithms Analysis - Job Interview
Data Structures and Algorithms: Deep Dive Using Java
From 0 to 1: Data Structures & Algorithms in Java
Cracking the Coding Interview - 189 Questions and Solutions


Other Data Structure and Algorithms  You may like
  • 5 Books to Learn Data Structure and Algorithms in-depth (books
  • How to reverse an array in Java? (solution)
  • 75+ Coding Interview Questions for Programmers (questions)
  • How to remove duplicate elements from the array in Java? (solution)
  • How to implement a recursive preorder algorithm in Java? (solution)
  • 50+ Data Structure and Algorithms Problems from Interviews (list)
  • 10 (Free) Data Structure Courses for Programmers (free courses)
  • How to print leaf nodes of a binary tree without recursion? (solution)
  • Recursive Post Order traversal Algorithm (solution)
  • 10 DS, Algo, and SQL courses to Crack Coding Interview  (courses)
  • Iterative PreOrder traversal in a binary tree (solution)
  • How to count the number of leaf nodes in a given binary tree in Java? (solution)
  • Recursive InOrder traversal Algorithm (solution)
  • 10 Free Data Structure and Algorithm Courses for Programmers (courses)
  • 100+ Data Structure Coding Problems from Interviews (questions)

Thanks for reading this article so far. If you like this article then please share with your friends and colleagues. If you have any issues, please drop a note.

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check the Easy to Advanced Data Structures course on Udemy. It's authored by a Google Software Engineer and Algorithm expert and its completely free of cost.

No comments:

Post a Comment