and will notice that it gets close to φ = (1 + √5) / 2 ≈ 1.618033989, which makes the number of recursive calls O(φⁿ), which is much more fun than O(2ⁿ).
Really it's worse than exponential, because the size of the input is not n, it's the number of bits needed to store n i.e. log n. So as the number of bits k grow, it's growing phi^(2^k).
no 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.
The troubles of handling call stack recursion is downstream of the lack of strong tooling for static analysis of stack usage. Of the few tools available for generating a build-time call graph for an application, almost none of them can do so in a machine-readable format. AFAIK, the state of the art here is LLVM's dot-callgraph pass, and even that emits DOT rather than something more widely adopted like CSV or JSON. Outside of that, you have to build your own thing, either via runtime profiling or a custom compiler plugin.
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].
Most of these issues are a consequence of recursion never getting the same codification as the rest of the jmp patterns we eventually turned into control structures - eg: if, for, while, try/catch.
In the meantime, the theory of structured recursion[recursion schemes] has been developing, yet no language offers then as first class constructs. The best we get is library support. Imagine if we had to import a package to support if statements. The result? Programmers write recursive programs while navigating all the foot guns described in the article. No wonder recursion is hard to get right.
I might not be understanding what you’re saying here… but recursion compared to your if/whiles, are inherently coupled to the shape of the type they traverse where in the prior two we define data comparisons or input sizes.
Using a jmp isn’t really a call as you’d know, and information is lost that would be crucial to unwinding a recursion.
A recurse keyword would still leave the person writing the code with the decision with proving termination with base cases or trampolines — lest there is just a bunch of math that would unwind your recursion into a better bounded problem. Which is kind of what current keywords do anyway.
lol. 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 a compiler or linter error at static analysis time if that doesn't work out."
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?
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.
> 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 a compiler or linter error at static analysis time if that doesn't work out."
Scala and Kotlin have that. Other modern languages probably do as well.
Reference link: https://v8.dev/blog/modern-javascript#proper-tail-calls (Recursion, Proper tail calls, 2016)
Proper Tail Calls were implemented behind experimental flags but never shipped by default — the flags were later removed.
A fun quote from the article, discussing a basic Fibonacci recursive implementation:
> Each call branches into two more calls, so the total number of calls grows as O(2ⁿ).
Well, no, not really. If anyone bothers counting how many recursive calls are actually made, the result is far from powers of two:
A curious person will then calculate the actual ratio: and will notice that it gets close to φ = (1 + √5) / 2 ≈ 1.618033989, which makes the number of recursive calls O(φⁿ), which is much more fun than O(2ⁿ).Yes, because the number of calls in this setup is 2 * the next result - 1, and the Fibonacci sequence itself grows at this Θ(φⁿ) rate.
Really it's worse than exponential, because the size of the input is not n, it's the number of bits needed to store n i.e. log n. So as the number of bits k grow, it's growing phi^(2^k).
no 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.
The troubles of handling call stack recursion is downstream of the lack of strong tooling for static analysis of stack usage. Of the few tools available for generating a build-time call graph for an application, almost none of them can do so in a machine-readable format. AFAIK, the state of the art here is LLVM's dot-callgraph pass, and even that emits DOT rather than something more widely adopted like CSV or JSON. Outside of that, you have to build your own thing, either via runtime profiling or a custom compiler plugin.
CS 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.
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
[3]: https://stackoverflow.com/a/34097339
[4]: https://stackoverflow.com/a/3114245
Heh, reminds me of this talk at !!conf: Tail Call Optimization: The Musical, https://youtu.be/-PX0BV9hGZY (2019).
>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.
Bad code is hard to read, that is orthogonal to the fact that it is recursive.
Risky?
Presumably stack depth and overflow.
Most of these issues are a consequence of recursion never getting the same codification as the rest of the jmp patterns we eventually turned into control structures - eg: if, for, while, try/catch.
In the meantime, the theory of structured recursion[recursion schemes] has been developing, yet no language offers then as first class constructs. The best we get is library support. Imagine if we had to import a package to support if statements. The result? Programmers write recursive programs while navigating all the foot guns described in the article. No wonder recursion is hard to get right.
I might not be understanding what you’re saying here… but recursion compared to your if/whiles, are inherently coupled to the shape of the type they traverse where in the prior two we define data comparisons or input sizes.
Using a jmp isn’t really a call as you’d know, and information is lost that would be crucial to unwinding a recursion.
A recurse keyword would still leave the person writing the code with the decision with proving termination with base cases or trampolines — lest there is just a bunch of math that would unwind your recursion into a better bounded problem. Which is kind of what current keywords do anyway.
Recursion isn't lying to you. Rather, many JavaScript implementations are screwing you over.
I suspect scheme would handle this much better.
lol. 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 a compiler or linter error at static analysis time if that doesn't work out."
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?
[delayed]
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.
This exists in clang for C++ as the statement attribute [[clang::musttail]] and in gcc as [[gnu::musttail]]
> 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 a compiler or linter error at static analysis time if that doesn't work out."
Scala and Kotlin have that. Other modern languages probably do as well.
Been a while since I last used it but there is @tailrec in Scala. The compiler does enforce it and optimize the resulting bytecode.