1 2 Previous Next 22 Replies Latest reply: Apr 19, 2013 7:01 PM by 967983 RSS

    Fibonnaci Recursion without for or while loop

    967983
      Hi,

      I am trying to print the values of Fibonnaci by using recursion but without using for or while loop.

      Any help is appreciated. I have tried different combinations but I am not getting the desired output.The base program I have created is below:
      public class Samp {
           static int[] fibValue=new int[2];
           int a;
           int flag0=0;
           int flag1=0;
           public static void main(String[] args) 
           {
                Samp s = new Samp();
                fibValue[0]=0;
                fibValue[1]=1;
                System.out.print("0,1,");
                s.fib(10);
           }
      
      
           int fib(int n)
           {
                if(n==0)
                {
                     flag0=1;
                     return 0;
                }
                if(n==1)
                {
                     flag1=1;
                     return 1;
                }
                a=(fib(n-1) + fib(n-2));
                System.out.print(a+",");
                return a;
           }
      }
      Sample Output:
      0,1,1,2,3,5,8,13,21,34,
        • 1. Re: Fibonnaci Recursion without for or while loop
          1001575
          Hi,
          The problem is with your printing. Every time it goes to the recursive method it prints the intermediate results.

          So, while calculating the values, store them in an array and print them at last. Here is the modified code:

          package com.example;
          
          public class Fibonacci {
               public static int[] fibo = new int[20];
               public static void main(String[] args) {
                    int n = 10;
                    fib(n);
                    for (int k=0; k<n ; k++) {
                         System.out.println(fibo[k]);
                    }
               }
          
               private static int fib(int i) {
                    if(i == 0 || i == 1) {
                         fibo[i] = i;
                         return i;
                    }
                    else {
                         int n = fib(i-2) + fib(i-1);
                         fibo[i] = n;
                         return n;
                    }
                    
               }
          }
          • 2. Re: Fibonnaci Recursion without for or while loop
            967983
            Is it not possible without using for or while loop? I am sure there must be some way.
            • 3. Re: Fibonnaci Recursion without for or while loop
              EJP
              System.out.println(Arrays.toString(fibo));
              • 4. Re: Fibonnaci Recursion without for or while loop
                1001575
                Here for loop is being used just to print the series and not for the calculation of Fibonacci series. If still you want not to use loop for printing, you can use this:
                System.out.println(Arrays.toString(fibo));
                • 5. Re: Fibonnaci Recursion without for or while loop
                  967983
                  You are missing the point. I want to print the values in the function fib itself without storing anywhere. I am sure we can check for some condition and print the value there itself.
                  • 6. Re: Fibonnaci Recursion without for or while loop
                    gimbal2
                    964980 wrote:
                    I am sure we can check for some condition and print the value there itself.
                    You're sure are you? Then what "some condition" are you talking about? Or are you just making wild claims to get other people to think about it for you?

                    I'M SURE there is a way to fly to the moon without building a space ship. Go!
                    • 7. Re: Fibonnaci Recursion without for or while loop
                      EJP
                      You are missing the point.
                      I am missing what point?
                      I want to print the values in the function fib itself without storing anywhere.
                      I see. I am missing the point that you hadn't even stated yet. How surprising.

                      Please don't waste my time with any more of this nonsense.
                      • 8. Re: Fibonnaci Recursion without for or while loop
                        967983
                        You people, being such senior members of the forum should not talk like this. You must always say it's possible.

                        There must be some way of printing the fibonnaci numbers without storing anywhere and getting it without printing the intermediate values.

                        I am going to talk about the pattern I found in my next post. Watch out.
                        • 9. Re: Fibonnaci Recursion without for or while loop
                          967983
                          public class Samp {
                               static int[] fib=new int[10000];
                               int a;
                               int flag0=0;
                               int flag1=0;
                               public static void main(String[] args) {
                                    Samp st = new Samp();
                          
                                    fib[0]=0;
                                    fib[1]=1;
                          
                          
                                    System.out.print("0,1,");
                                    st.fib(10);
                          
                               }
                          
                          
                               int fib(int n)
                               {
                                    if(n==0)
                                    {
                                         flag0=1;
                                         return 0;
                                    }
                                    if(n==1)
                                    {
                                         flag1=1;
                                         return 1;
                                    }
                                    System.out.println("(n-1)="+(n-1)+",(n-2)="+(n-2));
                                    a=(fib(n-1) + fib(n-2));
                                    System.out.print(a+",");       
                                    return a;
                               }
                          }
                          Output:
                          0,1,(n-1)=9,(n-2)=8
                          (n-1)=8,(n-2)=7
                          (n-1)=7,(n-2)=6
                          (n-1)=6,(n-2)=5
                          (n-1)=5,(n-2)=4
                          (n-1)=4,(n-2)=3
                          (n-1)=3,(n-2)=2
                          (n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,(n-1)=1,(n-2)=0
                          1,3,(n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,5,(n-1)=3,(n-2)=2
                          (n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,(n-1)=1,(n-2)=0
                          1,3,8,(n-1)=4,(n-2)=3
                          (n-1)=3,(n-2)=2
                          (n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,(n-1)=1,(n-2)=0
                          1,3,(n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,5,13,(n-1)=5,(n-2)=4
                          (n-1)=4,(n-2)=3
                          (n-1)=3,(n-2)=2
                          (n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,(n-1)=1,(n-2)=0
                          1,3,(n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,5,(n-1)=3,(n-2)=2
                          (n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,(n-1)=1,(n-2)=0
                          1,3,8,21,(n-1)=6,(n-2)=5
                          (n-1)=5,(n-2)=4
                          (n-1)=4,(n-2)=3
                          (n-1)=3,(n-2)=2
                          (n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,(n-1)=1,(n-2)=0
                          1,3,(n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,5,(n-1)=3,(n-2)=2
                          (n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,(n-1)=1,(n-2)=0
                          1,3,8,(n-1)=4,(n-2)=3
                          (n-1)=3,(n-2)=2
                          (n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,(n-1)=1,(n-2)=0
                          1,3,(n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,5,13,34,(n-1)=7,(n-2)=6
                          (n-1)=6,(n-2)=5
                          (n-1)=5,(n-2)=4
                          (n-1)=4,(n-2)=3
                          (n-1)=3,(n-2)=2
                          (n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,(n-1)=1,(n-2)=0
                          1,3,(n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,5,(n-1)=3,(n-2)=2
                          (n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,(n-1)=1,(n-2)=0
                          1,3,8,(n-1)=4,(n-2)=3
                          (n-1)=3,(n-2)=2
                          (n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,(n-1)=1,(n-2)=0
                          1,3,(n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,5,13,(n-1)=5,(n-2)=4
                          (n-1)=4,(n-2)=3
                          (n-1)=3,(n-2)=2
                          (n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,(n-1)=1,(n-2)=0
                          1,3,(n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,5,(n-1)=3,(n-2)=2
                          (n-1)=2,(n-2)=1
                          (n-1)=1,(n-2)=0
                          1,2,(n-1)=1,(n-2)=0
                          1,3,8,21,55,
                          • 10. Re: Fibonnaci Recursion without for or while loop
                            967983
                            public class Samp {
                                 static int[] fib=new int[10000];
                                 int a;
                                 int flag0=0;
                                 int flag1=0;
                                 public static void main(String[] args) {
                                      Samp st = new Samp();
                            
                                      fib[0]=0;
                                      fib[1]=1;
                            
                            
                                      System.out.print("0,1,");
                                      st.fib(5);
                            
                                 }
                            
                            
                                 int fib(int n)
                                 {
                                      if(n==0)
                                      {
                                           flag0=1;
                                           return 0;
                                      }
                                      if(n==1)
                                      {
                                           flag1=1;
                                           return 1;
                                      }
                                      System.out.println("(n-1)="+(n-1)+",(n-2)="+(n-2));
                                      a=(fib(n-1) + fib(n-2));
                                      System.out.print(a+",");       
                                      return a;
                                 }
                            }
                            Output:
                            0,1,(n-1)=4,(n-2)=3
                            (n-1)=3,(n-2)=2
                            (n-1)=2,(n-2)=1
                            (n-1)=1,(n-2)=0
                            1,2,(n-1)=1,(n-2)=0
                            1,3,(n-1)=2,(n-2)=1
                            (n-1)=1,(n-2)=0
                            1,2,5,
                            • 11. Re: Fibonnaci Recursion without for or while loop
                              967983
                              In the above 2 posts I have passed the values 5 and 10 to the fib function. Another thing I noticed about the pattern is that second time time n-1 becomes 1 and n-2 becomes 0 consequently, the output printed is a fibonacci number and not an intermediate value.
                              • 12. Re: Fibonnaci Recursion without for or while loop
                                marlin
                                As you probably know, you can calculate the nth Fib number recursively by encoding the relationship

                                fib(n) = fib(n-1) + fib(n-2)

                                and yes, you must terminate the recursion by properly guarding the expression with an if clause to do the trivial case.

                                Similarly you can recursively print a list of n fib numbers by first printing the first n-1 and then printing the nth

                                print(n) = print(n-1); System.out.println(", " + fib(n)); System.out.println();

                                which similarly must be properly guarded.

                                It is a stupid way to do things, but such is the nature of homework assignments.
                                • 13. Re: Fibonnaci Recursion without for or while loop
                                  967983
                                  Hi Marlin,

                                  Thanks for your time and reply. Can you pls give me the code to print the nth fibonacci number by calling the print function recursively.
                                  • 14. Re: Fibonnaci Recursion without for or while loop
                                    thomas.behr
                                    Oh, come on. Do show some initiative. It's your homework after all.
                                    1 2 Previous Next