Creating Fibonacci Sequence using Recursion and Iteration in python

Today we will try to use python for creating Fibonacci sequence dynamically.

Before directly jumping into code we just want to explain what is Fibonacci Sequence.

In Mathematics Fibonacci numbers are denoted as Fn, form a sequence, called the Fibonacci Sequence, so that each number is a sum of two preceding ones.

F(0) = 0 , F(1) = 1

so F(n) = F(n-1) + f(n-2) [for n > 1]

The sequence starts like below

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

Fibonacci Series

Now lets jump into the python. How do we create this Fibonacci Sequence in python.

For todays topic we will try to write the same function twice.

First with Recursive function and then with iterative loop. And finally we will discuss briefly the advantages and disadvantages of two different approaches.

Now what is recursive function ?

Recursive function is an example of a scenario where the function calls itself again and again to accomplish some job.

Let me give a very simple example. You with all your friends walked into a restaurant at weekend and say you have ordered for 10 plates of Chicken Salads.

When the chef sees the order he understands that he have to make same dish 10 times , so he starts saying to himself “Let me prepare a plate of Chicken Salad” and he needs to keep saying and doing the same thing until he completes the preparation of 10 dishes of chicken salads.

So this is a typical example of Recursive Function. Here the function is preparesalad() and the function will keep calling itself till it is done with all ordered items, in our example it is 10 times.

Now as we are clear with the basic concept of recursion let us directly jump into the python code to frame the Fibonacci Sequence as below -

def fibonaci_sequence(first_no,sec_no,n,ls):
    if (n==0):
        return ls
    if (len(ls) == 0):
        ls.append(first_no)
        ls.append(sec_no)
    temp = first_no + sec_no
    first_no = sec_no
    sec_no = temp
    ls.append(sec_no)
    fibonaci_sequence(first_no,sec_no,n-1,ls)
    return ls
ls = []
#call to Fibonacci recursive function
ls = fibonaci_sequence(0,1,10,ls)

So the output will be as below -

Output of Fibonacci Series generated by Recursive method of python 3.0

Though the code is self explanatory but just to give an idea we have passed 4 input parameters to function ->

1. The first number of Fibonacci Sequence(0)
2. The second number of Fibonacci Sequence(1)
3. No of items we want in series after first and second number
4. The python list in which we want to store the Fibonacci sequence and function will finally return this list at the end of the execution.

We need to keep in mind two key deciding factors when writing recursive function ->

1. Recursive function only we can write for the scenarios where the a big job can be divided into smaller n number of similar tasks.

2. We need to define the termination point of recursive function based on certain condition irrespective of job is accomplished or not. If we do not consider the end of recursive function the function will go to infinite invocations of itself.

Now as I promised I will also share the same function using iterative approach as below -

def fibonacisequence_iteration(first_no,sec_no,n,ls):
   ls = []
   i = 0
   ls.append(first_no)
   ls.append(sec_no)

   while i<n:
       temp = first_no+sec_no
       first_no = sec_no
       sec_no = temp
       ls.append(sec_no)
       i += 1

   return ls
ls = []
#call to Fibonacci Iterative function
ls = fibonacisequence_iteration(0,1,10,ls)

So the output will be exactly same as before -

Output of Fibonacci Series generated by Iterative method of python 3.0

So do you find any difference between two approaches ?

Lot of questions must be coming into your mind ? Why recursive why iterative when recursive and when iterative?

To answer all of that I am just trying my best to put a small quick comparison between two -

Comparison between Recursion and Iteration

Hope all of you have enjoyed the article on Fibonacci Sequence.

Happy Reading!! Happy Coding!!