I am a graduate of a coding bootcamp, and throughout my career as a dev I have noticed some definite comp sci degree-sized gaps in my knowledge. Certain concepts and design patterns and data structures that didn’t get covered in the brief time I was in bootcamp, nor in the following time spent learning on the job, when building web apps full time in Ruby on Rails. But you hear about them, other developers throw their names around or they are mentioned in articles or blog posts, and you realise that a wider understanding of these things will help you to become a better programmer.

So I am spending time now to upgrade my knowledge and learn about these things, filling those gaps as best I can.

One of these concepts is recursion, something I keep coming across but haven’t used very much. I think due to using Ruby as my primary programming language, I tend towards iteration to solve the problems for which other, particularly functional, languages would turn to recursion.

For instance, to write a method that takes an integer n and returns the nth number in the much beloved Fibonacci sequence, I would write something like this:

def iterative_fib(n)
fib_array = (1..n).inject([0, 1]) { |arr| arr << arr.last(2).sum }
fib_array[n]
end
As we can see, we have an array fib_array that starts with [0, 1] and then in the block, shoves the sum of the last two numbers in the array onto the end, as many times as 1..n. It concludes by returning the value in fib_array at index n. So if n is 5, the fib_array would end up as [0, 1, 1, 2, 3, 5] and the return value would be 5. To prove that this method does what it’s supposed to, I wrote this test:

describe '#iterative_fib' do
it 'should return the correct number in the Fibonacci sequence that corresponds to the index of the n argument' do expect(fibonacci.iterative_fib(0)).to eqexpect(fibonacci.iterative_fib(2)).to eq 1
expect(fibonacci.iterative_fib(5)).to eq 5
expect(fibonacci.iterative_fib(10)).to eq 55
expect(fibonacci.iterative_fib(20)).to eq 6765
end
end

It passes – I imagine I could keep adding expects for all entries in the sequence and it would continue to pass.

When turning to recursion, I read the very helpful ‘How to Use Recursion and Memoization in Ruby’ in the Ruby Guides. Basically, recursion is a function that calls itself until it reaches its end goal, and then returns a value.

The recursive method to solve the same Fibonacci sequence problem as above is:

def recursive_fib(n)
return n if n < 2
recursive_fib(n - 1) + recursive_fib(n - 2)
end


I tested this method with the spec used for the iterative method, and it also passed.

Here’s how we get the return value from the line recursive_fib(n - 1) + recursive_fib(n - 2):

I like to think of the results of each recursive call creating a sort of tree. Let’s say that n is 5. So 5 is the top of the tree, and it works down with each call on itself until the guard clause is reached and the process stops for each side. The final result will look something like this:

We end up with all of those 0s and 1s across the bottom, and it is through summing these together that we get our return result.

We can see on one side of the tree, stemming from the 4, that the sum is 3. And on the other side, we end up with 2.

So after all is said and done, recursive_fib(num - 1) + recursive_fib(num - 2) resolves to 3 + 2, and thus returns 5, which is the correct value from the Fibonacci sequence.

It helps to understand that the guard clause at the top of the method only evaluates to true within the internal calls on itself, never at the top level.
It can be useful to visualise what is going on in the code in order to fully understand it. I ended up drawing the tree structure out on paper in order to see more clearly what was happening in each of those recursive calls.

As an aside, some languages have something called tail call optimisation, but Ruby doesn’t. This means that at some point, the method will fail with SystemStackError: stack level too deep it depends on your machine, but it’s generally when a really big number is passed in as n. In order to get the solution for a large number in the Fibonacci sequence in Ruby, you’ll need to use an iterative method like the one at the top of this page.