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.

Post Author

Posted April 17th, 2017, by

Post Tags

, , ,

Post Comments

No Comments

About The Colin Walls Blog

This blog is a discussion of embedded software matters - news, comment, technical issues and ideas, along with other passing thoughts about anything that happens to be on my mind. The Colin Walls Blog

@colin_walls tweets

  • My latest video blog is now available. I talk about the use of a memory management unit [MMU] in an embedded system https://t.co/aSVECLARgl
  • Embedded software article: RTOS Revealed #6 look at the additional facilities that and RTOS may offer & beyond https://t.co/GXg8ivM3gW
  • #programmingTip To maintain real time integrity, keep ISRs as short as possible - unload the real work onto a task.

Follow colin_walls

Comments

Add Your Comment

Archives