One of the, if not the most commonly asked question during a technical interview for many programmers involves the Fibonacci Sequence. Why you ask? Because the Fibonacci Sequence is a great test of the programmer’s understanding of recursion, function calls, variables, the stack and many other key concepts that any good programmer should know.
That being said, you will more likely than not be asked this question
Using recursion, find the nth element within the Fibonacci Sequence
In this article, I will actually cover two separate methods to solve this problem, with recursion and iteration.
Recursion
It’s important to understand at a very basic level what recursion is. Recursion is essentially a function calling on itself. To achieve the expected end-result for this problem, we will be utilizing tail recursion which means that the calling function does not make computations after making a recursive call.
Line by line, first, we define our function that accept a parameter: the index within the Fibonacci Sequence that you are trying to find. We set two cases for this function, a base case and a recursive case.
The base case ensures that the program has a condition so the function doesn’t run infinitely causing a stack overflow. The recursive case will continuously run until the base case is met.
Essentially, this is how the recursive function will run and evaluate the argument you pass in. Each time you make a function call, memory is allocated to it within the stack storing different copies of the local variables for each call. Once the base case is reached the function will return the value to which it is being called until we return to the very first function call.
Now that we’ve covered the recursive approach, let’s take a look at the interactive approach.
Iteration
There is a saying that “anything that can be done recursively can also be done through looping”. Iteration can be done in a variety of methods including, do, while, until and for loops.
In this iteration example we have 3 variables. In order to get the value of the index, that number is obtained by adding the previous two numbers. We set i=2 in the for loop because thinking back to the first 3 numbers within the Fibonacci Sequence, the value at index 2 is 2.
Thus, in the first iteration of the for loop, we are creating the initial 3 numbers within the Fibonacci Sequence. With each iteration, we set each variable to the corresponding values until we reach the index. Upon hitting the index, we return the value at that index.
Conclusion
While this is a commonly asked interview question, it’s best to know the different approaches you can take to reach the same solution. It’s important to give the interviewer the solution using the method they ask of you, but showing them that you are able to use different methods can go a long way.
I hope this has been an informative article!
