# Algorithm to Generate Fibonacci Sequence.

In this guide, we are going to learn the algorithm to generate the Fibonacci sequence in step by step. Fibonacci numbers are the numbers in the following integer sequence.

The first few Fibonacci term are,

`0,1,1,2,3,5,8,13,...`

Each term beyond the first two is derived from the sum of its nearest predecessors.

### Algorithm development:

From the definition we are given that:
New term = preceding term + term before preceding term
The last sentence of the problem statement suggests we may be able to use the definition to generate consecutive term (apart from the first two) iteratively.
Let us define:

a) As the term before preceding term
b) As the preceding term
c) New term

Then to start with we have:

``` a := 0         first Fibonacci number
b := 1         second Fibonacci number
c := a+b      third Fibonacci number (from definition)```

When the new term c has been generated we have the 3rd Fibonacci number. To generate fourth or next Fibonacci number, we need to apply the same definition again. Before we can make the next computation we need to make some adjustments. The fourth Fibonacci derived from the sum of the second and third Fibonacci numbers. With regard to the definition the second Fibonacci number has the role of term before the preceding term and the 3rd Fibonacci number has the role “preceding term” therefore, before making the next computation we must ensure that:

a) New term (i.e.) assumes the role of the preceding term,
b) And what is currently the preceding term must assume the role of the term

before the preceding term.
That is,

```a := 0   [1]    term before preceding term
b :=1    [2]    preceding term
c := a+b [3]    new term
a := b   [4]    term before preceding term becomes preceding term
b :=c    [5]    preceding term become new term.```

After making step [5] we are in position where we can use the definition to generate the next Fibonacci number. A way to do this is to loop back to step [3]. Further investigation of steps [3]->[5] indicates they can be placed in a loop to iteratively generate Fibonacci numbers (for n>2). The essential mechanism we could use is:

```a := 0;
b := 1;
i :=  2;
while i<n do
begin
i := i+1;
c := a+b;
a := b;
b := c
end```

### Algorithm Description

1) Prompt and read n, the number of Fibonacci numbers to be generated.
2) Assign first two Fibonacci numbers a and b.
3) Initialize count of the number generated.
4) While less than n Fibonacci numbers have been generated do

1. Write out next two Fibonacci numbers;
2. Generate next Fibonacci number keeping a relevant.
3. Generate next Fibonacci number from most recent pair keeping b relevant for next computation
4. Update count of numbers of Fibonacci numbers generated, i.

5) If n even then write out last two Fibonacci numbers else write out second last Fibonacci number.

Anwar Yakkiparamban

Anwar Yakkiparamban is the founder of Lauyou Learning. Prior to Lauyou learning, Anwar worked at ARD Engineering & Development, Qatar. He holds bachelor degree in Electronics and Communication Engineering from Govt. Engineering College Idukki.