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.

0,1,1,2,3,5,8,13,21,34,55,89,144

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

[showads ad=inside_post]

Let’s see the code,

#include <iostream>

void fibonacci(int n)
{
	int last = 0;
	int secondLast = 0;
	for(int i = 0; i < n ; i++)
	{
		int val = last + secondLast;
		std::cout<<val<<",";
		if(!val)
			last = 1;
		secondLast = last;
		last = val;

	}
}
int main()
{
	fibonacci(20);
	std::cout<<std::endl;
	return 0;
}