This discussion is archived
1 2 Previous Next 22 Replies Latest reply: Apr 19, 2013 5:01 PM by 967983 RSS

Fibonnaci Recursion without for or while loop

967983 Newbie
Currently Being Moderated
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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Guru
    Currently Being Moderated
    System.out.println(Arrays.toString(fibo));
  • 4. Re: Fibonnaci Recursion without for or while loop
    1001575 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Guru
    Currently Being Moderated
    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 Guru
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    Oh, come on. Do show some initiative. It's your homework after all.
1 2 Previous Next

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points