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

# Fibonnaci Recursion without for or while loop

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