468,765 Members | 1,737 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,765 developers. It's quick & easy.

regarding recursive function declared as inline

Hi Everyone,

I have a function declared as inline and i was wondering as to how it
would be expanded by the compiler

sample(int x)
{
if (x>0) sample(--x);
printf("%d",x);
}

Does anyone have any idea?

Dec 12 '06 #1
7 1668
sa*****@yahoo.co.in wrote:
Hi Everyone,

I have a function declared as inline and i was wondering as to how it
would be expanded by the compiler

sample(int x)
{
if (x>0) sample(--x);
printf("%d",x);
}

Does anyone have any idea?
Yes. Compile it and see.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Dec 12 '06 #2
sam_...@yahoo.co.in wrote:
I have a function declared as inline and i was wondering as to how it
would be expanded by the compiler

sample(int x)
{
if (x>0) sample(--x);
printf("%d",x);
}

Does anyone have any idea?
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.

Cheers! --M

Dec 12 '06 #3
>
Yes. Compile it and see.
Yes i did and it did work, but i'm afraid the expansion of inline
functions are not to be seen, in my case i made sure that the input to
the recursive function was determined at run time as an input, so how
does compiler expand this case? or is it that the compiler leaves the
function as it is and is invoking it as an ordinary function call?

Dec 12 '06 #4
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)?

Dec 12 '06 #5
sa*****@yahoo.co.in wrote:
however do
you think every recursive logic can be expressed in a loop (even using
some extra variables)?
Yes, anything that can be expressed recursively in C++ can be, not
least because all C++ code is ultimately translated into some machine's
instructions, and most machines have support only for the equivalent of
goto statements, which are used for functions and loops.

Cheers! --M

Dec 12 '06 #6
sa*****@yahoo.co.in wrote:
>Yes. Compile it and see.

Yes i did and it did work, but i'm afraid the expansion of inline
functions are not to be seen, in my case i made sure that the input to
the recursive function was determined at run time as an input, so how
does compiler expand this case? or is it that the compiler leaves the
function as it is and is invoking it as an ordinary function call?
Compile it, make sure your compiler outputs the assembly, and see.

There is no way to tell whether a function has been inlined or not, by
means of C++ language. It's not what's known as "observable behaviour".

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Dec 12 '06 #7

sa*****@yahoo.co.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

Dec 12 '06 #8

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

6 posts views Thread by kceiw | last post: by
7 posts views Thread by Aloo | last post: by
5 posts views Thread by Digital Puer | last post: by
14 posts views Thread by jg | last post: by
reply views Thread by zhoujie | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.