February 27 2017

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