Recursion isn't lying to you. Rather, many JavaScript implementations are screwing you over.
I suspect scheme would handle this much better.
Recursion is lying to you
21–30 of 51 posts
Re: Recursion is lying to you
#22lol. i once interviewed with facebook and had some "senior" dev on the phone who was balking and grousing at my claim that iterative algorithms are faster than recursive ones. the minute i mentioned spatial locality, he went quiet. more to the point, i feel like there should be a compiler switch or decorator style flag in modern languages that declare "this function is expected to optimize with tail recursion, throw…
Re: your first paragraph, I don't get it, what does spatial locality have to do with recursion vs. iteration? And the blanket speed claim doesn't make sense either. I feel like you're thinking of a specific algorithm or access pattern or technology and overgeneralizing to the idea that it's somehow impossible for recursion to ever match the performance or be faster?
Yes, and a high-level scripting language can in some specific circumstances be made to run code faster than a low-level compiled language. Generally, it's the other way around though.
Re: Recursion is lying to you
#23[flagged]
Re: Recursion is lying to you
#24Earlier quoted context omitted.
It's not CS 101 that JavaScript apparently sucks at TCO. That was surprising to me.
The CS 101 model of computing doesn’t have TCO… which makes it pretty accurate to the real world.
TCO is surprisingly commonly supported in the real world. TCO is supported in C++ compilers, JavaScript in Safari, Scala, Clojure in a way, etc.!
For instance:
"All current mainstream [C++] compilers perform tail call optimisation fairly well (and have done for more than a decade), even for mutually recursive calls" [1].
"As of July 22, 2023 Safari is the only browser that supports tail call optimization" of JavaScript [2].
"Since Clojure uses the Java calling conventions, it cannot, and does not, make the same tail call optimization guarantees. Instead, it provides the recur special operator, which does constant-space recursive looping" [3].
"The Scala compiler will automatically optimize any truly tail-recursive method. If you annotate a method that you believe is tail-recursive with the @tailrec annotation, then the compiler will warn you if the method is actually not tail-recursive" [4].
[1]: https://stackoverflow.com/a/34129
[2]: https://stackoverflow.com/a/37224563
Re: Recursion is lying to you
#25lol. i once interviewed with facebook and had some "senior" dev on the phone who was balking and grousing at my claim that iterative algorithms are faster than recursive ones. the minute i mentioned spatial locality, he went quiet. more to the point, i feel like there should be a compiler switch or decorator style flag in modern languages that declare "this function is expected to optimize with tail recursion, throw…
Re: your first paragraph, I don't get it, what does spatial locality have to do with recursion vs. iteration? And the blanket speed claim doesn't make sense either. I feel like you're thinking of a specific algorithm or access pattern or technology and overgeneralizing to the idea that it's somehow impossible for recursion to ever match the performance or be faster?
maybe the wrong terminology, but non-tail-call-optimized recursions spray their state across space with each iteration consuming a new stack frame, where iterative algorithms live in one stack frame and can re-use temporaries. the state spraying results in consumption and spilling down the memory hierarchy, from registers through caches. i think of this as the memory hierarchy being designed to best perform when spatial locality of memory usage is maintained, but it's slightly different from what most people mean when they discuss spatial locality... maybe "cache efficiency" is the better term?
Re: Recursion is lying to you
#26Earlier quoted context omitted.
Re: your first paragraph, I don't get it, what does spatial locality have to do with recursion vs. iteration? And the blanket speed claim doesn't make sense either. I feel like you're thinking of a specific algorithm or access pattern or technology and overgeneralizing to the idea that it's somehow impossible for recursion to ever match the performance or be faster?
Yes, and a high-level scripting language can in some specific circumstances be made to run code faster than a low-level compiled language. Generally, it's the other way around though.
This feels like a strawman and doesn't really attempt to answer my question. These kinds of broad generalizations really need good evidence/citation.
Re: Recursion is lying to you
#27CS 101, no? Recursion is easier to write, but less performant and more risky than iteration.
It's not CS 101 that JavaScript apparently sucks at TCO. That was surprising to me.
Heh, reminds me of this talk at !!conf: Tail Call Optimization: The Musical, https://youtu.be/-PX0BV9hGZY (2019).
Re: Recursion is lying to you
#28no mention of dynamic programming for dealing with recursive functions? Dynamic programming was built for this, you don't even need to thrash the heap as much as that trampoline. Instantiate your array, make sure you set your base cases and loops so that you don't step in an `undefined` hole, and then recurse in reverse.
Re: Recursion is lying to you
#29Earlier quoted context omitted.
>Recursion is easier to write And read..
You’ve never read a 5000 line recursive method that returns different numbers of arguments depending on where it chose to execute the recursive call.
If all you do is replace the recursion in that example with one (or more) loops with mutable indexes, chances are the code will get worse.
Re: Recursion is lying to you
#30Earlier quoted context omitted.
Re: your first paragraph, I don't get it, what does spatial locality have to do with recursion vs. iteration? And the blanket speed claim doesn't make sense either. I feel like you're thinking of a specific algorithm or access pattern or technology and overgeneralizing to the idea that it's somehow impossible for recursion to ever match the performance or be faster?
maybe the wrong terminology, but non-tail-call-optimized recursions spray their state across space with each iteration consuming a new stack frame, where iterative algorithms live in one stack frame and can re-use temporaries. the state spraying results in consumption and spilling down the memory hierarchy, from registers through caches. i think of this as the memory hierarchy being designed to best perform when spat…
> maybe the wrong terminology, but non-tail-call-optimized recursions spray their state across space with each iteration consuming a new stack frame, where iterative algorithms live in one stack frame and can re-use temporaries
If that's what you mean then I'm afraid it sounds like you're mixing a few things up. For example, imagine depth-first search: you're going to need a stack somewhere, whether it's the CPU stack which you use via recursion, or an explicit stack you use via iteration. Iterating doesn't magically remove your need for that space and somehow collapse everything down to one stack frame. And you can reuse temporaries from the heap too, etc.
Fundamentally, there is the question of how much space you need for given algorithm, the question of what algorithm you should use in the first place, the question of whether that particular algorithm should be implemented recursively or iteratively, and the question of what is more maintainable and easier to evolve in practice.
These are all separate questions, but you're conflating them. If your iteration uses constant space but your recursion doesn't, that's because you're not implementing the same algorithm. You're implementing a different algorithm that achieves the same original goal you had. Of course one algorithm might beat the other, that's no surprise.