Categories
Basics Guides

How To Flatten A Recursive Function

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_run
or 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

By Ali Sherief

Editor-in-chief and serial coder & blogger.

This website was made possible by hostingby.design (formerly walkerservers). If you need to rent powerful VPSes or dedicated boxes with crypto, credit card, or Paypal, these are your guys. Consider joining with my affiliate link.
This is default text for notification bar