Recursion Made Simple with Roman Numerals
A procedure is recursive if it invokes itself. Thus:
// ES6
const 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.
The Bad
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 aribify2and 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.
