Black Bytes
Help more people learn by sharing this post!

Recursion and Memoization in Ruby

Have you ever wondered if there is an alternative to iteration? Well I have good news for you: there is, and it’s called recursion.

Recursive functions are those that keep calling themselves until they hit an end goal (also known as the base case). The idea is that after each function call we make some progress towards this base case, reducing the amount of work left to be done.

Once the base case is reached, that’s the end of the recursion, and the functions start resolving.

Ruby Recursion

A classic example to start learning about recursion is calculating a factorial number, let’s see how we can do this in Ruby using both iteration and recursion.

To calculate the factorial of a number we have to multiply all the numbers from 1 to our target number. For example, the factorial of 5 is: 1 * 2 * 3 * 4 * 5 = 120. Let’s see how we can do this using Ruby and recursion.

Example:

In this example I show you two ways to calculate a factorial number. The iterative and the recursive solution.

In the recursive solution we make progress by decreasing the number we are working with (n-1). Once (n <= 1) there are no more recursive calls, and this is what happens:

As Ruby developers we go for the iterative solution most of the time, and that’s great, but I think it’s still worth knowing how recursion works. Now let’s see another classic example: fibonacci numbers.

The Fibonacci Sequence

Leonardo Fibonacci discovered this sequence when investigating how to model the growth of rabbit population under ideal conditions. The sequence is calculated by adding up the two numbers that came before the current one.

Example:
1, 1, 2, 3, 5, 8, 13, 21

To calculate this in Ruby you can use a recursive function:

Using this function and a range you can easily calculate the first 20 Fibonacci numbers.

However, there is a problem:

Your function is doing a lot of extra work that it doesn’t need to. To illustrate this, look at the following image.

ruby recursion

In the image we can see how fib(3) is calculated five times. This makes your function really slow if you try to calculate longer Fibonacci sequences. The solution? Memoization.

Memoization: Reusing Work We Have Already Done

Wouldn’t it be great if you could just reuse the work you have already done in previous steps? We can do that using memoization.

To save our expensive calculation results we use a cache. In this case, an array will do.

Example:

First we check to see if the result is already in the cache, if it is then return it, otherwise we do the calculation and save the result.

This will run a lot faster and it will be able to calculate much bigger Fibonacci numbers.

The Limits of Recursion

As a reader kindly pointed out, the recursive solution can fail with SystemStackError: stack level too deep with big input numbers (around 7500, exact number depends on your system). If you need to calculate an even bigger number you would have to use an iterative solution.

Conclusion

Recursion is great but sometimes it can be hard to grasp. Now it’s your turn, practice makes mastery! Please share this post if you like it :)

6 comments
jonathonjonesphilosophy says last year

I wonder whether the array version or a hash version would be faster/less resource intensive. Would this code be better or worse?

By the way, I like that your way of setting this up just adds the basic version to the variable, so that it is unnecessary to write “return n if n < 2” at the top of the function.

    Jesus Castello says last year

    I would say using a hash here doesn’t provide any benefits since we aren’t scanning the array, we are accessing the index directly. That’s a constant time operation, so it doesn’t get much better than that.

splattael says last year

I like your solution! It’s very similar to the “hash” version:

Micah Buckley-Farlee says last year

This will run a lot faster and it will be able to calculate much bigger Fibonacci numbers.

Unfortunately, this is not the case, because of a key limitation in Ruby – the lack of tail call optimization. On my vanilla 2.1.5 build of Ruby, the highest number I can run your recursive, memoized solution of fibs with is 7685 before I get a SystemStackError: stack level too deep

    Jesus Castello says last year

    Thanks for pointing that out, I was aware of the issue but wasn’t sure how to put it into words. I ran some tests and it seems like the stack size is always the same on every machine. On a Linux VM the ulimit parameter for max stack size didn’t seem to have an effect.

    I used this code to find the maximum number that can be calculated recursively:

    (0...99999).each { |n| fib(n); p "Calculating fib #{n}"; @cache = [0,1] }

Guess What? (@kofno) says last year

You can actually turn TCO on in ruby, if you are so inclined. That would make it possible to write the recursive example w/out eating up stack: http://nithinbekal.com/posts/ruby-tco/

Comments are closed

Popular posts

11 Ruby Tricks You Haven’t Seen Before
 Programming
Jan 18, 2016
The Ultimate Guide to Blocks, Procs & Lambdas
 Programming
Feb 02, 2016
Building Your Own Linux Tools with Ruby: A Practical Guide
 Programming
Jun 27, 2016
Mastering Ruby Arrays
 Programming
May 06, 2015