Recursion is one of those useful concepts that you learn in college in programming class and also on online tutorials. It enables a wide range of problems to be solved that otherwise can’t be performed, such as quicksort and binary search. Morever, recursion works in all languages because the underlying concept is the same.
However, there is a limit to the maximum depth of a function call before a runtime fails. In C++, you can nest up to 256 recursive function calls on the stack before it segfaults. In Python, you get an exception when a similar amount is reach. Both are very annoying instances of program failure, yet recursion is too fundamental to do without.
How can we solve this problem?
In order to work around this limitation, we can use a technique called unrolling the stack to save the state of several function executions into several vectors which each represent a call stack for a single variable. Each element inside the vectors is used by a single function. Then, we make excessive use of iteration and loops. I will give examples on how to work different kinds of recursive functions below.
Single Recursive Call
The simplest recursive function only recurses once and has no return value, and looks something like as follows:
void DoSomething(int a, string data) {
if (a < 0) return;
print data;
DoSomething(a<<1, data + "1");
// implicit return statement
}
It's easy to see that this can be converted into a loop. Note that it is not required for all variables to be converted to stacks. If you can optimize out a stack, then by all means, do it.
void DoSomething(int a, string data) {
vector stack_data {data};
vector stack_a{a};
int depth = 0;
do {
print stack_data[depth];
if (stack_a[depth] < 0) {
// In this particular case there is nothing
// after the recursive call (including other recursive
// calls), so a return statement would also work, but I
// want to demonstrate how the call stack is unwinded.
stack_data.pop_back();
stack_a.pop_back();
depth--;
conitnue; // Equivalent to an implicit return.
}
depth++;
stack_data.resize(depth+1);
stack_a.resize(depth+1);
stack_a[depth] = stack_a[depth-1] << 1;
stack_data[depth] = "1";
// Implicit continue here implies a recursive call
} while (depth > 0);
}
Multiple Recursive Calls
Things get slightly more complicated when we recurse into the function two or more times per call. In that case, a simple while loop will no longer cut it.
void DoSomething(int a, string data) {
if (a < 0) return;
print data;
DoSomething(a<<1, data + "1");
DoSomething(a<<1, data + "2");
...
DoSomething(a<<1, data + "10");
// implicit return statement
}
To solve this problem, we will introduce a call-stack variable for indicating the recursion number per-function, and build a switch case inside the while loop. When we build a switch case, we should populate the call-stack with the first state we want to start in.
void DoSomething(int a, string data) {
vector stack_data {data};
vector stack_a {a};
int depth = 0;
vector stack_recursetype {1};
do {
if (stack_recursetype[depth] == 0) {
stack_data.pop_back();
stack_recursivetype.pop_back();
stack_a.pop_back();
depth--;
continue; // Equivalent to an implicit return.
}
// The original function body begins here.
else if (stack_a[depth] < 0) {
stack_data.pop_back();
stack_recursetype.pop_back();
stack_a.pop_back();
depth--;
continue; // Equivalent to an implicit return.
}
print stack_data[depth];
// It is irrelevant how the stack values are changing per
// unrolled function call. That is because the recursetype
// is an implicit variable as if we were an assembler, and
// a list of successive function calls is one-dimensional.
//
// The point being, nested switch cases are not needed here.
switch (stack_recursetype[depth-1]) {
case 1:
stack_recursetype[depth] = 2;
depth++;
stack_a.resize(depth+1);
stack_recursetype.resize(depth+1);
stack_data.resize(depth+1);
stack_a[depth] = stack_a[depth-1] << 1;
stack_data[depth] = stack_data[depth-1] + "1";
stack_recursetype[depth] = 1;
break;
case 2:
stack_recursetype[depth] = 3;
depth++;
stack_a.resize(depth+1);
stack_recursetype.resize(depth+1);
stack_data.resize(depth+1);
stack_a[depth] = stack_a[depth-1] << 1;
stack_data[depth] = stack_data[depth-1] + "2";
stack_recursetype[depth] = 1;
break;
...
case 10:
stack_recursetype[depth] = 0; // set it to some END state
depth++;
stack_a.resize(depth+1);
stack_recursetype.resize(depth+1);
stack_data.resize(depth+1);
stack_a[depth] = stack_a[depth-1] << 1;
stack_data[depth] = stack_data[depth-1] + "10";
stack_recursetype[depth] = 1;
break;
}
// Implicit continue here implies a recursive call
} while (depth > 0);
}
Multiple Recursive Calls, Selective Execution
The previous unrolled recursive function does not work well when some of the branches have conditions on them. Take the following example, where the second branch is protected by a condition:
void DoSomething(int a, string data) {
if (a < 0) return;
print data;
DoSomething(a<<1, data + "1");
if (a & 0x4) {
DoSomething(a<<1, data + "2");
}
...
DoSomething(a<<1, data + "10");
// implicit return statement
}
In this case, we have to transfer the branch condition inside the appropriate switch case, and abstain from pushing a new stack element if that condition is not satisfied.
void DoSomething(int a, string data) {
vector stack_data {data};
vector stack_a {a};
int depth = 0;
vector stack_recursetype {1};
do {
if (stack_recursetype[depth] == 0) {
stack_data.pop_back();
stack_recursivetype.pop_back();
stack_a.pop_back();
depth--;
continue; // Equivalent to an implicit return.
}
// The original function body begins here.
else if (stack_a[depth] < 0) {
stack_data.pop_back();
stack_recursetype.pop_back();
stack_a.pop_back();
depth--;
continue; // Equivalent to an implicit return.
}
print stack_data[depth];
// It is irrelevant how the stack values are changing per
// unrolled function call. That is because the recursetype
// is an implicit variable as if we were an assembler, and
// a list of successive function calls is one-dimensional.
//
// The point being, nested switch cases are not needed here.
switch (stack_recursetype[depth-1]) {
case 1:
stack_recursetype[depth] = 2;
depth++;
stack_a.resize(depth+1);
stack_recursetype.resize(depth+1);
stack_data.resize(depth+1);
stack_a[depth] = stack_a[depth-1] << 1;
stack_data[depth] = stack_data[depth-1] + "1";
stack_recursetype[depth] = 1;
break;
case 2:
stack_recursetype[depth] = 3;
// The function will only recurse if the
// condition is satisfied.
if (a & 0x4) {
depth++;
stack_a.resize(depth+1);
stack_recursetype.resize(depth+1);
stack_data.resize(depth+1);
stack_a[depth] = stack_a[depth-1] << 1;
stack_data[depth] = stack_data[depth-1] + "2";
stack_recursetype[depth] = 1;
}
break;
...
case 10:
stack_recursetype[depth] = 0; // set it to some END state
depth++;
stack_a.resize(depth+1);
stack_recursetype.resize(depth+1);
stack_data.resize(depth+1);
stack_a[depth] = stack_a[depth-1] << 1;
stack_data[depth] = stack_data[depth-1] + "10";
stack_recursetype[depth] = 1;
break;
}
// Implicit continue here implies a recursive call
} while (depth > 0);
}
Multiple Recursive Calls, Iterative Execution
What if one of the branches was inside a loop? Then it has to be included inside the respective branch.
void DoSomething(int a, string data) {
if (a < 0) return;
print data;
DoSomething(a<<1, data + "1");
for (int i = 0; i < 10; i++) {
int i = 0;
while (true) {
DoSomething(a<<1, data + "2");
if (i == 10) break;
i++;
}
...
DoSomething(a<<1, data + "10");
// implicit return statement
}
The loops will look slightly different here because their conditions are embedded inside the branch case body instead of simply making a nested loop. That is because it is complicated to break out of a nested loop to execute the actual body. In this case, a single additional call stack must be made, and loop conditions must be checked before progression can continue to the next state.
Keep in mind that the loop itself only has one existing call stack at any given time. At each iteration, the call stack is destroyed and a new one is made (you'll see why this is done later). All this works well for "for" and "while" loops, but for "do-while" loops you need to introduce an additional condition called something like
first_runor something similar. "for" loops must also be deconstructed to "while" loops, in order to allow any arbitrary function call to be used as a condition.
void DoSomething(int a, string data) {
vector stack_data {data};
vector stack_a {a};
int depth = 0;
vector stack_recursetype {1};
int branch_2_i = -1; // Used in case 2 - set to some invalid value
do {
if (stack_recursetype[depth] == 0) {
stack_data.pop_back();
stack_recursivetype.pop_back();
stack_a.pop_back();
depth--;
continue; // Equivalent to an implicit return.
}
// The original function body begins here.
else if (stack_a[depth] < 0) {
stack_data.pop_back();
stack_recursetype.pop_back();
stack_a.pop_back();
depth--;
continue; // Equivalent to an implicit return.
}
print stack_data[depth];
// It is irrelevant how the stack values are changing per
// unrolled function call. That is because the recursetype
// is an implicit variable as if we were an assembler, and
// a list of successive function calls is one-dimensional.
//
// The point being, nested switch cases are not needed here.
switch (stack_recursetype[depth-1]) {
case 1:
stack_recursetype[depth] = 2;
depth++;
stack_a.resize(depth+1);
stack_recursetype.resize(depth+1);
stack_data.resize(depth+1);
stack_a[depth] = stack_a[depth-1] << 1;
stack_data[depth] = stack_data[depth-1] + "1";
stack_recursetype[depth] = 1;
break;
case 2:
// the while loop shall be embedded inside the
// branch case.
if (branch_2_i == -1) {
branch_2_i = 0;
depth++;
stack_a.resize(depth+1);
stack_recursetype.resize(depth+1);
stack_data.resize(depth+1);
stack_a[depth] = stack_a[depth-1] << 1;
stack_data[depth] = stack_data[depth-1] + "2";
stack_recursetype[depth] = 1;
}
else if (branch_2_i == 10) {
stack_recursetype[depth] = 3;
--depth;
stack_data.pop_back();
stack_a.pop_back();
stack_recursetype.pop_back();
branch_2_i = -1;
}
else {
--depth;
stack_data.pop_back();
stack_a.pop_back();
stack_recursetype.pop_back();
++branch_2_i;
depth++;
stack_a.resize(depth+1);
stack_recursetype.resize(depth+1);
stack_data.resize(depth+1);
stack_a[depth] = stack_a[depth-1] << 1;
stack_data[depth] = stack_data[depth-1] + "2";
stack_recursetype[depth] = 1;
}
break;
...
case 10:
stack_recursetype[depth] = 0; // set it to some END state
depth++;
stack_a.resize(depth+1);
stack_recursetype.resize(depth+1);
stack_data.resize(depth+1);
stack_a[depth] = stack_a[depth-1] << 1;
stack_data[depth] = stack_data[depth-1] + "10";
stack_recursetype[depth] = 1;
break;
}
// Implicit continue here implies a recursive call
} while (depth > 0);
}
Returning Values From Recursive Functions
Up to now, we have only seen recursive functions that return a value. Naturally, most useful recursive functions you will deal with will return some kind of value. Some might even take additional pointer or reference parameters to return multiple values. The good news is that return values can be represented as a stack as well.
int DoSomething(int a, string data) {
if (a < 0) return 1;
print data;
return DoSomething(a<<1, data + "1");
}
void DoSomething(int a, string data) {
vector stack_data {data};
vector stack_a{a};
vector stack_ret_a;
int depth = 0;
do {
stack_ret_a.resize(depth+1);
print stack_data[depth];
if (stack_a[depth] < 0) {
// In this particular case there is nothing
// after the recursive call (including other recursive
// calls), so a return statement would also work, but I
// want to demonstrate how the call stack is unwinded.
stack_data.pop_back();
stack_a.pop_back();
stack_ret_a[depth] = 1; // This is a return value.
depth--;
conitnue;
}
depth++;
stack_ret_a.resize(depth+1);
stack_data.resize(depth+1);
stack_a.resize(depth+1);
stack_a[depth] = stack_a[depth-1] << 1;
stack_data[depth] = "1";
stack_ret_a[depth] = stack_a[depth];
// Implicit continue here implies a recursive call
} while (depth > 0);
return_ret_a[depth];
}
Work In Progress
I am still fleshing out the prototype of this scheme, so some parts, in particular the areas where return logic is handled, are probably wrong. Later I will make another posts with corrections and new material
