Techniques How to Remove Any Recursion

A function that calls itself is hard to visualize for most developers. Common software requirements are implemented thru loops, arrays, variables, and automated function calls thus making the use of recursion and variations of the list data structure unusual. In this article, we will take a look at how we can remove any recursive program by following the simple techniques described below. It is very important to understand that this article is not saying that recursion is bad.

Some applications of removing recursion are compiler optimization and coping with limited SQL function recursive calls. Let's see how it works by looking at Fibonacci numbers, which is defined as:

• F_N = F_N-1 + F_N-2 for N ≥ 2 with F₀ = F₁ = 1

We can easily implement a function on finding the Nth element of the Fibonacci sequence using a regular loop in C/C++ as shown below:

int fibo_loop(int N)
{
    int a = 0;
    int b = 1;
    int t = 1;

    for (int i = 1; i <= N; i++)
    {
        t = a + b;
        a = b;
        b = t;
    }

    return t;
}

Imagine you're given a recursive function call for Fibonacci instead of simple for loops (or worst, you're handed over an unmaintable project with several unnecessary and buggy recursive SQL functions by your former colleague).

int fibo(int N)
{
    if (N <= 1)
    {
        return 1;
    }
    else
    {
        return fibo(N - 1) + fibo(N - 2);
    }
}
 

Simpler as it seems,  fibo() function's flow of logic is less efficient than the fibo_loop() due to several stack pushes and pops for large values of N. But luckily, most compilers nowadays optimize such deficiencies in our program during compile time. Our objective in this article is to see how the method of converting any recursive program to simple loops and not how to optimize your code - the optimized code for Fibonacci is the fibo() function, although it's commonly implemented with arrays for backtracking and analytical purposes.

1. First, let's breakdown any compounded recursive calls into separate lines, and call it fibo1():

   int fibo1(int N)
   {
       int t = 0;

       if (N <= 1)
       {
           return 1;
       }
       else
       {
           t += fibo1(N - 1);
           t += fibo1(N - 2);

           return t;
       }
   }

2. Next, we remove any unnecessary else statements, since any ifs, else ifs will flow in this section of the code anyway. We'll call this implementation fibo2().

   int fibo2(int N)
   {
       int t = 0;

       if (N <= 1)
       {
           return 1;
       }

       t += fibo2(N - 1);
       t += fibo2(N - 2);

       return t;
   }

3. Then we maintain only one (1) return statement as much as possible for simplication purposes using the goto statement and the last: label. We will call this implementation fibo3().

   int fibo3(int N)
   {
       int t = 0;

       if (N <= 1)
       {
           t = 1;
           goto last;
       }

       t += fibo3(N - 1);
       t += fibo3(N - 2);

       last:
       return t;
   }

4. Yes, I know that goto statements are evil and not very OOP. Trust me, we will convert it to control loops later on. Converting it to goto at this point makes it more convenient. Besides, we're not violating any logic of the program flow.

   This next step is quite amusing for novice developers. We remove the last recursive function, replaces it with N = N - 2, and go to the very first step of the function after initializing the variable t, as there are no codes that follow that will disrupt any logic of the program flow. We'll label that step as start:. This technique is called end-recursion removal and being done by most compilers to remove code deficiencies due to recursive function call abuse.

   We skipped the initialization of t to zero(0) as logic dictates that we need the last value of t. And since we need the last value of t, we need to add the previous value of t to t, instead of t to 1 under if (N <= 1).

   Take your time at this point to understand what has been done to replace the last recursion call with a goto loop. It will be confusing if this is your first time.

   After implementing the procedure above, this gives us fibo4() as shown below:

   int fibo4(int N)
   {
       int t = 0;

       start:
       if (N <= 1)
       {
           t += 1;
           goto last;
       }

       t += fibo4(N - 1);

       N = N - 2;
       goto start;

       last:
       return t;

   }

5. And now the meticulous part - removing the last recursion call and replacing it with a stack. If your programming language doesn't support stacks, don't worry, you can implement a stack using an array or if SQL, using tables. If you need guidance how to do it, visit this article here.

   But why use a stack at this point? Since the value of N is required to be at the same state before and after the recursion is called, we need to push it to a stack. Then we replace the recursion by N = N - 1, invoking the goto command to start, and a next: label where the program can resume after going back from start:.  

   We need to insert another script after the last label wherein we check if the stack is not empty, as we need to retrieve the value of N and go back to the next: label and so it doesn't terminate in case the program is called thru N = N - 1; goto start;.

   int fibo5(int N)
   {
       int t = 0;

       start:
       if (N <= 1)
       {
           t += 1;
           goto last;
       }

       s.push(N);
       N = N - 1;
       goto start;
       next:

       N = N - 2;
       goto start;

       last:
       if (!s.empty())
       {
           N = s.top(); s.pop();
           goto next;
       }

       return t;
   }

6. You will be amused to know that the program above works. As promised, we are now converting goto statements to while loops. We'll start with goto start;.

   The label start: naturally represents do { } block, the first goto start can be replaced by continue, and the last goto start: can be written as while (1) or while (true);

   int fibo6(int N)
   {
       int t = 0;

       do
       {
           if (N <= 1)
           {
               t += 1;
               goto last;
           }

           s.push(N);
           N = N - 1;
           continue;

       next:

           N = N - 2;

       } while (true);

       last:
       if (!s.empty())
       {
           N = s.top(); s.pop();
           goto next;
       }

       return t;

   } 

7. We can remove the last: label by moving it inside if (N<=1), then to emulate goto next, we replace it with continue, and finally put a break after the if statement to go the last line of the code and return t. And so the final implementation in fibo7() would be:

   int fibo7(int N)
   {
       int t = 0;

       do
       {
           if (N <= 1)
           {
               t++;
               if (!s.empty())
               {
                   N = s.top(); s.pop();
                   N = N - 2;
                   continue;
               }
               break;
           }

           s.push(N);
           N = N - 1;
       } while (true);

       return t;
   }

The fibo7() function is not as simple and as efficient as the fibo_loop() function, but if we're talking about the techniques in converting any recursive program to loops - you have it all here!