Designing Code for Fibonacci Sequence without Recursion
What’s a Fibonacci sequence:
Fibonacci sequence is a kind of sequence in which every subsequent number is sum of the previous two numbers i.e.
Designing Code for Fibonacci sequence:
Now let’s write a code to display this sequence but without recursion. Because with recursion it easy i.e. just use the concept,
F(i) = F(i – 1) + F(i -2)
But it takes a lot of time for large numbers because of repeated calculations in recursion.
So, let’s do it without recursion.
Algo to create a Fibonacci sequence of N numbers without recursion:
- Create 2 variables that will store the value of last and second last number.
- Initialize both the variables with 0.
- Now start a loop till N and for every i-th index,
- Print Sum of last and second last i.e SUM = LAST + SECOND_LAST
- Assign last to second last i.e. SECOND_LAST = LAST
- Assign Sum to last i.e. LAST = SUM
Let’s see the code,
void fibonacci(int n)
int last = 0;
int secondLast = 0;
for(int i = 0; i < n ; i++)
int val = last + secondLast;
last = 1;
secondLast = last;
last = val;