by 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,whileand even the outcastgoto. - 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
baseCasefrom anyargumentusing some number of applications ofg. - Or there is at least one
argumentfor which no number of applications ofgwill reduce it to thebaseCase.
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 want to work with you. Check out our "What We Do" section!
