Printable View
Hi.
Recursion is slower than loops due to stacks and that stuff. However, I'm wondering if good compilers (VC++, gcc...) change some types of recursion into loops during optimization.
For example,
void demo(int i){
if (i==0) do something;
demo(i-1);
}
Since the call to the function is the last line, there's no need to save it into the stack. Ex: SML optimizes it this way. I'm wondering about C++.
Thanks :D
I doubt it, but you could compile that code an look at the assembly. Every C++ compiler is different, so I can't say what "C++" will do. Some compilers may optimize in a certain way, but not all will.
Thx for your reply.
Yes I tried it and saw the disassembly window in VC++. It translates it into a loop in VC++ .NET in release mode (but not in debug mode).
No optimizations are made in debug mode. Otherwise when steping through your program it wouldn't go where/do what you expect.
Well, to test a compiler out, you could simply write a highly inefficient recursive function and then an iterative function that accomplishes the same task. Use both of them and see which one runs more quickly. If there is a large difference in run-time, then no optimization must have been made.
Fierytycoon
I know for certain that many compilers will optimize tail recursion into an iterative solution.
(Briefly) Tail recursion means that there are no operations after the recursive call - and that kind of recursion is really easily translated into a loop.
Regards,
Bassman