sa*****@yahoo.c o.in wrote:
There is no requirement that the compiler expand inline everything
declared inline -- the keyword is only a hint. Recursion is probably
one of the things that could make the compiler skip it, but you'd have
to check the assembly output of your specific compiler to find out for
sure. If it was smart enough to expand the function above, it would
probably just turn it into a loop.
Thanks for the response, now i understand that inline keyword is just
a request for the c++ compiler to do something different,, however do
you think every recursive logic can be expressed in a loop (even using
some extra variables)?
You need a potentially unbounded number of variables or pointers and an
unbounded memory space (i.e. a stack, which recursion gives you for
free), but if you have that, it can be done.
In general the compiler won't be kind enough to do that sort of
optimization for you though, but there's one case in which most will
(at least with -O2 or whatever) called tail recursion.
You can look up the details, but if you wanted to compute, say,
factorials by recursion instead of loops (you're coming from ML or Lisp
or something) the naive approach is:
int fact(int n) {
return n * fact(n-1);
}
(I'm ignoring the fact that this won't work for n larger than some
smallish number). But this is a poor way of writing it; much better is
int fact(int n, int m) {
if(n == 0) return m;
else return fact(n-1, n*m);
}
int fact(int n) {
return fact(n, 1);
}
because the compiler will probably optimize that recursion into just a
loop, saving you both function call overhead in terms of time and
(usually more importantly) stack space.
Evan
