Recursion vs Iteration: Different Approaches to Problem Solving

This article was co-authored by Benjamin Calace and Guillermo Caserotto, members of the Whitespectre Node.JS team.

Here at Whitespectre we started a new series of “code challenges” for the team a few months ago- each a short programming ‘puzzle’ with many possible solutions. Anyone on the engineering team can participate and each one can be solved in either Ruby or JavaScript, but without using external libraries.

In one of our most recent challenges, the key debate was whether to use a recursive vs. iterative approach. Coincidentally, we were also working on a custom DSL initiative for one of our client partners, where a lot of the interesting technical challenges could be solved either iteratively or recursively. So it occurred to us to share some thoughts regarding these two approaches.

First we’ll share the code challenge and some ways to solve it. Then we’ll cover some of the issues that we faced during the custom DSL project and the solutions that we came up with there.

The Code Challenge

Given a positive number, sum up all the digits. If the result has more than one digit, keep repeating the process until you only get a one digit number.

25 => 2+5=7
456 => 4+5+6=15 ==> 1+5=6
321423 => 3+2+1+4+2+3=15 ==> 1+5=6
6528765 => 6+5+2+8+7+6+5=39 ==> 9+3=12 ==> 1+2=3

We ended up with a lot of solutions… mainly with two approaches, iterative and recursive.

Here is the solution:

First let see a pseudo code. For example, we have the number 456:

We need to get the digits: 456 => [4,5,6]
Then, compute the sum of this digits: [4,5,6] => 15
Is the sum a one digit number?
Yes: We’re done, print the sum.
No: Do it again with the new number obtained in step 2.

Iterative Approach: Ruby

Get the digits with the .digits method to get an array of digits.
Then use the .sum method to get the sum of an array.

For example:

num = 241
num.digits => [2,4,1]
num.digits.sum => 7

Then loop over if the sum has more than two digits.

loop do
 num = num.digits.sum
return num
if num.digits.size < 2
end

Here is the complete solution:

def sumDigits(num)
return 0 unless num.respond_to ? (: digits)
loop do
 num = num.digits.sum

return num
if num.digits.size < 2 endend

Ruby made it very easy to solve the sum of the digits with those methods.

Recursive Approach: JavaScript

In order to get the sum, first we need to create an array with the digits:

const int = 1234;
int.toString().split(''); // => [1,2,3,4]

JavaScript doesn’t have a .sum method. So we need to use another method to sum up all the digits.

We could start doing it with an imperative implementation, iterating through the array and keeping an accumulated value:

const int = 1234;
const digits = int.toString().split('');
let sum = 0;
for (let i = 0; i < digits.length; i++) {
 sum += digits[i];
}
console.log(sum); // => 10

Another way is using Array.reduce() to compute the result by subsequently adding the first element to the rest and, thus, achieve recursive thinking. This thought process can be extended to picture summation as performing a sequence of operations in the following manner.

sum[1, 2, 3, 4] = 1 + sum[2, 3, 4] // => 10
sum[1, 2, 3, 4] = 1 + 2 + sum[3, 4] // => 10
sum[1, 2, 3, 4] = 1 + 2 + 3 + sum[4] // => 10

So, using Array.reduce() we could get the sum.

const sum = int.toString().split('').reduce((acc, number) => (acc += parseInt(number)), 0);

The other part of the solution involves calling the function recursively.

If the sum has two digits, call the function again with the new value.

if(number > 10) return sumDigits(number);

So, here is the complete solution:

function sumDigits(int) {
 const result = int.toString().split('').reduce((sum, number) => (sum += parseInt(number)), 0);
 if (result > 10) return sumDigits(result);

 return result;
}

This function will recursively sum up all the digits, for example, if we have 321423.

sumDigits(321423) // will do two sums
[3,2,1,4,2,3] => 15 // has two digits, so, do it again
[1,5] => 6

Surprisingly (or not) this code challenge ended up with these two main approaches, and between Ruby and JavaScript, and guess what, it was a tie! In other words, each approach is valid; and there is sometimes little to choose between the two. In specific circumstances, there may be a more marked difference between readability/maintainability and/or performance.

DSL Translation

At the same time, we had had a similar ‘debate’ happening in a project for one of our client partners that involved a custom DSL. The idea was to be able to translate an object into a valid Elasticsearch query. The issue however, was more on how we would “traverse” the object, since its depth wasn’t fixed.

For example, we’d want to be able to iterate all properties in an object such as:

{
   "OR": {
     "name": "Blue Sweater",
     "AND": {
       "color": "blue",
       "type": "sweater"
     }
   }
 }

Since we have no way of initially knowing how deep the object was (the request itself could contain an unlimited number of nested “OR” and ”AND” clauses), our initial approach could be to go with a recursive function, which would treat each “OR” / ”AND” values as separate requests:

Another possible approach could be based on the fact that pretty much any recursive solution can be made into an iterative one using a stack:

const dsl = req => {
     const stack = [req];
     while (stack.length > 0) {
     const top = stack.pop();
     for (const [key, value] of Object.entries(top)) {
         if (key === 'OR' || key === 'AND') {
            stack.push(value);
     } else {
            // do something with the value
            console.log(value);
     }
   }
  }
};

Both solutions would end up doing the same thing: iterate through the object’s keys, and if there’s an “OR” / ”AND”, either iterate again, or save in a stack for later. Otherwise, just log the value. However, both implementations have their own pros and cons. If it’s a small function like this one, or if there’s the possibility that the object is extremely large, then probably the iterative one would be preferable, since there’s much less memory limitations. Otherwise, the recursive solution may be preferable, since it’s much less bug-prone, and probably just easier to read.

In our case, since we knew we would have to add many more conditions on this same function (since there are a lot of edge cases to consider on Elasticsearch), we opted for the recursive approach. Also, there really wasn’t a real possibility that the object was so large that we’d get an overflow.

Another similar case we found on the same project, was the need to convert a string like key1.key2.key3 into an object like:

{
   "key1": {
     "key2": {
       "key3": {}
     }
   }
 }

The Iterative Way

const createNestedPath = key => {
     let curr = {};
     const root = curr;
     const keys = key.split('.');
     for (const splitKeyofkeys) {
     const nestedChild = {};
     curr[splitKey] = nestedChild;
     curr = nestedChild;
     }
     return root;
}

The result is as expected:

{
   "key1": {
     "key2": {
       "key3": {}
     }
   }
 }

The Functional Way

We needed to create an object for each key that we had.

Using reduceRight(), it starts from the last item in the keys and works its way out to the outer object.

For example, having an array of keys

const result = key.split('.').reduceRight((obj, key) => ({
 [key]: obj
}), {});

result is the same as above:

{
   "key1": {
     "key2": {
       "key3": {}
     }
   }
 }

As we can see we can use both approaches, iterative or recursive.

So, to sum up, we hope we’ve demonstrated that when it comes to recursive vs. iterative, there really isn’t a way to say one is universally better than the other. Instead, it depends on each particular use case and what your team considers to be more important for that particular issue.

For some cases, it can be better to use recursion (for example, when dealing with complex structures) because the resulting code is clearer and more readable. However, since it uses more memory because of the extensive use of the call stack, performance can take a hit- which may make it not suitable for your use case. The important thing is to take these different aspects into consideration as you plan your approach.