Recursive Functions vs Iterative Looping

Recursion as a concept is one of those hallmarks of Computer Science that seems to stay in the domain of undergraduate studies. That’s because iterative looping is both straight forward and, depending on the language, more performant. Recursion is rarely the right answer to a problem. That is, until it is precisely the solution that you need to employ, such as in building / parsing tree-like structures. Yet another reason is that while recursion makes reasoning about a problem far easier in the case of say, tree-like data structures, it does make understanding in detail how some function executes more difficult than simply looping. There is a certain amount of trust, a leap of faith some would say, that one must place in the natural recursion to do what you’re mathematically expressing in the function body.

The goal of this little post however, is not to highlight the differences between recursive functions and iterative looping, but to show that they are really more like mirror-images of one another. To do this we’ll take a look at a Computer Science classic – a function which converts decimal numbers to binary form, using JavaScript.

The While Loop Implementation

The looping construct we’ll use is the while loop. I think this is a good choice given our goals of finding similarities between recursion and looping because the while loops makes use of a single Boolean condition for its control flow, which is quite a lot like a recursive functions base case.


function convert(number) {
  let remStack = [],
      rem
  
  while (number !== 0) {
    rem = Math.floor(number % 2)
    remStack.push(rem)
    number = Math.floor(number / 2)
  }
  
  return remStack.reverse().join('')
}

console.log(convert(77)) // 1001101
console.log(convert(2))  // 10

Our convert function takes a decimal number named number as its only argument. It initializes an empty array remStack and a temporary variable of rem. It goes to a while loop which runs so long as number is greater than 0, after which remStack is reversed and joined to form our binary number as output.

For those who can’t recall how binary numbers can be derived from decimal numbers, I’ll give a brief description. To convert a decimal number to a binary representation, we can continually divide the number by 2 (binary is a base 2 number system) until the division result is 0. We push the remainders of such divisions (always a 0 or a 1) on the remStack, which will be reversed and then joined in the final return statement.

Go ahead and play around with a small input number, say, 5, to convice yourself of what’s happening if you need to. I know that I did, especially considering that I lack a Computer Science education.


5 / 2 == 2 rem == 1
2 / 2 == 1 rem == 0
1 / 2 == 0 rem == 1

5 divided by 2 using Math.floor is 2, with a remainder of 1. 2 divided by to makes 1 with a remainder of 0. 1 divided by 2 is 0 with a remainder of 1. Each of these remainders get pushed onto remStack, get reversed and joined to give us the number 5’s binary form of 101.

Let’s now take a look at how to do these same operations with recursion.

The Recursive Implementation


function convert2(number) {
  let remStack = [],
      rem

  function doConversion(number) {
    if (number === 0)
      return remStack.reverse().join('')
    else {
      rem = Math.floor(number % 2)
      remStack.push(rem)
      number = Math.floor(number / 2)
      return doConversion(number)
    }
  }
  return doConversion(number)
}

console.log(convert2(77)) // 1001101
console.log(convert2(2))  // 10

The convert2 function takes in a decimal number via the parameter number. Then, remStack and rem are initialized as an empty array and temporary variable, respectively. The doConversion function trampolines up from the bottom of our convert2 function. A base case is set for when number === 0, the remainders of number are pushed onto remStack, and doConversion is called again with number being halved. Finally, remStack is reversed and joined in the base case termination of the recursion.

Comparing Solutions

Take a moment and compare the recursive and looping solutions. Don’t concern yourself with which one is more elegant or straightforward. Instead notice the similarities between the operations that each perform.

You’ll notice that at their core, the only real difference is that the while loop implementation is constantly watching for a change in the condition that number !== 0 whereas the recursive function considers each recursive call to itself and determines if number === 0.

The most interesting parts of both functions, the parts that actually perform the operation of deriving a binary number from a decimal are actually a one-to-one match. Take a look at both of these function when they are stripped of all parts that they share.

Syntactically shared parts:

let remstack = [], rem
rem = Math.floor(number % 2)
remStacck.push(rem)
number = Math.floor(number / 2)
return remStack.reverse.join('')

Now here’s what the function bodies look like when stripped of these shared parts.

Syntactically different parts:


function convert(number) {
  while (number !== 0) {
  }
}

function convert2(number)
  function doConversion(number) {
    if (number === 0) {
    } else {
      doConversion(number)
    }
  }
  return doConversion(number)
}

Now the only things that are left are the control-flow constructs used in each. I think that stripping both of the function bodies bare like this really lets you see how both recursion and looping accomplish the same thing.

While I won’t deny that recursion takes a conceptual leap in reasoning, there isn’t that much in terms of written code that makes recursion much different from looping.

Conclusion

I hope that this post is useful for anyone who is puzzled by recursion, and that it helps to lower any inhibitions with using recursion in their programs. To many people, the observations in this post are obvious, but for just as many others, distilling the details of implementing a simple function as we did in this post with two different methods can really help in comprehension.