Fibonacci series in Java – Letstacle

Fibonacci series in Java – Letstacle 0 HomeLive Programming HelpComputer Science Homework HelpPython Homework HelpPython Homework SolvedJava Homework HelpJava Homework solvedC++ Homework HelpR Homework HelpPHP Homework HelpHTML Homework HelpJavaScript Homework HelpSQL Homework HelpDo My Programming HomeworkAndroid Assignment HelpAboutHow it WorksCareersArticlesJavaJavaScriptPythonC++hackerrank solutionsHTMLMathsDatabase AcademyPython Tutor ReviewsRecent ReviewsLeave a Review PaymentFAQs Contact / Get Help Fibonacci series in Java September 8, 2021 8 Comments You shall find a lot of articles on the Fibonacci series in Java out there on the internet. Then why read this one? In this article, we are going to learn how to print the Fibonacci series and improve the algorithm step by step.We shall start with recursion improve with memoization and finally implement a top-down dynamic approach. Lastly, we shall see how mathematics makes our lives easy!What is the Fibonacci series? In this series, every term is the sum of the previous 2 terms. So, the nth term is equal to (n-1)th term plus (n-2)th term.The first 2 terms are defined as 0 and 1. From this, we can keep building the Fibonacci series to any number of terms using this simple formula. For instance, the series 1 1 2 3 5 8 13 21 is a Fibonacci series with 8 elements.Fibonacci Series in Java using RecursionIn a recursive program, we repetitively solve sub-problems which leads to the final solution. Let’s write a Java program to calculate the nth Fibonacci term using recursion.Codepublic class FibRec { static int fibonacci(int n) { if(n <= 1) return n; return fibonacci(n-1)+fibonacci(n-2); } public static void main(String[] args) { System.out.println(fibonacci(8)); } }Output21The above code returns the 8th Fibonacci term.For every value of n, the above formula is used to calculate results.For example, when n was 4, fibonacci(3) and fibonacci(2) are calculated and added. The minimum value of n for which the formula is used is 2. Below that we return n itself.This is our base case. For n=1 we return 1. For n=0 we return 0. Therefore, if n is less or equal to 1 we return n itself.Fibonacci using MemoizationIn the above solution, we can notice that fib(2) has been calculated multiple times.Well, the Fibonacci series is an ideal example of overlapping sub-problems.So, we can improve the above algorithm using memoization. In this technique, we create a lookup table where we store the calculated result for every value from 0 to n. In this way, we don’t have to solve the same problems repeatedly.Codepublic class FibMem { static int lookup[]; static int fibonacci(int n) { if(lookup[n] != -1) return lookup[n]; if(n <= 1) { lookup[n] = n; return n; } lookup[n] = fibonacci(n-1)+fibonacci(n-2); return lookup[n]; } public static void main(String[] args) { int n = 6; lookup = new int[n+1]; for(int i=0; i

Leave a comment

Your email address will not be published.