Java recursive Fibonacci sequence

Question

Please explain this simple code   public int fibonacci int n         if n    0          return 0      else if n    1        return 1     else       return fibonacci n - 1    fibonacci n - 2       I m confused with the last line especially because if n   5 for example  then fibonacci 4    fibonacci 3  would be called and so on but I don t understand how this algorithm calculates the value at index 5 by this method  Please explain with a lot of detail

User · Answer

Simple Fibonacci  public static void main String  args        int i   0      int u   1       while i lt 100           System out println i           i   u i          System out println u           u   u i

User · Answer

Try this  private static int fibonacci int n       if n  lt   1          return n      return fibonacci n - 1    fibonacci n - 2

User · Answer

Use while   public int fib int index        int tmp   0  step1   0  step2   1  fibNumber   0      while  tmp  lt  index - 1            fibNumber   step1   step2          step1   step2          step2   fibNumber          tmp    1             return fibNumber      The advantage of this solution is that it s easy to read the code and understand it  hoping it helps

User · Answer

Michael Goodrich et al provide a really clever algorithm in Data Structures and Algorithms in Java  for solving fibonacci recursively in linear time by returning an array of  fib n   fib n-1     public static long   fibGood int n        if  n  lt    1            long   answer    n 0           return answer        else           long   tmp   fibGood n-1           long   answer    tmp 0    tmp 1   tmp 0            return answer            This yields fib n    fibGood n  0

User · Answer

Yes  it s important to memorize your calculated return value from each recursion method call  so that you can display the series in calling method   There are some refinement in the implementation provided  Please find below implementation which gives us more correct and versatile output   import java util HashMap  import java util stream Collectors   public class Fibonacci   private static HashMap lt Long  Long gt  map   public static void main String   args        long n   50      map   new HashMap lt  gt         findFibonacciValue n       System out println map values   stream   collect Collectors toList         public static long findFibonacciValue long number        if  number  lt   1            if  number    0                map put number  0L               return 0L                    map put number  1L           return 1L        else if  map containsKey number             return map get number         else           long fibonacciValue   findFibonacciValue number - 1L    findFibonacciValue number - 2L           map put number  fibonacciValue           return fibonacciValue              Output for number 50 is    0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181  6765  10946  17711  28657  46368  75025  121393  196418  317811  514229  832040  1346269  2178309  3524578  5702887  9227465  14930352  24157817  39088169  63245986  102334155  165580141  267914296  433494437  701408733  1134903170  1836311903  2971215073  4807526976  7778742049  12586269025

User · Answer

Most of solutions offered here run in O 2 n  complexity  Recalculating identical nodes in recursive tree is inefficient and wastes CPU cycles   We can use memoization to make fibonacci function run in O n  time  public static int fibonacci int n        return fibonacci n  new int n   1       public static int fibonacci int i  int   memo         if  i    0    i    1            return i             if  memo i     0            memo i    fibonacci i - 1  memo    fibonacci i - 2  memo             return memo i       If we follow Bottom-Up Dynamic Programming route  below code is simple enough to compute fibonacci   public static int fibonacci1 int n        if  n    0            return n        else if  n    1            return n            final int   memo   new int n        memo 0    0      memo 1    1       for  int i   2  i  lt  n  i              memo i    memo i - 1    memo i - 2             return memo n - 1    memo n - 2

User · Answer

F n                                                                     F n-1    F n-2                                                                         F n-2  F n-3  F n-3   F n-4                                                     F n-3  F n-4    Important point to note is this algorithm is exponential because it does not store the result of previous calculated numbers  eg F n-3  is called 3 times    For more details refer algorithm by dasgupta chapter 0 2

User · Answer

This is the best video I have found that fully explains recursion and the Fibonacci sequence in Java   http   www youtube com watch v dsmBRUCzS7k  This is his code for the sequence and his explanation is better than I could ever do trying to type it out   public static void main String   args        int index   0      while  true                System out println fibonacci index            index                public static long fibonacci  int i                if  i    0  return 0          if  i lt   2  return 1           long fibTerm   fibonacci i - 1    fibonacci i - 2           return fibTerm

User · Answer

RanRag accepted  answer will work fine but that s not optimized solution until and unless it is memorized as  explained in Anil answer   For recursive consider below approach  method calls of TestFibonacci are minimum  public class TestFibonacci        public static void main String   args             int n   10           if  n    1                System out println 1              else if  n    2                System out println 1               System out println 1             else               System out println 1               System out println 1               int currentNo   3              calFibRec n  1  1  currentNo                         public static void calFibRec int n  int secondLast  int last              int currentNo            if  currentNo  lt   n                 int sum   secondLast   last              System out println sum               calFibRec n  last  sum    currentNo

User · Answer

In pseudo code  where n   5  the following takes place      fibonacci 4    fibonnacci 3    This breaks down into       fibonacci 3    fibonnacci 2      fibonacci 2    fibonnacci 1     This breaks down into         fibonacci 2    fibonnacci 1       fibonacci 1    fibonnacci 0         fibonacci 1    fibonnacci 0     1     This breaks down into          fibonacci 1    fibonnacci 0     1      1   0       1   0    1     This breaks down into          1   0    1      1   0       1   0    1     This results in  5  Given the fibonnacci sequence is 1 1 2 3 5 8      the 5th element is 5  You can use the same methodology to figure out the other iterations

User · Answer

A Fibbonacci sequence is one that sums the result of a number when added to the previous result starting with 1         so   1   1   2            2   3   5            3   5   8            5   8   13            8   13   21   Once we understand what Fibbonacci is  we can begin to break down the code   public int fibonacci int n         if n    0          return 0      else if n    1        return 1     else       return fibonacci n - 1    fibonacci n - 2       The first if statment checks for a base case  where the loop can break out  The else if statement below that is doing the same  but it could be re-written like so         public int fibonacci int n             if n  lt  2               return n           return fibonacci n - 1    fibonacci n - 2           Now that a base case is establish we have to understand the call stack Your first call to  fibonacci  will be the last to resolve on the stack  sequence of calls  as they resolve in the reverse order from which they were called  The last method called resolves first  then the last to be called before that one and so on     So  all the calls are made first before anything is  calculated  with those results  With an input of 8 we expect an output of 21  see table above    fibonacci n - 1  keeps being called until it reaches the base case  then fibonacci n - 2  is called until it reaches the base case  When the stack starts summing the result in reverse order  the result will be like so     1   1   1        ---- last call of the stack  hits a base case   2   1   3        ---- Next level of the stack  resolving backwards   2   3   5        ---- Next level of the stack  continuing to resolve     They keep bubbling  resolving backwards  up until the correct sum is returned to the first call in the stack and that s how you get your answer   Having said that  this algorithm is very inefficient because it calculates the same result for each branch the code splits into  A much better approach is a  bottom up  one where no Memoization  caching  or recursion  deep call stack  is required   Like so             static int BottomUpFib int current                        if  current  lt  2  return current               int fib   1              int last   1               for  int i   2  i  lt  current  i                                  int temp   fib                  fib    last                  last   temp                             return fib

User · Answer

I think this is a simple way   public static void main String   args            Scanner input   new Scanner System in           int number   input nextInt            long a   0          long b   1          for int i   1  i lt number i                 long c   a  b              a b              b c              System out println c

User · Answer

Instead of using an array and doing some fancy things just two add two values is waste of time  I have found an efficient way to display print the famous Fibonacci sequence   public static void main String args              System out println  This program lists the Fibonacci sequence              int answer   0          int startValue   1          int sum   0           while  answer  lt  10000                System out println answer                sum   add answer startValue                startValue   answer              answer   sum                                          This method return the sum of addition      private static int add int A int B               return A B

User · Answer

http   en wikipedia org wiki Fibonacci number in more details  public class Fibonacci        public static long fib int n            if  n  lt   1  return n          else return fib n-1    fib n-2              public static void main String   args            int N   Integer parseInt args 0            for  int i   1  i  lt   N  i                System out println i          fib i               Make it that as simple as needed no need to use while loop and other loop

User · Answer

A Fibbonacci sequence is one that sums the result of a number then we have added to the previous result  we should started from 1  I was trying to find a solution based on algorithm  so i build the recursive code  noticed that i keep the previous number and i changed the position  I m searching the Fibbonacci sequence from 1 to 15    public static void main String args           numbers 1 1 15       public static int numbers int a  int temp  int target        if target  lt   a                return a             System out print a              a   temp   a       return numbers temp a target

User · Answer

Why this answer is different  Every other answer either    Prints instead of returns Makes 2 recursive calls per iteration Ignores the question by using loops    aside  none of these is actually efficient  use Binet s formula to directly calculate the nth term   Tail Recursive Fib  Here is a recursive approach that avoids a double-recursive call by passing both the previous answer AND the one before that   private static final int FIB 0   0  private static final int FIB 1   1   private int calcFibonacci final int target        if  target    0    return FIB 0        if  target    1    return FIB 1         return calcFibonacci target  1  FIB 1  FIB 0      private int calcFibonacci final int target  final int previous  final int fibPrevious  final int fibPreviousMinusOne        final int current   previous   1      final int fibCurrent   fibPrevious   fibPreviousMinusOne         If you want  print here   memoize for future calls      if  target    current    return fibCurrent         return calcFibonacci target  current  fibCurrent  fibPrevious

User · Answer

in the fibonacci sequence  the first two items are 0 and 1  each other item is the sum of the two previous items  i e  0 1 1 2 3 5 8     so the 5th item is the sum of the 4th and the 3rd items

User · Answer

Here is O 1  solution     private static long fibonacci int n        double pha   pow 1   sqrt 5   n       double phb   pow 1 - sqrt 5   n       double div   pow 2  n    sqrt 5        return  long    pha - phb    div        Binet s Fibonacci number formula used for above implementation   For large inputs long can be replaced with BigDecimal

User · Answer

Here is a one line febonacci recursive   public long fib  long n             return n  lt   0   0   n    1   1   fib  n - 1     fib  n - 2

User · Answer

Fibonacci series is one simple code that shows the power of dynamic programming  All we learned from school days is to run it via iterative or max recursive code  Recursive code works fine till 20 or so  if you give numbers bigger than that you will see it takes a lot of time to compute  In dynamic programming you can code as follows and it takes secs to compute the answer   static double fib int n        if  n  lt  2          return n      if  fib n     0          return fib n       fib n    fib n - 1    fib n - 2       return fib n       You store values in an array and proceed to fresh computation only when the array cannot provide you the answer

User · Answer

public class Fibonaci             static void fibonacci             int ptr1   1  ptr2   1  ptr3   0          int temp   0          BufferedReader Data new BufferedReader  new InputStreamReader System in            try               System out println  The Number Value s fib you required                   ptr3   Integer parseInt Data readLine                  System out print ptr1         ptr2                     for  int i   0  i  lt  ptr3  i                      System out print ptr1   ptr2                         temp   ptr1                  ptr1   ptr2                  ptr2   temp   ptr2                          catch IOException err                System out println  Error     err             catch NumberFormatException err                System out println  Invald Input                          public static void main String  args throws Exception                  Fibonaci fibonacci                  You can do like this

User · Answer

There are 2 issues with your code    The result is stored in int which can handle only a first 48 fibonacci numbers  after this the integer fill minus bit and result is wrong  But you never can run fibonacci 50   The code fibonacci n - 1    fibonacci n - 2  is very wrong  The problem is that the it calls fibonacci not 50 times but much more  At first it calls fibonacci 49  fibonacci 48   next fibonacci 48  fibonacci 47  and fibonacci 47  fibonacci 46  Each time it became fibonacci n  worse  so the complexity is exponential     The approach to non-recursive code    double fibbonaci int n       double prev 0d  next 1d  result 0d      for  int i   0  i  lt  n  i              result prev next          prev next          next result            return result

User · Answer

Recursion can be hard to grasp sometimes  Just evaluate it on a piece of paper for a small number   fib 4  - gt  fib 3    fib 2  - gt  fib 2    fib 1    fib 1    fib 0  - gt  fib 1    fib 0    fib 1    fib 1    fib 0  - gt  1   0   1   1   0 - gt  3   I am not sure how Java actually evaluates this  but the result will be the same

User · Answer

For fibonacci recursive solution  it is important to save the output of smaller fibonacci numbers  while retrieving the value of larger number  This is called  Memoizing    Here is a code that use memoizing the smaller fibonacci values  while retrieving larger fibonacci number  This code is efficient and doesn t make multiple requests of same function   import java util HashMap   public class Fibonacci     private HashMap lt Integer  Integer gt  map    public Fibonacci         map   new HashMap lt  gt           public int findFibonacciValue int number        if  number    0    number    1          return number            else if  map containsKey number           return map get number             else         int fibonacciValue   findFibonacciValue number - 2    findFibonacciValue number - 1         map put number  fibonacciValue         return fibonacciValue

User · Answer

public class febo     public static void main String   a       int x   new int 15        x 0  0     x 1  1     for int i 2 i lt x length i               x i  x i-1  x i-2           for int i 0 i lt x length i               System out println x i

User · Answer

In fibonacci sequence each item is the sum of the previous two  So  you wrote a recursive algorithm   So    fibonacci 5    fibonacci 4    fibonacci 3   fibonacci 3    fibonacci 2    fibonacci 1   fibonacci 4    fibonacci 3    fibonacci 2   fibonacci 2    fibonacci 1    fibonacci 0    Now you already know fibonacci 1   1 and fibonacci 0     0  So  you can subsequently calculate the other values   Now   fibonacci 2    1 0   1 fibonacci 3    1 1   2 fibonacci 4    2 1   3 fibonacci 5    3 2   5   And from fibonacci sequence 0 1 1 2 3 5 8 13 21     we can see that for 5th element the fibonacci sequence returns 5   See here for Recursion Tutorial

User · Answer

import java util         Author 12CSE54   Date 28 10 14        public class cfibonacci           public void print int p            int a 0 b 1 c      int q   new int 30       q 0  a      q 1  b      for int i 2 i lt p i              c a b      q i  c      a b      b c            System out println  elements are     n        for int i 0 i lt q length i        System out println q i              public static void main String ar   throws Exception           Scanner s new Scanner System in       int n      System out println  Enter the number of elements n        n sc nextInt        cfibonacci c new cfibonacci        c printf n

User · Answer

You can also simplify your function  as follows   public int fibonacci int n         if  n  lt  2  return n       return fibonacci n - 1    fibonacci n - 2

User · Answer

public long getFibonacci  int number        if   number  lt  2            return 1            long lRet   0      lRet   getFibonacci  number -1    getFibonacci  number -2       return lRet

User · Answer

public class FibonacciSeries        public static void main String   args            Scanner scanner   new Scanner System in           int N   scanner nextInt            for  int i   0  i  lt   N  i                  int result   fibonacciSeries i               System out println result                     scanner close               private static int fibonacciSeries int n            if  n  lt  0                return 1            else if  n  gt  0                return fibonacciSeries n - 1    fibonacciSeries n - 2                     return 0

User · Answer

It is a basic sequence that display or get a output of 1 1 2 3 5 8 it is a sequence that the sum of previous number the current number will be display next    Try to watch link below Java Recursive Fibonacci sequence Tutorial  public static long getFibonacci int number   if number lt  1  return number  else return getFibonacci number-1    getFibonacci number-2       Click Here Watch Java Recursive Fibonacci sequence Tutorial for spoon feeding

User · Answer

chro is spot on  but s he doesn t show the correct way to do this recursively   Here s the solution   class Fib       static int count       public static void main String   args            log fibWrong 20        6765         log  Count      count      21891         count   0          log fibRight 20       6765         log  Count      count      19            static long fibRight long n            return calcFib n-2  1  1              static long fibWrong long n            count            if  n    0    n    1                return n            else if  n  lt  0                log  Overflow                 System exit 1               return n            else               return fibWrong n-1    fibWrong n-2                         static long calcFib long nth  long prev  long next            count            if  nth--    0              return next          if  prev next  lt  0                log  Overflow with      nth 1                       combinations remaining                System exit 1                     return calcFib nth  next  prev next              static void log Object o            System out println o

User · Answer

Just to complement  if you want to be able to calculate larger numbers  you should use BigInteger   An iterative example   import java math BigInteger  class Fibonacci      public static void main String args             int n 10000          BigInteger   vec   new BigInteger n           vec 0  BigInteger ZERO          vec 1  BigInteger ONE             calculating         for int i   2   i lt n   i                 vec i  vec i-1  add vec i-2                         printing         for int i   vec length-1   i gt  0   i--               System out println vec i                System out println

User · Answer

public static long fib int n        long population   0       if   n    0      n    1      base cases               return n        else    recursion step                population  fib n - 1    fib n - 2              return population

User · Answer

By using an internal ConcurrentHashMap which theoretically might allow this recursive implementation to properly operate in a multithreaded  environment  I have implemented a fib function that uses both BigInteger and Recursion  Takes about 53ms to calculate the first 100 fib numbers   private final Map lt BigInteger BigInteger gt  cacheBig         new ConcurrentHashMap lt  gt     public BigInteger fibRecursiveBigCache BigInteger n        BigInteger a   cacheBig computeIfAbsent n  this  fibBigCache       return a    public BigInteger fibBigCache BigInteger n        if   n compareTo BigInteger ONE    lt   0            return n        else if  cacheBig containsKey n            return cacheBig get n         else           return                   fibBigCache n subtract BigInteger ONE                add fibBigCache n subtract TWO               The test code is    Test public void testFibRecursiveBigIntegerCache         long start   System currentTimeMillis        FibonacciSeries fib   new FibonacciSeries        IntStream rangeClosed 0 100  forEach p - amp R           BigInteger n   BigInteger valueOf p           n   fib fibRecursiveBigCache n           System out println String format  fib of  d is  d   p n                long end   System currentTimeMillis        System out println  elapsed           end - start                 end - start  1000         and output from the test is                                    fib of 93 is 12200160415121876738     fib of 94 is 19740274219868223167     fib of 95 is 31940434634990099905     fib of 96 is 51680708854858323072     fib of 97 is 83621143489848422977     fib of 98 is 135301852344706746049     fib of 99 is 218922995834555169026     fib of 100 is 354224848179261915075     elapsed 58 0

User · Answer

Most of the answers are good and explains how the recursion in fibonacci works    Here is an analysis on the three techniques which includes recursion as well     For Loop Recursion Memoization   Here is my code to test all three   public class Fibonnaci          Output   0 1 1 2 3 5 8 13      static int fibMemo         public static void main String args              int num   20           System out println  By For Loop            Long startTimeForLoop   System nanoTime               returns the fib series         int fibSeries     fib num           for  int i   0  i  lt  fibSeries length  i                  System out print       fibSeries i                            Long stopTimeForLoop   System nanoTime            System out println              System out println  For Loop Time      stopTimeForLoop - startTimeForLoop              System out println  By Using Recursion            Long startTimeRecursion   System nanoTime               uses recursion         int fibSeriesRec     fibByRec num            for  int i   0  i  lt  fibSeriesRec length  i                  System out print       fibSeriesRec i                            Long stopTimeRecursion   System nanoTime            System out println              System out println  Recursion Time      stopTimeRecursion -startTimeRecursion               System out println  By Using Memoization Technique            Long startTimeMemo   System nanoTime               uses memoization         fibMemo   new int num           fibByRecMemo num-1           for  int i   0  i  lt  fibMemo length  i                  System out print       fibMemo i                            Long stopTimeMemo   System nanoTime            System out println              System out println  Memoization Time      stopTimeMemo - startTimeMemo                   fib by memoization      public static int fibByRecMemo int num            if num    0               fibMemo 0    0              return 0                     if num   1    num   2             fibMemo num    1            return 1                      if fibMemo num     0               fibMemo num    fibByRecMemo num-1    fibByRecMemo num -2               return fibMemo num            else              return fibMemo num                          public static int   fibByRec int num            int fib     new int num            for  int i   0  i  lt  num  i                  fib i    fibRec i                      return fib             public static int fibRec int num            if  num    0                return 0            else if  num    1    num    2                return 1            else               return fibRec num - 1    fibRec num - 2                        public static int   fib int num            int fibSum     new int num           for  int i   0  i  lt  num  i                  if  i    0                    fibSum i    i                  continue                             if  i    1    i    2                    fibSum i    1                  continue                             fibSum i    fibSum i - 1    fibSum i - 2                      return fibSum             Here are the results   By For Loop  0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181  For Loop Time 347688 By Using Recursion  0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181  Recursion Time 767004 By Using Memoization Technique  0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181  Memoization Time 327031   Hence we can see memoization is the best time wise and for loop matches closely   But recursion takes the longest and may be you should avoid in real life  Also if you are using recursion make sure that you optimize the solution

[java] Java recursive Fibonacci sequence

Examples related to java

Examples related to recursion

Examples related to fibonacci