# 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!

### 6 thoughts on “How to Use Recursion & Memoization in Ruby”

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

```@cache = {0 => 0, 1 => 1}

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

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

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.

• 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.

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

``````fib = Hash.new { |cache, n| cache[n] = fib[n - 1] + fib[n - 2] }
# prefill
fib[0] = 0
fib[1] = 1
fib[23] # => 28657
``````
3. 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`

• 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] }`