How to Use Recursion & Memoization in Ruby

What is recursion in Ruby?

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

Once the base case is reached, the recursion ends, and the functions start returning.

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 & 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:

def iterative_factorial(n)
  (1..n).inject(:*)
end

def recursive_factorial(n)
  # Base case
  return 1 if n <= 1

  # Recursive call
  n * recursive_factorial(n-1)
end

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:

return 1      # recursive_factorial(1)
return 2 * 1  # recursive_factorial(2)
return 3 * 2  # recursive_factorial(3)
return 4 * 6  # recursive_factorial(4)
return 5 * 24 # recursive_factorial(5)

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:

def fib(n)
  return n if n < 2

  fib(n-1) + fib(n-2)
end

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

(1..20).each { |n| puts fib(n) }

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.

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:

@cache = [0,1]

def fib(n)
  return @cache[n] if @cache[n]

  @cache[n] = fib(n-1) + fib(n-2)
end

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.

Example:

memo = []

(0..n).each do |i|
  memo[i] = i < 2 ? i : memo[i-1] + memo[i-2]
end

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 & subscribe to my newsletter 🙂