Hey guys for other reasons I want to know which will process info faster. An infinite recursion or an infinite loop?
They are the same thing. Both operations are performed on the stack.
I'd say the loop is faster. Recursion requires a function call for every iteration and for every function call there is a function frame created, so eventually with recursion you will run out of stack space, and it will be slower for that reason. The loop requires no such mechanism, if you've ever written assembly you can just create a loop with a single conditional jump, while call instruction pushes address to the stack, taking up space for every iteration. It's actually not that hard to benchmark, I'll try to do that after work maybe.
Also compilers have a big say in this scenario. Better find out what they are doing here.
2 Likes
It really depends what you're doing. In my experience, I try to use iteration (loops) as much as possible, and save recursion for the few areas, where it's really needed (large sorts), or code obfuscation is helpful (like encryption). The speed difference is negligible in most languages due to the trade-offs associated with each method.
And, dynamic_gravity, yes both operations occur on the stack, but in iteration the stack is cleaned on every loop, where as recursion continues to grow the stack until it hits the rest of the program's allocated memory. If you'd like more information you can check out this video: https://youtu.be/0pncNKHj-Sc
In the professional world, you're often not working on your own code the majority of the time, so making something slightly longer by avoiding things like recursion/ternary operators/lambdas/etc is in your team's best interest. Hopefully they'll return the favor by continuing to make readable, easy to follow code, and not choosing Perl for your teams next project ;).
Depends if the language has tail call optimization. Scala, Scheme, and Javascript (the ES6 spec of the language) have this.
I think that the recursion and infinite loops are almost similar in speed during run-time but recursion takes more time to compile. But that's just something I kind of remember form 2 years ago from my CS class, and could be wrong.
I got to playing with this over the summer actually. Because of out the program stack grows and the additional references used in function calls, recursion will always be slower than a functionally equivalent loop.
1 Like
This is a different story if its optimized into a jump by the compiler.
For some compilers on some optimization settings for tail recursion only, and even then it only matches.
Yep.
There's also continuations that you can use to optimize your recursive algorithm. Its not going to match the performance of a loop, but it will at least prevent creating a ton of function frames.
EDIT: I mean, trampolines :S
Continuations sounds like something new to me. Could you link to a definition and explanation?
I originally read on it in Functional Programming in Scala. You can implement it in about any language, although it will be more elegant if the language has functions as values. The idea is that instead of making the function call itself, it returns itself (the function). This allows the currently executing function to "end", and then the next function frame is allocated.
EDIT: OMG, this is the wrong name! They're actually called trampolines!
A clever optimization, but still not as fast.
One of these days I should implement my own optimizing C compiler with a number domain attribute, graphing relations, and bit level negation/logic cascading. Then feed that into a collapsing function based on LCS from suffix arrays and dead code elimination I'd have one mean optimizing compiler.
Btw, I implemented trampolines in javascript just for kicks (its a bit different from how I explained it):
This is basic computational complexity theory guys.
Recursion is stack bound via its return pointer and cannot be infinite, infinite recursion will be very fast at generating a stack overflow. XD
Almost all algroithms/loops with low Big-O complexity use a loop combined with a heap/tree data structure. if you ask any computer science student they will run away from recursion wherever they can! Look at http://bigocheatsheet.com/ for an example.
Quicksorts worst case complexity is an example of the problems with recursive algorithms. If you want to get a better idea of how these things work you can look up the relevant pseudo code samples for the various algorithms listed on that page.