using inline prototype in recursion functions c++ [duplicate]

Th开发者_运维技巧is question already has answers here: Closed 12 years ago.

Possible Duplicate:

Two questions about inline functions in C++

Hi, Can i declare my function as "inline" if it is a recursive function? I've heard it may be a bit problematic/dangerous. I'd like to understand the reasons behind all this.

Thanks!

---

You can declare it inline if you like, but it will do nothing because the function obviously cannot be inlined. Note that, in general, the compiler is free to completely ignore any and all inline requests.

That being said, it may actually get inlined if the compiler removes the recursion. A common technique used is the tail-call optimisation, which changes functions that call themselves recursively at the end of the function into iterative functions. For example:

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

would get transformed into:

int factorial(int n, int accum = 1)
{
start:
  if (n == 1) return accum;
  accum *= n;
  n = n - 1;
  goto start;
}

which could be inlined.

Note that while the compiler is free to not inline functions declared with inline, it cannot ignore your request for internal linkage i.e. you can still define your inline recursive function in a header file and include it with many cpp files without worrying about multiple definitions.

---

To understand the reasons why inlining doesn't make sense, you have to think about what inlining a function does.

When it's inline, it will essentially ask the compiler to replace the function call with the body of the function (the compiler can ignore this). So if you did this recursively, it'd be infinite. Let's look at an example:

int factorial(int n) {
  if (n == 0 || n == 1)
    return 1;
  return n * factorial(n-1);
}

Now, if this were inlined, we'd first replace a call to factorial with it's body. Looking at the body of factorial itself, we'd have to replace the call factorial(n-1). This gives:

int factorial(int n) {
  if (n == 0 || n == 1)
    return 1;
  return n * ((( if (n-1 == 0 || n-1 == 1)
    return 1;
  return (n-1) * factorial(n-1-1); )));
}

I'm using tripple parenthesis to indicate code replacement. Of course this isn't exactly valid code, but it ilustrates my point.

From here, we have another factorial call inside the new code, so we replace that, and on ad infinitum.

So, that's reasoning behind why such a thing isn't done. Modern compilers are clever enough not to do this for exactly this reason, though.