Recursion Made Simple with Roman Numerals

A procedure is recursive if it invokes itself. Thus:

`// ES6const toInfinityAndBeyond = num => toInfinityAndBeyond(num + 1);`

Of course, `toInfinityAndBeyond` is only useful if, rather than seeking an answer, you want to blow your call stack. But you see the point: we find `toInfinityAndBeyond` in its own body. What possible use could this be?

Recursion is often well suited to express the logic of a problem. Let’s take a simple problem: the conversion of Roman to Arabic numerals. One solution is this one:

We might be interested in solving this problem differently for a number of reasons, perhaps to avoid the pitfalls that go along with complex regular expressions, or because we want to avoid mutating variables. Most relevant for our purposes is the `key` object. Note how it includes not only `M:1000`, but also entries like `CM: 900` and `IV: 4`. This hard wires crucial logic rather than expressing it.

A First Stab

Recursion gives us a more expressive way to approach the problem, one that allows us to use a single pure function that does not mutate variables. Here is a first stab:

This has the benefit of expressing the logic of converting valid (or even some invalid!) Roman numerals to Arabic numerals, but it has some problems as well. Let’s consider the good before the bad.

The Good

In the first place, we are not using variables or complex regular expressions. More to the point, in our `nums` object, we have no need of shortcuts like `IX: 9` or `CM: 900` — our program handles this for us. How?

The function `arabify` takes a string, which we are assuming to be valid Roman numerals. If that string is empty, it simply returns 0. An empty string is our base case, the point at which `arabify` stops calling itself. Without a base case, the `arabify` calls will just keep piling up on the stack until there is a stack overflow.

If the string passed to `arabify` is not empty, we must determine the relation of the first two characters. If the first character is less than the second character — `nums[romNum[0]] < nums[romNum[1]` — we know that the former should be subtracted from the latter. That is, if `X` represents `10` and `C` a 100, then `XC` is `90`.

Why in the case where the first two characters require the first be subtracted from the second do we need the call again to `arabify`? Because we could have a case like `XCII`, where we not only need to subtract the first item from the second, but the result must be added to the remaining numerals.

If the first numeral is not less than the second numeral, the solution is straightforward: add the first numeral to the value of the rest. We can simply call `arabify` on the remainder of the string from Roman numerals to find that value.

One downside to `arabify` is that it’s not the most readable. Wouldn’t it be nice if instead of having to parse things like `nums[romNum[0]] < nums[romNum[1]`, we could have `nums[fst] < nums[snd]` instead?

The second problem is unlikely to arise in this particular context, but pointing it out is useful. The calls to `arabify` are going to keep piling on the call stack until the base case is reached — an empty string, then each call can be evaluated and the final answer returned. This means that `arabify` will consume memory roughly proportionally with the size of the string passed in as an argument.

Fortunately, the ES6 spec now includes tail call optimization. For recursive calls in the tail position, the function calls need no longer pile up on the stack. Let’s take a second stab at `arabify` that makes this clearer.

Tail Call Optimization

`arabify2` uses tail calls and is a bit easier to read.

On line four, we use ES6 destructuring to so that we can say `fst` rather than `romNum[0]`, `snd` rather than `romNum[0]`, and `rest` rather than `romNum.slice(2)` or `romNum.slice(1)`.

Note the difference between the recursive calls to `arabify2` in comparison to `arabify`: we don’t make a call to `aribify2`and then do something else with it. `aribify2` uses the parameter `sum` to keep track of all the information it needs. There is no reason to ‘remember’ the previous `aribify2` calls: the last call returns the result we are looking for.