Designing Code for Fibonacci Sequence without Recursion

Fibonacci sequence:

The Fibonacci sequence is a sequence type in which the sum of the previous two numbers is each consecutive number.

First few Fibonacci numbers are 0 1 1 2 3 5 8 …..etc.

Fibonacci sequence without recursion:

Let us now write code to display this sequence without recursion. Because recursion is simple, i.e. just use the concept,

Fib(i) = Fib(i-1) + Fib(i-2)

However, because of the repeated calculations in recursion, large numbers take a long time.

So, without recursion, let’s do it.

Approach:

Create two variables to hold the values of the previous and second previous numbers.
Set both variables to 0 to begin.
Begin a loop until N is reached, and for each i-th index
- Print the sum of the previous and second most previous i.e sum= previous + second previous
- Assign previous to second previous i.e. second previous= previous
- Assign sum to previous i.e previous=sum

Below is the implementation:

1)C++ implementation of above approach.

#include <iostream>
using namespace std;
int main()
{ // given number
    int n = 10;
    // initializing previous and second previous to 0
    int previous = 0;
    int secondprevious = 0;
    int i;
    // loop till n
    for (i = 0; i < n; i++) {
        // initializing sum to previous + second previous
        int sum = previous + secondprevious;
        cout << sum << " ";
        if (!sum)
            previous = 1;
        secondprevious = previous;
        previous = sum;
    }
    return 0;
}

2)Python implementation of above approach.

# given number
n = 10
# initializing previous and second previous to 0
previous = 0
secondprevious = 0
# loop till n
for i in range(n):
    sum = previous + secondprevious
    print(sum, end=" ")
    if (not sum):
        previous = 1
    # initializing value to previous to second previous
    secondprevious = previous
    previous = sum

Output:

0 1 1 2 3 5 8 13 21 34

Related Programs: