Fibonacci Series In Java With Recursion - Full Tutorial (FAST Algorithm)

Full tutorial for generating numbers in the Fibonacci sequence in Java, using Recursion!
The Fibonacci sequence (series) is often one of the first Java assignments teaching recursion for beginners.
The basic Fibonacci algorithm is very simple, but works extremely slowly. This improves on that Fibonacci algorithm and generates Fibonacci numbers FAST.
We'll walk through the entire Fibonacci series algorithm step by step, and walk through coding the entire thing in Java.
Learn a great Java Fibonacci sequence program by watching the whole algorithm being described and coded.
Learn or improve your Java by watching it being coded live!
Hi, I'm John! I'm a Lead Java Software Engineer and I've been in the programming industry for more than a decade. I love sharing what I've learned over the years in a way that's understandable for all levels of Java learners.
Let me know what else you'd like to see!
Links to any stuff in this description are affiliate links, so if you buy a product through those links I may earn a small commission.
📕 THE best book to learn Java, Effective Java by Joshua Bloch
amzn.to/36AfdUu
📕 One of my favorite programming books, Clean Code by Robert Martin
amzn.to/3GTPVhf
🎧 Or get the audio version of Clean Code for FREE here with an Audible free trial
www.audibletria...
🖥️Standing desk brand I use for recording (get a code for $30 off through this link!)
bit.ly/3QPNGko
📹Phone I use for recording:
amzn.to/3HepYJu
🎙️Microphone I use (classy, I know):
amzn.to/3AYGdbz
Donate with PayPal (Thank you so much!)
www.paypal.com...
☕Complete Java course:
codingwithjohn...
codingwithjohn...

[@Sami67995]

Everyone can be a java programmer but to be a java teacher It takes a lot of effort Thank you John

[@myguy2656]

Can Someone explain how he gets f(6) = f(6-1) + f(6-2) =8? Because when i add it up i get 5+4=9…

[@jonsantos6056]

Very useful for learning recursion especially if dealing with slow speed computations. *Tip: Primitives can never be assigned 'null', instead, they will default to 0.*

[@asankasiriwardena3383]

a fairly easy implementation without recursion, int n = 10; int[] arr = new int[n]; arr[1] = 1; for (int i = 2; i < n; i++) { arr[i] = arr[i - 1] + arr [i -2]; } System.out.println(Arrays.toString(arr));

[@MrDarshD]

Well explained and coded! Loved the way you described small details like why we do n-1 and n+1!! Also appreciate the bonus at the end with all numbers printed. Thank you so much John!

[@dianamirlanbekova5894]

Hi John, why 0 is not being counted as 1st number in fibonacci sequence? If I type 3, it results 0 1 1 2. It should've print out 0 1 2

[@elmehditalbi8972]

Hello John, I'm asking once again if generics can be done in a video explained by you. Please I'm having trouble with the content, and your explanation is magnificent !

[@CodingWithJohn]

I do plan to have a generics video sometime, it just depends on if I have enough time during any given week to make the video on that particular topic. Some take quite a bit long to put together than others!

[@elmehditalbi8972]

@@CodingWithJohn thank you so much

[@joshlicew6691]

Bro generics are so easy. Lets say for example you have a ArrayList, I cant pass a string, or a double, or any other type other than a Integer. NOW with a generics class you replace where you would put the type to a letter, it can be any letter, but usually E. So now im going to say ArrayList. Now the type is a generics type which means i can now say ArrayList, or Arraylist, its just like think of it as a variable. It chances based on the use

[@timothymattnew]

@@CodingWithJohn yep, the video is very needed)

[@lucasteixeira1631]

he made it! Generics In Java - Full Simple Tutorial kzbin.info/www/bejne/gWLMpmShjdCJpaM

[@VGS_7]

what about this solution? public static void printFibo(int a , int b , int n ){ if(n==0) return ; s.o.p(a+" "); printfibo(b , a+b , n-1); }

[@Avarn388]

You’ve earned my sub. I’ve been working out a similar problem with Python so your refresher was really helpful. I will definitely utilize this for my assignment.

[@Sixerking88]

But what if we take first fibonacii term = 0 Here you take zero fibonacii term = 0

[@emerson3070]

6:12 You remind me of the Dean from 'Community' the show lol :)

[@MTB_Bay_Area]

Clear, and to the point like all your videos. Thank you for helping.

[@07Flash11MRC]

Great video. Can you do Bernoulli Numbers next, please?

[@pulumathisireesha7652]

sir , after a certain limit why some are -ve and some are positive..bcz after 92 i.e, after it cross the limit of LONG size, all should be negative right. but why some are positive?

[@jelmerterburg3588]

This happens because overflow can result in any number within the signed 64 bit range, both positive and negative. Adding two large negative numbers, for example, can easily overflow to a positive number. In the case of the Fibonacci sequence, things will start to bounce around pretty wildly as soon as the first negative number appears.

[@Guide4Ever]

This was one of the best and well delivered tutorials! Kudos to you!

[@uncopino]

i was playing around with recursion yesterday and i made a fibonacci recursive algorithm as fast as yours but using no static variables. i just made the method return an array of 2 longs (the last two values) in order to avoid the double recursive call. i can post the code if anyone’s interested

[@CodingWithJohn]

Go for it!

[@uncopino]

@@CodingWithJohn it should throw an IllegalArgumentException when given n < 2, i know. anyway, here it is: public static long[] last2fibonacciValues(long n) { long[] last2values = {0, 1}; if(n

[@HocineFerradj]

Best way to calculate Fibonacci number is : public static double fibonacci2(double number) { double a = 1 / Math.sqrt(5); double b = Math.pow((1 + Math.sqrt(5)) / 2, number); double c = Math.pow((1 - Math.sqrt(5)) / 2, number); return Math.round(a * (b - c)); }

[@ajsdatabase398]

good job. this is not for beginners

[@octaviocardenas4012]

I did that series without recursion that way: int[] fibonacci = new int[20]; fibonacci[0] = 0; fibonacci[1] = 1; for(int i=2; i

[@belkhirisub9115]

Honestly, I was struggling to understand Fibonacci in high school, but now I understand everything well I wish you were my programming teacher

[@vitcermak7737]

As a junior software engineer (Java dev) I gotta ask you - where have you been 2 years ago when I was sweating bullets on programming exercises like this?! :D

[@tubememax]

We could also use a hash map to store results over more than one calculation.

[@JoaoRicSoares]

What text font is he using?

[@FloStudios]

Interesting facet about this caching method...you don't even need to write a loop and run fibonacci() n-times. Just run it once and the cache should have the whole sequence! Print the array space delimited.

[@pendelachenchusasank3993]

f(n) means f(1) and f(n-1)+f(n-2) means f(0)+f(-1) is this correct sir and what is the answer sir

[@haltsmaul.]

To calculate all Fibonacci's up to n, you could have used the cache array instead of using a for loop to calculate each n.

[@giftbanda9795]

public static void main(String[] args) { Map memo = new HashMap(); int result = fibonacci(5, memo); System.out.println(result); } /** * Calculates the nth Fibonacci number using memoization. * Time Complexity: O(n) where n is the value of the input number. * Space Complexity: O(n) for storing the memoization map and the recursive call stack. */ public static int fibonacci(int num, Map memo) { if (num

[@colonelh.s.l.3834]

Wait why does fibonacci(n-1) + fibonacci(n-2) eventually shoot out 8 if n = 6? If fibonacci(n-1) is called, won't it keep calling itself until it gets to n=1, and then give n=1? Which would mean 1 + 1 = 2?

[@timm1328]

let phi = (1+sqrt(5))/2 then fib(n)= (phi^n - (1-phi)^n)/sqrt(5). no recursion and returns values as large as a double can hold and accepts any positive double as input not just integers

[@vpenywise]

Brutal... It all seems so easy, so logical, so natural... But then you try to code it yourself and... woof! :D

[@alexandercvetkov4269]

Repetition is the mother of all knowledge. :D The fundament is easy and natural, to be able to apply the fundament - it takes practice. And practice is the child of repetition. I was like that with two-dimensional arrays - the two indexes confused me to a level beyond 14 year old girl, watching a chick-flick. Now i do them fine. :D I guess a guy must be more stubborn than the actual thing he wants to learn.

[@bennyibmnkonga1122]

very cool! the cache help to reduce the complexity of the fibo algorithme to O(n) instead of O(n^2) i found it very amazing and i like, thank you JOHN!

[@raz0229]

or store the values of n in an array upto 100 or something and just return them so you always get O(1) to impress your teacher. LOL

[@AlexandruTimus]

You can get O(1) by doing the calculation in a mathematical way. You you search on internet there are some formulas that can calculate the Nth number in just one line of matemathic operations.

[@theALFEST]

Iterative algorithm is much faster and doesn't need cache

[@bolbans]

@@theALFEST would you mind sharing?

[@theALFEST]

@@bolbans for (int i = 3; i

[@gsabella4]

I bombed this on a mid level tech interview today. I was not familiar with the Fibonacci algorithm, however the interviewer also explained this horribly. Hope it doesn't ruin my chances, but I'll see where the chips fall.

[@evanserickson]

Love the video! Let's see some full stack tutorials for back end. Like spring and credit card processing

[@obvioustruth]

works for any number?: fibonacci(n) { φ=(1+√5)/2; return (φ^n-(1-φ)^n)/√5 }

[@KaisarAnvar]

I love the fact that you don’t use auto-prediction while you’re typing. I want to disable mine too but don’t know how. I use IntelliJ and VSCode.

[@1004-u5t]

excuse my dumbness.. but, how does the program know whats in f(n-1) and f(n-2)?

[@danielmdubois]

Nice video. I understand why you skipped over it, since the focus was on teaching recursion, but I think it would be worth taking a moment at the point when you introduce a for loop to mention that you could have avoided all the recursion entirely with an interative solution. (At least you're saving the memoization from call to call!)

[@FredrickIrubor]

Using a for loop and array worked just fine with fast speed public class FibonnaciLoop { private static long[] fibArr; public static void main(String[] args) { int n=50; fibArr = new long[n+1]; fibArr[0]=0; fibArr[1]=1; for (int i=2; i

[@danielmdubois]

@@FredrickIrubor You don't need to allocate an array; you can get by with updating and storing nMinus1 and nMinus2 each iteration.

[@omaribrahimmemories]

how does the code store? isn't when the project is off the still will return to null so if it have been to calculate again it will take same time, i didn't understand this thing

[@brandonsullivan4866]

Amazing video sir! Thank you for the knowledge.

[@birukbrookm.9809]

it would have been so much better if you wrote it cleanly and not your functions and variable every where but thanks for explaning

[@bestmomentsofgamer2130]

can anyone please give me John's plugin to have such font and color in Intellj...

[@sameenchowdhury2312]

you have 2 links to your course in the description, 1 is free other is paid. Now which is what and which one is best for what type of people?

[@kunalkheeva]

Could you please start solving leetcode problems as well?

[@CarlosFlinston]

fibonacci without recursion for curious: private static long fibonacci(int n) { if (n

[@freeSpiritNonna]

Thanks for the great video for Java recursion usage. It's very helpful for Java beginners like me. However, I am not sure if the recursion is a good method for this Fibonacci calculation because a simple while loop seems to achieve the same speed in delivering the same result without costing any memory for the array. I tried the following quick code and it delivered the same result in no time: 7540113804746346429. public class FiboLong { public static void main(String[] args) { long lPrev = 0; long lCurr = 1; long lPrevTmp; long lCount = 1; while (lCount

[@Nbak-cw7jx]

Hello thank you for this tutorial, but what if the user will be the ones to choose the start and end point of the Fibonacci like the user chooses 55 as the starting point and 987 as the end, and it must dispay 55 to 987 without displaying the series before 55

[@samuelsimon4087]

firstly 987 is too high.(Explained in vid last part), disregarding that calculate till the higher number. to print it, loop goes like int low = 55, high = 987; for(int i = low; i

[@Mu7ammad]

is there a way to solve the problem of limitation like what if I use wrapped numbers?

[@killerman0073]

My god... by the end of the video all i could hear was fibonacci and some other words in the middle

[@michelazar5920]

why do you use private instead of public for the fibonacci method

[@nibbler7]

Man your videos are a lifesaver! Could you do a video on lambdas? It would be very appreciated!

[@arup_basak]

public static long fibonacchi2(int n) { n--; long addable, curr, temp; addable = 0; curr = 1; for (int i = 0; i < n; i++) { temp = curr; curr += addable; addable = temp; } return curr; } Hey John, i think my Code is More faster and consumes less Memory

[@brightmatter]

interesting, I made one of these with an iterative approach to add up a particular diagonal in pascal's triangle. I think i hit a wall sooner than n=92 though. i'll have to go back and see why that was.

[@flamewing7851]

honestly, i'd rather just use the formula for the sequence.

[@AnuragSingh-fd7nc]

How can i see how much time it took to run the program in visual studio code?

[@marathistates]

Thanks jon Bhai i am from India🇮🇳 😍

[@King-nt2zv]

there is actually a formula for nth Fibonacci number , (((1+√5)/2)^n - ((1-√5)/2)^n))/ √5 . It's super fast.

[@Zeddy27182]

It's not about the value but the recursion.🤣

[@bhalatr9098]

import java.math.BigDecimal; public class fibonacci { public static void main(String[] args) { BigDecimal n = BigDecimal.valueOf(1000), firstTerm = BigDecimal.valueOf(0), secondTerm = BigDecimal.valueOf(1); System.out.println("Fibonacci Series till " + n + " terms:"); for (BigDecimal i = BigDecimal.valueOf(0); i.compareTo(n) < 0; ) { System.out.print(firstTerm + " "); // compute the nextterm BigDecimal nextTerm = firstTerm.add(secondTerm); firstTerm = secondTerm; secondTerm = nextTerm; i = i.add(BigDecimal.ONE); } } }

[@Nbak-cw7jx]

Hello thank you for this tutorial, but what if the user will be the ones to choose the start and end point of the Fibonacci like the user chooses 55 as the starting point and 987 as the end, and it must dispay 55 to 987 without displaying the series before 55

[@JesseLinseman]

Simply change the bounds of the for loop he showed in the video to include this user entry. e.g. if user entered start = 55, end = 987, the loop would be changed to the following: for(int i = start; i

[@ranaufalmuha]

"if u learn something", of course its verry helpfully btw.. i got exam yesterday, and i make same return with you wich is (fibonacci(n-1)+fibonnaci(n-2)), but my base case is just if(n==1). anddddd the time is ended. its running when the number is odd :" .. wtf im so stupid yesterdayy. i hope my lecturer forgive me and give me good score :"

[@tvclipsgames1338]

that is why long value is very very long 👍👍

[@fesd2010]

you can use BigInteger to get higher numbers

[@TheBikerDude2024]

Wonderful explaining.

[@augustuscaeser8939]

can you also do this iteratively please

[@4ipon4ik]

I don't understand one thing. Why are you calling your fast recursive function in a for loop (for example 100 times) to print each fibonacci number, when you can call it 1 time with last number "fibonacci(100)" and then just print out all fibonacciCache values?

[@theclam1338]

Would have been good if you can use stack to explain how the recursive calls are working

[@CodingWithJohn]

I have a more extensive explanation of recursion here: kzbin.info/www/bejne/oV6am32GbLZ5e68

[@manudewi]

I tried to reproduce this for python and didn't get it at first But using nested functions I achieved it... thank you very much for the inspiration!!! 🙏 One question as a Java beginner concerning the scope of the fibonacciCache, that makes it accessible to different recursive calls of the fibonacci function (as every recursive call has it's own execution context, we don't wan't to be creating a number of fibonacciCache arrays equal to the number of recursive calls, right?)). I get why you create an array instance outside of the fibonacci method, but is there any special reasion, why you created a fibonacciCache method, instead of just a fibonacciCache array? Has it to do something with the fact, that array sizes in Java are fixed?

[@Jesun-fi1zr]

Thx you are saviour of the exam

[@ToBa2501]

That's a good abroach, but I wonder if it is necessary to solve it with recursion. If the values are stored in an array anyway then you have everything you need to do it without recursion. I did it this way and I also tried it once using a double as a return to check higher values. I'd tried 1500 and it took still not more than a millisecond to calculate the Fibonacci. public class Application { public static void main(String[] args) { int n = 90; long fibunacciNumber = calcFibunacci(n); System.out.println("Fibonacci: " + fibunacciNumber); } private static long calcFibunacci(int n) { long [] list = new long[n + 1]; list[0] = 0; list[1] = 1; for (int i = 2; i

[@rahulmohuture]

Hello sir, I'm a complete bigginer in Java and I have question about my courier.... That java really a courier charming language to learn.... If it really is then please guide me if you are reading this 🙏 Show me path 👣 to good future.... Please reply 😇

[@robertb5357]

Great and easy explanations of many java topics. Keep up the good work

[@anubhavtrivedi1283]

Make video on java enterprise edition

[@ravitrivedi9588]

Thank you so much for the simple explanation john!!!!!!!!, I just have a tiny question to ask , Why are you creating a Cache in main method can't we directly create it inside the fibonacci function itself ? As its using mainly over there

[@djwebm6653]

Nice video, but im debating with myself if the cache was really needed aswell. Wouldnt it be possible to pass trough the destination n, the current n previous number and this number recursivly? I might be in the wrong here tho but Something like this: fibbonachi(int destN, int currentN, int previous, int number) The method would just add the numbers and send through the new number and the number variable. And then whenever the destN is equal to the currentN it would stop recurring

[@nate6199]

Do you think you could explain reading and writing input from a file? Love your videos.

[@dilln2158]

He already did

[@starfire7119]

Can you do it without using loop

[@mohammedjaradat7806]

the cache part was where I lost it

[@begumgames]

No surprise u gone bald

[@jesusayala1342]

Thank you very much for all the effort dear John!!! I like all your content, it helps us to learn a lot!! please don't stop teaching us =) I was thinking of simplifying a bit the code you teach us in your video, but I'd like your opinion: private static long fibonacci(int n){ if (n

[@marvinabt4964]

Fast algorithm? Isn't it faster to use the formula for the nth term, as it runs constant instead of in terms of n?

[@CodingWithJohn]

Yep that's faster for sure. But I know it's a common early programming assignment to implement a Fibonacci algorithm specifically using recursion.

[@dsar8727]

Hey John, love the Epi SG. And Rush are amazing.

[@lucasbittencourtnogueira5858]

what if we used a Map? Hashmap

[@franchello1105]

Change to BigInteger.

[@fremontlowe1]

Thanks for this tutorial. I found it to be extremely helpful. I even changed the cache variable to BigInt to increase the size of fibonacci numbers returned. I no longer saw negative numbers; and still executed in sub seconds.

[@FredrickIrubor]

the 12th fibonacci number is 144, that's too much of a mathematical coincidence

[@שחרכץ-ד6ר]

have you heard of otto?

[@shwetayadav4244]

Amazin explanation

[@2k7Bertram]

Bro I wish you were my Java prof back in college. Excellent!

[@lumilo7]

GRacias pelaooo! ♥

[@felixurrutia4246]

Is there a way to fix the long issue you shown at the end of the video?

[@carlostitlan]

May be with BigInteger class

[@enriquecabral-mixco1337]

Great video!

[@יהודהבןארצי]

Good explanation

[@diyaa_hudaib5263]

U are great maaaannn can u explain how can i put every element in GUI separated on lines and put thim exactly on the spot that i think?

[@lakhanitutorials]

👍👍👍

[@DK-fn6xr]

This is how I learned about stack overflow error.

[@Soulyrics-kr8sf]

Gammac cuddh

[@שחרכץ-ד6ר]

do u like long?

[@navjotsingh2457]

Ty

[@abymathew575]

Thank you

[@pranjalnama2420]

thank you

[@yudup12]

Petardieu