# Recursion and Iteration

While iterative constructs are well understood by programmers in general, it is not uncommon to stumble upon difficulties when dealing with recursion, but did you know that **every recursion can be turned into an iterative process (and vice versa)**?

In this series of posts, we’ll explore how we can map recursive processes to their iterative counterparts as well as the pros and cons of each approach.

For this first post, we’ll start with a brief introduction and then proceed by studying **simple recursion**.

## Definitions and Scope

Before we begin it is helpful to establish a few definitions and the scope we’ll be dealing with.

First of all, I’ll handle this subject from the perspective of **imperative** languages only (e.g. C++, Java, Javascript, C#, etc), and I’ll do this for two main reasons:

- When using languages that are
*REALLY*functional (sorry, but*lambdas, map, filter, reduce*aren’t enough to make your language functional) you**must**use recursion, as there are no loops or other iterative constructs. - I have very little experience with functional languages.

Also, for the sake of simplicity and readability, I’ll be dealing with **pure functions** only, that is, those functions that have **no side effects** and only read and write from/to **local variables** (excluding *out* parameters), which means that they will **always** yield the same result given the same input.

With these considerations out of the way, let’s start by making a distinction between **recursion** and **iteration**:

- Iteration -> Any kind of
**loop**, like`for`

,`while`

and even the outcast`goto`

. - Recursion ->
**Functions**that call**themselves**, either directly or indirectly.

Example:

```
function recursiveFactorial(n) {
if (n === 0) {
return 1;
}
return n * recursiveFactorial(n - 1);
// This function calls another instance of itself
}
function iterativeFactorial(n) {
let result = 1;
for(let counter = 1; counter <= n; counter++) {
// This function uses a loop to calculate the result
// and has no reference to itself
result *= counter;
}
return result
}
```

Both functions above are equivalent from an **extensional** perspective, that is, given the **same input** they will always yield the **same output**, so from the point of view of the caller, these functions are essentially the same.

However, from an **intensional** perspective, they are different, as their implementation differs.

Note that if we think about recursion naively we might be tempted to think that it is a never-ending process given that a recursive function depends on another instance of itself, which in turn depends on yet another instance of itself and so on until the end of time.

However, there’s a crucial element in this setting, that we call the **base case**, which is the instance of the recursive function for which it is well defined and doesn’t depend on another instance of itself.

In the **factorial** function the **base case** is **0**, as we can see above.

## Simple Recursion => Iteration

There are two broad recursion classes: simple and multiple.

Functions that make use of simple recursion are the ones that reference themselves only a single time (per return statement).

Multiple recursion, on the other hand, allows functions to reference themselves **multiple** times in a single return statement.

As we already mentioned, in this post we’ll be focusing solely on **simple** recursion.

### Recursion with a single argument and a single base case

We’ll see how we can turn a recursion that has a single argument and base case into an iterative process.

Here’s a generic recursive function with the aforementioned properties:

```
function f(argument) {
if(argument === baseCase) {
return baseValue;
// These variables are not defined
// in this context as they are mere
// placeholders, and may be substituted by
// any value
}
return h( f ( g(argument) ) );
// Yet again, these functions are not defined
// as we intend to represent a general
// recursive function, the only constraints for
// these functions is that both "h" and "g"
// cannot reference "f".
}
```

I know the definition above might seem a little bit out of the blue, but I promise that in no time it will all make sense.

First, let’s analyze what happens when we call `f`

with some `argument`

:

If `argument`

is the **base case**, then `f`

return the **base value**, otherwise it will **transform** the `argument`

with `g`

, and then call `f`

with `g(argument)`

, and at last the result of `f(g(argument))`

is fed to `h`

.

Now we’ll have to evaluate `f(g(argument))`

, where yet again we have the same two possibilities, either the argument (which is now `g(argument)`

) is the **base case**, or not.

If `g(argument) === baseCase`

, then `f(g(argument))`

evaluates to `baseValue`

, and then we can resolve the first application, that yields `h(baseValue)`

.

Now suppose that `g(argument)`

is **not** the **base case**, so we’ll have to evaluate `g(g(argument))`

.

Did you notice what’s happening here?

Each time the **current** argument of the **current** instance of `f`

fails to be the **base case**, we “stack” another application of `g`

over the `argument`

and also “stack” another application of `h`

over the overall result.

Still confusing? Let’s go back to the factorial function and fit it within our general recursive function “mold”:

```
function recursiveFactorial(n) {
// Here "f" is the "recursiveFactorial" function
// and "argument" is "n"
// 0 is the "baseCase"
if (n === 0) {
// 1 is the "baseValue"
return 1;
}
// The function "g" is equivalent to
// the n - 1 operation and "h" is
// equivalent to the multiplication operation
return n * recursiveFactorial(n - 1);
}
// Equivalently
function recursiveFactorial(n) {
const baseCase = 0;
const baseValue = 1;
if (n === baseCase) {
return baseValue;
}
return h(n, recursiveFactorial(g(n)));
}
function g(n) {
return n - 1;
}
function h(n, m) {
// In this case "h" is a binary function,
// however we can easily generalize "h"
// to have an arbitrary arity, so long
// we only pass a single instance of
// "f" as an argument to "h", in order
// to avoid multiple recursion
return n * m;
}
```

Any time we call `f`

with an argument that is **not** the **base case**, it won’t be able to give us an answer right away, for it depends on another instance of itself.

Expanding the expression `f(argument)`

we have:

`h ( f ( g (argument) ) )`

`h ( h ( f ( g ( g (argument) ) ) ) )`

`h ( h (... f ( baseCase ) ... ) )`

Note that the pattern is: `h`

composed `n`

times with itself, composed with `f`

, composed with g, which is then also composed `n`

times with itself, that is, the number of times `h`

is composed with itself is ** the same** number of times `g`

is composed with itself.

This sequence of compositions of `g`

goes on and on until for a certain number `n`

of compositions, the resulting `g`

composed `n`

times with itself evaluated for `argument`

yields `baseCase`

, which means that `f`

can **finally** stop “calling” itself and return the **baseValue** at last.

Now if you’ve been paying attention you probably can already see how we may turn this recursive process into an iterative one.

As the amount of times `h`

is composed with itself is **the same** amount of times `g`

is composed with itself, if we find out how many compositions of `g`

it takes to reduce `argument`

to the `baseCase`

, then to calculate `f(argument)`

all we have to do it **iterate** `h`

over `baseValue`

.

So it all boils down to the question of **how many times** we need to apply apply `g`

over `baseValue`

.

Alas, a general iterative implementation for our general recursive function:

```
function f(argument) {
// Compute the number of applications
// of "g" that are necessary to reduce
// "argument" to the "baseCase"
let gIterationCounter = 0;
let transformedArgument = argument;
while(trasformedArgument !== baseCase) {
gIterationCounter++;
transformedArgument = g(argument);
}
// Apply "h" to the "baseValue"
let result = baseValue;
for(let hIterationCounter = 1;
hIterationCounter <= gIterationCounter;
hIterationCounter++) {
result = h(result);
}
return result;
}
```

However, if we think carefully about how the iterative evaluation of recursive functions, we notice there are two possibilities:

- Either we can reach the
`baseCase`

from any`argument`

using some number of applications of`g`

. - Or there is
**at least one**`argument`

for which no number of applications of`g`

will reduce it to the`baseCase`

.

The first case corresponds to the class of **total functions** and the second one corresponds to the class of **partial functions**.

Ideally, we’d like to deal only with the first case, because **total functions** are always guaranteed to halt, that is, they will always return something regardless of the argument we pass to them.

For the second case, however, if we pick an argument that no number of applications of `g`

will reduce it to the `baseCase`

, it means we’re in a **never-ending loop*!

Now you’re probably thinking: “Well, why don’t we just identify the arguments for which `f`

loops endlessly so that we can keep ourselves far away from them, or at least be able to throw an exception that indicates that this value is invalid ?”.

Well… The problem is that this is **precisely** the **halting problem**, which tells us that for some functions (actually infinitely many of them), there is **no** algorithm that can, for every `argument`

, decide whether it makes `f`

loop endlessly or not.

### Recursion with multiple base cases and base values

Whenever a recursive function has more than one base case this gives us more “opportunities” to reduce `argument`

to one of the base cases.

```
function f(argument) {
if (argument === baseCase1) {
return baseValue;
}
if (argument === baseCase2) {
return
}
//...
if (argument === baseCaseN) {
return baseValue;
}
return h ( f ( g (argument) ) );
}
```

We may even take this generalization further and abstract these conditionals in the form of a **function that recognizes when a given value corresponds to a base case**, which allows us to work with potentially **infinite** base cases.

```
function f(argument) {
if (isBaseCase(argument)) {
return baseValue;
}
return h (f ( g (argument) ) );
}
```

The next step is naturally to allow the recursive function to have different **base values** for each one of the base cases:

```
function f(argument) {
if (argument === baseCase1) {
return baseValue1;
}
if (argument === baseCase2) {
return baseValue2;
}
//...
if (argument === baseCaseN) {
return baseValueN;
}
}
```

Yet again, in much the same way we encapsulated the “recognition” of base cases in a function, we can do the same for base values by using a function that for a given argument that is guaranteed to be a base case, returns the corresponding base value.

```
function f(argument) {
if (isBaseCase(argument)) {
return correspondingBaseValue(argument);
}
return h ( f ( g (argument) ) );
}
```

Now we can work both with infinite base cases and infinite base values.

For the iterative version of this function:

```
function f(argument) {
let gIterationCounter = 0;
let transformedArgument = argument;
while(!isBaseCase(transformedArgument)) {
gIterationCounter++;
transformedArgument = g(argument);
}
let result = correspondingBaseValue(transformedArgument);
for(let hIterationCounter = 1;
hIterationCounter <= gIterationCounter;
hIterationCounter++) {
result = h(result);
}
return result;
}
```

The general idea remains pretty much the same, as we first find out the number of applications of `g`

that are necessary to reduce `argument`

to **some base case** and then we use this **base case** to find the corresponding **base value** and then finally we use this **base value** as the argument for the applications of `h`

.

But what if `f`

takes multiple arguments?

### Recursion with multiple arguments

Before we deal with functions that **actually** take more than one argument, it is useful to tackle a simpler yet similar problem, which is recursive functions that deal with **vectors**.

```
function f(vector) {
if (isBaseCase(vector)) {
return correspondingBaseValue(vector);
}
return h ( f ( g (vector) ) );
}
```

Notice that in the previous cases we never really specified the **type** of `argument`

, and that is because… well… **it doesn’t matter*!

So regardless of our argument is a **number**, or a **string** or a **vector** or a **tree**, or whatever, the representation we are working on is completely independent of the argument’s **type**.

This means that nothing changed, but there’s a key point here to observe which is the fact that even though **syntactically** speaking, a function that takes multiple arguments is not the same as a function that takes a vector as an argument, these multiple arguments can be easily encoded using vectors.

Ok, but what if we REALLY want to tackle recursive functions with multiple arguments?

To do so we need to adjust the auxiliary functions so that they can handle multiple arguments:

```
function f(argument1, argument2, /*...*/ argumentN) {
if (isBaseCase(argument1, argument2, /*...*/ argumentN)) {
return correspondingBaseValue(argument1, argument2, /*...*/ argumentN);
}
return h ( f ( g1(argument1), g2(argument2), /*...*/ gN(argumentN) ) );
}
```

The key point here is that now instead of having a single `g`

, we one `g`

for each argument, so that the “progression” of each argument via multiple applications of each `g`

is independent of one another:

`argument1 -> g1(argument1) -> g1(g1(argument1)) ...`

`argument2 -> g2(argument2) -> g2(g2(argument2)) ...`

`argument3 -> g3(argument3) -> g3(g3(argument3)) ...`

The only “dependency” that the arguments have on each other is that for `f`

to stop recursing, all the arguments must be reduced to some base case **simultaneously**, which doesn’t necessarily mean that this is going to happen at the first time some of the argument is reduced to some base case, for it is possible that during this reduction process some arguments end up “passing” by their base cases many times until they finally get in “sync” by reaching a base case together.

Even though we have seen that we **can** work with functions that actually take multiple arguments, from now on we’ll work with **vectors** to encode multiple arguments as this makes things much simpler.

Until now we’ve been gradually expanding on the different forms of recursion and each one of these expansions consisted of the introduction or generalization of one or more **auxiliary functions**, however, we still haven’t touched `h`

so far, so now, we’ll see what happens when `h`

takes multiple arguments.

`h`

with multiple arguments

Before we begin, we must recall that we’re only dealing with **simple** recursion, where `f`

is only referenced a single time, which means that even though `h`

will take multiple arguments from now on, **only one** of these arguments may include `f`

, otherwise we’d be dealing with **multiple** recursion which is a topic for the next post.

```
function f(vector) {
if (isBaseCase(vector)) {
return correspondingBaseValue(vector);
}
return h(vector, f(g(vector)));
}
```

Here we’re using a very specific form for `h`

, where it takes **two** arguments: the first one is the `vector`

and the second one is pretty much the same as before, `f`

‘s recursive call.

Now the expansion of `f`

becomes:

`h(vector, f(g(vector))`

`h(vector, h(g(vector), f(g(vector)) ) )`

`h(vector, h(g(vector), h(g(g(vector)), f(g(g(vector))) ) ) )`

Notice that the path `vector`

takes until it is reduced to a base case is still **linear**, so things remain pretty much the same in terms of how we turn this recursion into an iteration:

```
function f(vector) {
let gIterationCounter = 0;
let transformedArgument = vector;
while(!isBaseCase(transformedArgument)) {
gIterationCounter++;
transformedArgument = g(vector);
}
let currentVector = vector;
let result = correspondingBaseValue(transformedArgument);
for(let hIterationCounter = 1;
hIterationCounter <= gIterationCounter;
hIterationCounter++) {
result = h(currentVector, result);
currentVector = g(currentVector);
// Here we have to keep
// "currentVector" updated to
// feed it into "h", given that
// "h" now depends on the arguments
// of "f"
}
return result;
}
```

So that’s it for today and until next time!

We are hiring new talents. Do you want to work with us? become@codeminer42.com