How to Find Nth Fibonacci Number in Java [Solved] - Example Tutorial

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:

Find the Nth Number in Fibonacci Series

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

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 these Java data structure and algorithms courses 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.

That's all about how to calculate the 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 resources for further learning:

Other Data Structure and Algorithms  articles 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)
• 6 Dynamic Programming Courses for Programmers (best courses)
• 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 Nth Fibonacci solution in Java then please share it 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 free Data Structures in Java for Beginners course on Udemy. It's completely free of cost.

Lastly, what is your favorite Java programming exercise? Palindrom, Prime Number, Binary Search, or this one?  Do let me know in comments.