loops versus recursion

[frag.machine]

[Spike]

try a compiler that has decent tail recursion optimisations, so that it compiles it into a loop instead of actually recursing.
either way, your algorithm is different. your recursion version has an aweful lot more divides, and they're floats so they won't be optimised into simple bitshifts (read: expensive).

[frag.machine]

[frag.machine]

[qbism]

I wonder if a recursion-oriented language+compiler like LISP or scheme would give better performance for the recursion option here. Passing functions, what a concept! So elegant.

[jitspoe]

From my personal experience, recursion is often easier to implement and understand in certain situations (traversing trees, sorting algorithms, etc.), but slower to execute than an iterative approach.

[frag.machine]

[WickedShell]

Without obsessing about it past what spike said, any tail recursive function will be turned into a loop by a good compiler, after which point any speed differences are probably implementation differences. The obvious gain here is that in the loop you aren't pushing tons of overhead onto the stack. (Especially if you create a lot of temporary memory elements/objects inside each function). This is something that gets harped upon a lot around the time one takes Computer Science II course. (and gets further revisited later).

The conclusion I reached from college work, and observing the results in my own code is that spending the time to make your recursive function tail recursive is a very worth while investment of time. But once you can accomplish that there's no need to switch to a loop as the compiler should do that for you, and if it doesn't you probably aren't going to be happy about all the other things its not doing for you