The Startup
Published in

The Startup

Fibonacci Sequence on Python

from time import sleep
fibonacci = [1,1]
while True:
first = fibonacci[-2]
second = fibonacci[-1]
sum = first + second
fibonacci.append(int(sum))
print(sum)
sleep(0.05)

In this code, I want to show you 2 ways of coding the Fibonacci sequence in python. 1 way is as shown above which I intend to use to also teach you list indexing or the shorter way below which makes use of recursion:

def Fibonacci(x,y):
print(x+y)
Fibonacci(x+y,x)
Fibonacci(1,1)

I will go through both programs line by line so lets begin! Firstly, in the first program I make use of the sleep method in the time module because it seemed impractical to let the computer run through this code by itself as it would iterate through the first few numbers too fast so I have imported the sleep method so we see the results. If that isn’t a concern to you, then you can delete the first line and also the sleep(0.05) line.

Since I want to use the lists to solve this problem I first initialise a list which holds the first 2 values of the Fibonacci sequence which is 1 and 1. We will index from this list to calculate the next value in the sequence. Having 1,1 in between [] tells python that this is a list.

I then use the loop ‘while True:’ to infinitely iterate through the list. I say True rather than assigning a variable as it is more common to do it this way. Moreover, in larger programs, if you have variables to handle the infinite loop, you may accidentally replace the value of the variable later in program which may break the code so we use the boolean True which isn’t assigned to a variable. This also means that the only way to get out of this loop would be to use the break method.

first = fibonacci[-2]
second = fibonacci[-1]

The first 2 lines in the while loop take the last 2 values of the list. So the variables call the fibonacci list and [-2] would go to the list and take the second data going from the end of the code backwards(so the second to last value), this is known as indexing. Second then takes the very last value. Other examples of indexing would if

Greeting=”Hello World” ; print(Greeting[0]); print(Greeting[3]); print(Greeting[5]); print(Greeting[-3])

this would return H, l, , r. Please not that when reading from the front of strings, you start with 0 rather than 1 which is what you would intuitively start counting from so the H is the 0th value and then e is the 1st value according to index rules.

sum = first + second
fibonacci.append(int(sum))
print(sum)
sleep(0.05)

We assign a new variable called sum to be the sum of the last 2 values of the list(effectively the next value of the Fibonacci sequence). You may be considering why I didn’t just put this inside the append program; however, python doesn’t allow you to index when inside another method so you have to do it separately.

The append line adds the value of the we have computed onto the end of the Fibonacci list, this means after the first iteration sum = 1+1 = 2 so this line would append 2 onto the end of the Fibonacci list giving us the new list of [1,1,2], this is important as now, when we next iterate through the list, the new last and second to last values are 1 and 2 which continues the sequence. The int around the sum in this line isn’t particularly necessary, it makes sure that the sum variable is an integer; however, I always want to make sure my variables are the correct data type so I leave it there just incase.

I then print the sum so the end user actually gets to see the next value of the sequence rather than having to call the list themselves on the run time environment. The sleep is then used to slow down the program although it isn’t necessary if you want to crank up the speed and see how fast your computer can calculate numbers. The 0.05 represents 0.05s of time where Python will stop for until it continues running through the code. After this line it will go back to the beginning of the while loop and iterate through it again.

def Fibonacci(x,y):
print(x+y)
Fibonacci(x+y,x)
Fibonacci(1,1)

This next method is the more efficient method as it uses recursion. However, I want to warn you straight away that after some iterations, your Python will run into an error to do with a recursion limit. It will look like this:

RecursionError: maximum recursion depth exceeded while calling a Python object

So if you want to get the highest possible number, the first method would be the better choice. This makes use of a basic function which I’ve called Fibonacci where I’ve passed in 2 parameters x,y. In function logic, we pass in variables into the function so that variables distinguish from local and global variables but that is an entire other topic to write about. The function will first print the sum of the 2 integers passed in which would be the Fibonacci sequence and then it will run the recursive attribute of the function. It will call itself but rather than passing in the same 2 variables to before, this time it will pass in the sum (x+y) and also the last value of the current sequence. This would iterate through the function with new values every time creating a new Fibonacci sequence.

Now that we have made the function, we need to run through the function so I call the function on the last line and pass in the 2 parameter values of 1,1 which represent the first 2 values of the Fibonacci sequence. Not that when you pass variables like this, they are immediately assigned to the variables of the parameters in the function respectively. So x=1, y=1 and if we did Fibonacci(2,3) x=2, y=3. This is the logic behind the recursive method!

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store