Mar 11, 2021
Recursion, Fibonacci, and Speed with Ruby
The Fibonacci sequence is a sequence of numbers where the next number in the sequence is the sum of the previous 2 numbers. It is typically illustrated like this:
In this blog, I’ll be dipping my toes into the basics of how recursion works. I’ll implement two different solutions in Ruby to find the element of the Fibonacci sequence specified. The first solution is more standard coding practice while the second uses a more elegant, recursive solution to do the job.
The first solution takes in a number n, and creates a Fibonacci sequence from the beginning all the way up to the element we are looking for:
This method is straight forward and fast. It starts with two variables as 1, then adds them together to make a third variable, and then shifts the third variable into the second, and the second into the first. It does this over and over until we extract the value we are looking for.
The second solution uses recursion to achieve the same result:
This method is much less code than the first, and appears much more elegant. A number n is passed into the method and is checked whether it is greater than 2 or not. If it is not greater than 2, it encounters the so called “base case” of the method which returns the value 1. If it is greater than 2, it calls itself with one less than n and adds that value to itself called with 2 less than n. This recursive loop runs until n reaches the base case and eventually returns a value.
To help visualize what is happening in this method, see the following professional diagram:
To find out which method was faster, I benchmarked the results:
Which method is actually faster? Here:
The non-recursive solution is exorbitantly faster. Recursion does seem to do magic work in the function, however in this instance is not the best method to solve the problem. Recursion is a mind numbing topic, and it helps immensely to sketch out what is happening to wrap your head around it.
