## Mastering Most Common Interview Question: Fibonacci Sequence

Different companies can have very different emphasis on algorithms during coding interview. Nevertheless, if I had only 10 minutes to prepare for recruitment meeting, I would most definitely spend it on learning recursive version of Fibonacci sequence - it simply turns up the most often. In this post, I am providing you with “transcript” of the first time I was asked to implement Fibonacci sequence algorithm in Python few years ago. Take a look at the way I was thinking out loud and try to mimic this approach during your job interview **even when different algorithmic task appears!**

**RECRUITER: **Can you write a function, which takes a positive integer **n** as an argument and returns **n**-th element of Fibonacci sequence? So, for example for 6 this function should return 8.

**ME:** Sure! Let me start by defining a function you specified. For now it’ll return a placeholder (-1). I’ll just write first few elements of Fibonacci sequence in a comment to have them in mind. As far as I remember, every consecutive element is a sum of the previous two.

def fibonacci(n): # 0, 1, 1, 2, 3, 5, 8, 13, 21 return -1

### I started with **revisiting definition of the problem and small study of an example**, which I wrote in a comment.

I will implement a solution to a simpler problem - writing Fibonacci sequence algorithm for zeroth, first and second element. Actually, we can omit zeroth since you said, that my function should take a positive integer as an argument. So, below solution will produce bad result for **n **larger than 2. Otherwise it’s fine.

def fibonacci(n): # 0, 1, 1, 2, 3, 5, 8, 13, 21 if n == 1 or n == 2: return 1 return -1 # Good result print(fibonacci(1)) # Good result print(fibonacci(2)) # Bad result print(fibonacci(3))

**Simplifying a problem** is an important step towards its further exploration and better understanding. Recruiters love that!

I think I need a visual assistance. I’ll try to dissect an example with **n** = 6. The output should be 8 (8 is sixth element of Fibonacci sequence). But how exactly was that calculated? Let me quickly draw a simple diagram to find that out. Oh, now I see - tree perfectly fits this use case, so I will probably need to use recursion.

### Don’t forget to** visualize examples using diagrams** like charts, trees, graphs or tables.

To implement recursion we need recurrence definition and a termination step. The latter can be defined by looking at leaf nodes of the tree diagram I drew. Oh, the if statement I’ve written for the first two elements is already a termination step! Let me say out loud what I want my recurrence step to look like: In order to calculate a Fibonacci element at **n**-th position I need to take Fibonacci elements from previous two positions and sum them up. In other words, I need to sum Fibonacci elements from position **n **- 1 and **n **- 2, **which can also be calculated using my Fibonacci function**.

def fibonacci(n): # 0, 1, 1, 2, 3, 5, 8, 13, 21 if n == 1 or n == 2: return 1 return fibonacci(n - 1) + fibonacci(n - 2) # Good result print(fibonacci(1)) # Good result print(fibonacci(2)) # Good result print(fibonacci(6))