Common Programming Questions: The Fibonacci Sequence

Generating a Fibonacci sequence is an extremely popular programming question, which might seem intimidating at first but it's actually quite simple.

For those of you boomers who don't know what a Fibonacci sequence is:

In mathematics, the Fibonacci numbers, commonly denoted Fₙ, form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is, and for n > 1.

• Wikipedia

So what we're gonna do is programmatically generate an N length of Fibonacci numbers.

Enter the Fibonacci length: 8
[0, 1, 1, 2, 3, 5, 8, 13]

Visualizing a way to solve the problem

A good approach to solving these questions would be to break 'em up into little tidbits and understanding the problem and then implement that in code. Here, these are the steps

• Get user input for the length of the Fibonacci sequence.
• Set initial values of the sequence. (This is always 0 and 1)
• Create a loop and check if the length of the sequence is equal to the number the user has specified. If it is, then exit the loop. If it isn't generate the Fibonacci number and append that to the list of already generated Fibonacci numbers.
• And finally, print the Fibonacci sequence. But, how in the world do you generate the Fibonacci number??

So if you noticed, Fibonacci numbers are basically the sum of the previous two numbers in the sequence. And if you didn't, well that just sucks. Anyway, what we basically wanna do is

• Access the last two elements of the sequence/list
• Add 'em up
• Append them to the sequence/list

WOAH, so that's it? Yup.
Let's get started coding!

Solving the problem

So, I'm gonna do this in Python, you can choose whatever language you want, the concept is dead simple and you should be able to implement this in any language.

• First, we wanna get the user input, so that's nice & straightforward.

# inp is short for input
inp = int(input("Enter the length of the Fibonacci sequence: "))

• Now we'll create a function that generates the Fibonacci sequence:

inp = int(input("Enter the length of the Fibonacci sequence: "))

def fib(fibonacci_length):
    pass

• We can create a list and populate it with the default values of a Fibonacci sequence:

inp = int(input("Enter the length of the Fibonacci sequence: "))

def fib(fibonacci_length):
    fibonacci_list = [0, 1]

• Now, we're gonna create a while loop which checks if the Fibonacci length is equal to the length of the list fibonacci_list or not.

inp = int(input("Enter the length of the Fibonacci sequence: "))

def fib(fibonacci_length):
    fibonacci_list = [0, 1]
    while len(fibonacci_list) != fibonacci_length:
        pass

• We're now going to access the last two values of fibonacci_list by grabbing their indexes:

inp = int(input("Enter the length of the Fibonacci sequence: "))

def fib(fibonacci_length):
    fibonacci_list = [0, 1]
    while len(fibonacci_list) != fibonacci_length:
        second_last_index = len(fibonacci_list) - 2
        last_index = len(fibonacci_list) - 1

• Now we can append the sum of the last two values of the list to fibonacci_list and print the whole list:

inp = int(input("Enter the length of the Fibonacci sequence: "))

def fib(fibonacci_length):
    fibonacci_list = [0, 1]
    while len(fibonacci_list) != fibonacci_length:
        second_last_index = len(fibonacci_list) - 2
        last_index = len(fibonacci_list) - 1
        fibonacci_list.append(fibonacci_list[second_last_index] + fibonacci_list[last_index])
    print(fibonacci_list)

• And finally, we're gonna call the fib function and pass the user input (inp) variable to the fibonacci_length parameter:

inp = int(input("Enter the length of the Fibonacci sequence: "))

def fib(fibonacci_length):
    fibonacci_list = [0, 1]
    while len(fibonacci_list) != fibonacci_length:
        second_last_index = len(fibonacci_list) - 2
        last_index = len(fibonacci_list) - 1
        fibonacci_list.append(fibonacci_list[second_last_index] + fibonacci_list[last_index])
    print(fibonacci_list)

fib(inp)

Edit

Suggested by @robin-loche, this code can be shortened by making the following changes:

inp = int(input("Enter the length of the Fibonacci sequence: "))

def fib(fibonacci_length):
    fibonacci_list = [0, 1]
    while len(fibonacci_list) != fibonacci_length:
        fibonacci_list.append(fibonacci_list[-2] + fibonacci_list[-1])
    print(fibonacci_list)

fib(inp)

We can use negative indexing in Python to access the elements of the array from the last position. What I mean is

# In this array,
["apple", "lenovo", "asus"]
'asus' -> has the index of [-1]

This greatly reduces the amount code in the loop and I suggest you all to do it this way.

And that's all there is to it!
If you have coded this in a different programming language please share it down below :)
Thanks for reading, I'll catch you guys in my next post!

Comments

[robin-loche]

In python, you could also access the last items of the list using the minus indexes (list[-1] access the last element of the list), especially since you have already 2 items in your list. The inside of the loop would become only:
fibonacci_list.append(fibonacci_list[-2] + fibonacci_list[-1])

[Dhruva Srinivas]

Oh yes, that didn't occur to me, Thank you so much for sharing :)

[Pavan]

The solution you provided runs in O(n) time and can be brought down to O(1) ( which is not much interesting since it is just a closed formula), but the O(log N) is an interesting approach, take a look at it.

I am referring to the calculation of nth fibonacci number

[hidden_dude]

The fibonacci solution is not O(n) because there's no computer that's going to be able to compute operations resulting in a 711 bit number if given a value of 1024 (which has input size 10 in binary).

So it's more correct to say pseudo polynomial.
Even with the "O(1)" approximation formula it won't work in practice because of the huge number of bits these numbers require.

The numbers produced are exponential. And exponential is going to have some serious consequences in practice.