>It's a well-known fact that iterative algorithms (using loops) are much more efficient than recursive algorithms that do the same thing. A true recursive function is slower and will consume more system resources (especially memory) than its iterative counterpart.
>Clearly all recursive algorithms have manageable iterative algorithm counterparts, however to confidently imply the opposite that all efficient iterative algorithms have recursive algorithm counterparts is undoubtedly a false statement. In this regard, the vast universe of diverse iterative algorithms will always envelop and completely overwhelm the infinitesimal recursive algorithm universe. (Recursive algorithms are only small seeds from which certain iterative algorithms stem).
quickperm.org
WTF
Jow Forums told me recursion is best and real computer science!?
It's a well-known fact that iterative algorithms (using loops) are much more efficient than recursive algorithms that...
>Jow Forums told me recursion is best and real computer science!?
most of Jow Forums seems to be into networking or maybe just started programming or studying cs so i wouldn't be surprised.
Loops are a subset of recursion, everything that has ever been done with loops can be done with recursion.
There are however, things you cannot do with just a loop, and if your had to do it with a loop, that loop would essentially be a simplified implementation of how recursion is implemented, thus neither consumes any significant amount more resources than the other.
There are plenty of languages that don't have loops at all, and instead have only the ability to recurse. Those languages are entirely as capable of anything any other imperative language.
The point about it taking more resources is totally false. You'd expect normally when you reimplement something using a loop to something using recursion it takes more memory because it needs extra stack frames etc., but this is why TCOs exist (tail call optimization) which lets the recursive implementation use as many resources as any loop implementation would give.
Given all this, recursive algorithms are neither slower nor more resource intensive. Whoever wrote this is clearly a total moron, and probably sad because he can't quite fathom recursion and recursive concepts yet.
Loops are faster, yes. However, functions remain the basic building block of mathematical analysis, and they don't fundamentally have any iterative structure.
Thus, when functionally modelling an iterative programming language, you need to do it as a function which takes the machine state and the next operation and gives a new machine state.
The only way to do repetition with such a structure is recursion.
> well known fact
He confuses algorithm complexity with algorithm implementation. If the implementation is shit, the runtime will be shit.
yea but recursion is makes me feel smarter haha, so FUCK YOU
calling a function creates overhead
recursion involves a lot of function calls
Tail-call
a
i
l
|
c
a
l
l
Show me an iterative solution for thr coin change problem, then come to me and say with a straight face that it's clearer than the recursive approach.
While it's true that iteration is often more efficient, there are many problems which are more naturally espressed using recursion.
Woke, quickperm guy is a retard.
Show me a nice iterative implementation of the Ackerman function.
Some recursive algorithms require extra data structures like queues to implement in a loop but usually recursion is chosen instead. Not sure how I feel like this or if it matters.
>Jow Forums told me recursion is best and real computer science!?
When? Not only is recursion harder to understand it's also slower.
If you require an extra data structure, i.e., a stack to implement looping, in order to avoid using the call stack, I'd say the autism has gone too far. Recursion, when done right, is nice to read, intuitive to understand, and may have properly defined bounds. Excessively worrying about pushing stack frames sounds like micro-optimalisation, if you ask me. First implement an efficient algorithm, and only if that isn't sufficient enough, then worry about it should be rewritten.
> that all efficient iterative algorithms have recursive algorithm counterparts
Absolute nonsense. Alan Turing proved lambda calculus is Turing complete like way back in the 30s. Any algorithm using iteration can be reimplemented using recursion.
That's not conjecture either. It was proven ages ago.
>If you require an extra data structure, i.e., a stack to implement looping, in order to avoid using the call stack, I'd say the autism has gone too far.
Agreed, just look at any "iterative" implementation of quicksort. It always uses some sort of stack.
Such an algorithm is so inherently recursive that the best way to implementing it is just using recursion directly.
>Any algorithm using iteration can be reimplemented using recursion.
>That's not conjecture either. It was proven ages ago.
>Loops are a subset of recursion, everything that has ever been done with loops can be done with recursion.
These posters are absolutely based.
dear fucking inbreed imbecile
1. Google TCO
2. Write a quicksort without recursion (the very basis of divide and conquer or pruning of a search space approach)
3. Fuck you.
qsort [] = []
qsort (x:xs) = qsort [y | y
/thread
>muh quicksort
ITT: sophomore CS students
Any half-decent compiler can inline functions and optimize tail calls (gcc does the latter with -O2). Therefore, basically, no. But you're probably a brainlet who uses Python anyway.
Recursion is good for college assignments and fizzbuzz at interviews, but in the real world and applied to real programs it just wastes memory and CPU cycles unnecessarily.
People who shit on recursion have never had to solve complex problems.
There is literally nothing wrong with Python.
I'm , and I don't shit on recursion (see and and ). But I honestly believe that if your only argument for recursion is "muh quicksort" then it's a weak argument, sorting is not particularly complex.
This guy was on the right track by saying that any iterative algorithm can be implemented using recursion, because it is mathematically proven so.
Pic related, it's mfw people rely on arbitrary examples instead of proofs.
>But I honestly believe that if your only argument for recursion is "muh quicksort" then it's a weak argument, sorting is not particularly complex.
>your only argument
You don't know what an example is, do you?
>b-but you should rely on proofs on a mongolian imageboard! an example isn't enough!
No fucking shit any iterative algorithm can be implemented using recursion. Even without formally proving so, anyone with half a brain can see it. It's also informally stated in the first chapter of SICP. That just reinforces how retarded OP's source is.
The quicksort example isn't even supposed to highlight this fact. It's meant to show how a typically recursive algorithm is awkwardly implemented iteratively, which is the opposite of what you're saying.
I bet you suck cocks for fun, too.
>You don't know what an example is, do you?
Examples are worthless when they rely on an arbitrary selection for "pretty code" and "ugly code". It's perfectly possible to implement quicksort without recursion, without introducing any runtime overhead or particular code complexity. It's just "ugly code", which is a pretty useless criteria for evaluating algorithms.
>Even without formally proving so, anyone with half a brain can see it.
Conjecture is not a substitute for proofs. Begone, mathlet.
>The quicksort example isn't even supposed to highlight this fact. It's meant to show how a typically recursive algorithm is awkwardly implemented iteratively
Which is why it is a shit example and why you should feel embarrassed for appealing to aesthetics. Especially on a board that unironically believe that borked C code full of undefined behaviour is prettier than Haskell or Python.
>t. can't even prove quicksorts average-case complexity formally
You might be quite literally autistic (the irl kind, not the Jow Forums kind) if you're lashing out to people for not writing a formal proof on a Mongolian chinknigger forum. Please get help.