Inline recursive functions

Recently, I blogged about a video in which I talked about inlining of code. I thought that this was an interesting, but ultimately straightforward subject. I then got a message from a reader/viewer asking a simple question: is it possible to inline a recursive function?

I needed to think about that …

First off I wondered whether there was a universal answer on theoretical grounds. My conclusion was that there was not, as different recursive functions use resources in different ways. So the simple answer to the question is “it depends …”

Some recursive functions use parameters to pass a value through the iterations. A well known and easy to understand example is a factorial function:

int fact(int n)
{
   if (n > 1)
      n = n * fact(n-1);
   return n;
}

In this case, each value of n is updated from the last one. So, it would be possible to easily recode this algorithm as a simple loop that does the same job, but uses a single accumulating variable, in this case, m:

int fact(int n)
{
   int m=1;

   while (n>1)
   {
      m *= n;
      n--;
   }

   return m;
}

This function could be inlined with no problem.

Other recursive functions use the sequence of recursive calls to create a queue of values or indeterminate length, which is commonly accessed in a Last In, First Out [LIFO] fashion. Here is an example of a function to print a value in any number base [from 2 to 16]:

void printbase(int number, int base)
{
   if (number >= base)
   {
      printbase(number/base, base);
   }
   printf("%X", number%base);
}

Each instance of the parameter base is use to hold a single digit. The algorithm works from the least significant digit upwards, but printing must occur the other way around [interesting that we write numbers from right to left, in effect, even though we write text the other way; this gives away its Arabic origins]. So, the sequence of parameter instances establish a LIFO queue on the stack.

So, the best answer to the original question is that some recursive functions can be inlined, but others cannot.