Thought Leadership

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.

Colin Walls

I have over thirty years experience in the electronics industry, largely dedicated to embedded software. A frequent presenter at conferences and seminars and author of numerous technical articles and two books on embedded software, I am a member of the marketing team of the Mentor Graphics Embedded Systems Division, and am based in the UK. Away from work, I have a wide range of interests including photography and trying to point my two daughters in the right direction in life. Learn more about Colin, including his go-to karaoke song and the best parts of being British: http://go.mentor.com/3_acv

More from this author

Leave a Reply

This article first appeared on the Siemens Digital Industries Software blog at https://blogs.stage.sw.siemens.com/embedded-software/2017/04/17/inline-recursive-funtions/