Fibonacci series using recursion in C
- Thread starter Rahul++
- Start date
- Status
dpacmittal said:
Hmm, First tell me what you mean by not using any conditions. I assume you understand that any statement that translates into a comparion instruction on the CPU counts as a conditional statement. So this includes if else, switch, conditional operator (?, : ) and all loop constructs (while, for, do while) or even any other operation that initiates conditional branching.
If you want to generate only n numbers then there has to be an exit criteria and regardless of the approach you use (looping, function recursion, process recursion i.e forking child processess), it will end up as a comparion operation in the end.
ashvarybabul
Discoverer
//WAF to display sum of fibonacci Series 0+1+1+2+3+5+8...... n terms by recurresion function....
#include<iostream.h>
#include<conio.h>
#include<math.h>
double fibonacci(int n)
{
if(n==0 || n==1)
return n;
else
return fibonacci(n-1)+fibonacci(n-2);
}
void main()
{
clrscr();
int len;
cout<<"\t\t\tFibonacci Series Sum\n\n";
cout<<"Enter no. of terms to be placed in the Febonacci Series"<<endl;
cin>>len;
cout<<"The Series is:"<<endl;
for(int i=0;i<len;i++)
{
cout<<fibonacci(i);
if(i<len-1)
cout<<"+";
}
getch();
}
#include<iostream.h>
#include<conio.h>
#include<math.h>
double fibonacci(int n)
{
if(n==0 || n==1)
return n;
else
return fibonacci(n-1)+fibonacci(n-2);
}
void main()
{
clrscr();
int len;
cout<<"\t\t\tFibonacci Series Sum\n\n";
cout<<"Enter no. of terms to be placed in the Febonacci Series"<<endl;
cin>>len;
cout<<"The Series is:"<<endl;
for(int i=0;i<len;i++)
{
cout<<fibonacci(i);
if(i<len-1)
cout<<"+";
}
getch();
}
Scorpy
Contributor
Thanks a lot ... now I understood till the part the loop goes till 1 .... now what about when the loop goes to 2 .... then I do not understand the statement
return fibonacci(n-1)+fibonacci(n-2);
I dont understand how it returns the value 1 with this .... I mean if I just write
return ((n-1)+(n-2)) ;
I get a different result missing out some numbers and I know what is that happening because I know what this is doing ...but I have no idea what is
return fibonacci(n-1)+fibonacci(n-2);
doing ... please can someone explain ? I would ask my CP teacher but shes a b**ch .... hence I ask you guys
return fibonacci(n-1)+fibonacci(n-2);
I dont understand how it returns the value 1 with this .... I mean if I just write
return ((n-1)+(n-2)) ;
I get a different result missing out some numbers and I know what is that happening because I know what this is doing ...but I have no idea what is
return fibonacci(n-1)+fibonacci(n-2);
doing ... please can someone explain ? I would ask my CP teacher but shes a b**ch .... hence I ask you guys
^^ First of all what is a Fibonacci sequence. Though there is lot of history behind it and a lot of geometrical significance, but in simple numerical representation the basic sequence goes like
0, 1, 1, 2, 3, 5, 8, 13 ....
So basically every new term in the sequence is the sum of the previous two terms in the sequence. If you represent that as a mathematical function, you arrive at
F(n) = F(n-1) + F(n-2) [ Where n >=2 and F(0) = 0, F(1) = 1];
I am going to write this in another way... F(n) = F(n-2) + F(n-1);
So now if you want to calculate the 4th term in the series,
You can write it as
F(4) = F(2) + F(3);
i.e to say the sum of the 2rd term and the 3nd terms. So to find the 4th number, you need to find the 2nd and 3rd terms in the sequence first. But how do you find them. Apply the same formula recursively on each. So we have
F(2) = F(1) + F(0).
F(3) = F(2) + F(1) => [F(1) + F(0)] + F(1)
We can keep expanding these functions till we reach F(1) and F(0). We already know that F(0) = 0 and F(1) = 1, so we make use of that fact.
So we have
F(4) = F(2) + F(3)
=> F(4) = [F(1) + F(0)] + [F(2) + F(1)]
=> F(4) = [F(1) + F(0)] + [[F(1) + F(0)] + F(1)]
=> F(4) = [1 + 0] + [[1 + 0] + 1]
=> F(4) = 3
So the 4th term in the Fibonacci series is 3.
The program is doing the same thing. when you call the function with a value of 5, its internally calling the same function again with 4 and 3 and returns their sum. You have a special condition inside such when you call the function with 1 or 0, you just return a hard coded value of 1 or 0. This terminates the recursion and your values get calculated. This explains the basics of how that recursive program works.
But as I have represented in my calculations, the biggest problem with this basic recursion algo is that you are calculating... F(n-1) and F(n-2) separately with recursive calls. once you calculate F(n-2), you need to calculate it again for F(n-1) = F(n-2) + F(n-3). I would Suffice to say that there is a lot redundant calculations, So its not very optimal in terms of CPU cycles required. So the program can be further tweaked to make sure that redundant calculations do not happen by storing the already calculated values in an array and re-using them. You can explore that solution separately.
0, 1, 1, 2, 3, 5, 8, 13 ....
So basically every new term in the sequence is the sum of the previous two terms in the sequence. If you represent that as a mathematical function, you arrive at
F(n) = F(n-1) + F(n-2) [ Where n >=2 and F(0) = 0, F(1) = 1];
I am going to write this in another way... F(n) = F(n-2) + F(n-1);
So now if you want to calculate the 4th term in the series,
You can write it as
F(4) = F(2) + F(3);
i.e to say the sum of the 2rd term and the 3nd terms. So to find the 4th number, you need to find the 2nd and 3rd terms in the sequence first. But how do you find them. Apply the same formula recursively on each. So we have
F(2) = F(1) + F(0).
F(3) = F(2) + F(1) => [F(1) + F(0)] + F(1)
We can keep expanding these functions till we reach F(1) and F(0). We already know that F(0) = 0 and F(1) = 1, so we make use of that fact.
So we have
F(4) = F(2) + F(3)
=> F(4) = [F(1) + F(0)] + [F(2) + F(1)]
=> F(4) = [F(1) + F(0)] + [[F(1) + F(0)] + F(1)]
=> F(4) = [1 + 0] + [[1 + 0] + 1]
=> F(4) = 3
So the 4th term in the Fibonacci series is 3.
The program is doing the same thing. when you call the function with a value of 5, its internally calling the same function again with 4 and 3 and returns their sum. You have a special condition inside such when you call the function with 1 or 0, you just return a hard coded value of 1 or 0. This terminates the recursion and your values get calculated. This explains the basics of how that recursive program works.
But as I have represented in my calculations, the biggest problem with this basic recursion algo is that you are calculating... F(n-1) and F(n-2) separately with recursive calls. once you calculate F(n-2), you need to calculate it again for F(n-1) = F(n-2) + F(n-3). I would Suffice to say that there is a lot redundant calculations, So its not very optimal in terms of CPU cycles required. So the program can be further tweaked to make sure that redundant calculations do not happen by storing the already calculated values in an array and re-using them. You can explore that solution separately.
btw, if you expand the equation F(n) = F(n-1) + F(n-2) and solve as an LRE, you will end up with the following simplification.
F(n) = [1/Sqrt(5)] * [(1 + Sqrt(5))/2]^n
I remember doing this in Engg Math, but don't remember much of it now.
F(4) = 0.44721359549995793928183473374626 * (1.6180339887498948482045868343656)^ 4 = 3.0652475842498527874864215681119 ~= 3
F(5) = 0.44721359549995793928183473374626 * (1.6180339887498948482045868343656)^ 5 = 4.9596747752497686660500910355946 ~= 5
F(6) = 0.44721359549995793928183473374626 * (1.6180339887498948482045868343656)^ 6 = 8.0249223594996214535365126036973 ~= 8
F(7) = 0.44721359549995793928183473374626 * (1.6180339887498948482045868343656)^ 7 = 12.984597134749390119586603639285 ~= 13
F(n) = [1/Sqrt(5)] * [(1 + Sqrt(5))/2]^n
I remember doing this in Engg Math, but don't remember much of it now.
F(4) = 0.44721359549995793928183473374626 * (1.6180339887498948482045868343656)^ 4 = 3.0652475842498527874864215681119 ~= 3
F(5) = 0.44721359549995793928183473374626 * (1.6180339887498948482045868343656)^ 5 = 4.9596747752497686660500910355946 ~= 5
F(6) = 0.44721359549995793928183473374626 * (1.6180339887498948482045868343656)^ 6 = 8.0249223594996214535365126036973 ~= 8
F(7) = 0.44721359549995793928183473374626 * (1.6180339887498948482045868343656)^ 7 = 12.984597134749390119586603639285 ~= 13
dpacmittal
Contributor
Lord Nemesis said:
Yeah, I know a condition is necessary for a loop to terminate. I meant just if, ? and switch.
Tell me if you want me to post my code.
Fibonacci recursion
Hi
how about following code for fibonacci... it uses recursion, does not do redundant calculations and is simple ....
#include <iostream>
using namespace std;
int flag=2,f;
void fibo(int a,int b)
{
if (flag>=f)
return;
else
{
flag++;
cout << "," <<a+b ;
fibo(b,a+b);
}
}
int main()
{
cout <<"Enter number upto which fibonacci is to be found : ";
cin >>f;
cout <<"\n0,1";
fibo(0,1);
cout<<"\n";
return 0;
}
Hi
how about following code for fibonacci... it uses recursion, does not do redundant calculations and is simple ....
#include <iostream>
using namespace std;
int flag=2,f;
void fibo(int a,int b)
{
if (flag>=f)
return;
else
{
flag++;
cout << "," <<a+b ;
fibo(b,a+b);
}
}
int main()
{
cout <<"Enter number upto which fibonacci is to be found : ";
cin >>f;
cout <<"\n0,1";
fibo(0,1);
cout<<"\n";
return 0;
}
Lol, I can do much more with C now. You bumped old thread man
I am glad u can :bigok:
i want ur views on this code as compared to usually suggested code
Prime number : concise code by me
any better suggestions ? :unsure:
#include <stdio.h>
void main()
{
int num , i;
printf("Enter the number :\n");
scanf("%d",&num);
for (i=2;i<=num/2;i++)
if(num%i==0)
break;
(i>num/2)?((num!=1)?printf("Prime number \n")rintf("neither\n"))rintf("not a prime number :\n");
}
---------- Post added at 12:45 AM ---------- Previous post was at 12:37 AM ----------
Prime number : supposingly concise code by me
any better suggestions ? :unsure:
#include <stdio.h>
void main()
{
int num , i;
printf("Enter the number :\n");
scanf(" % d",&num);
for (i=2;i<=num/2;i++)
}
any better suggestions ? :unsure:
#include <stdio.h>
void main()
{
int num , i;
printf("Enter the number :\n");
scanf("%d",&num);
for (i=2;i<=num/2;i++)
if(num%i==0)
break;
(i>num/2)?((num!=1)?printf("Prime number \n")
rintf("neither\n"))rintf("not a prime number :\n");}
---------- Post added at 12:45 AM ---------- Previous post was at 12:37 AM ----------
Prime number : supposingly concise code by me
any better suggestions ? :unsure:
#include <stdio.h>
void main()
{
int num , i;
printf("Enter the number :\n");
scanf(" % d",&num);
for (i=2;i<=num/2;i++)
if(num%i==0)
break;
(i>num/2)?((num!=1)?printf("Prime number \n"): printf("neither\n")): printf("not a prime number :\n");}
- Status