4 ms·

Recursion is lying to you

RajT88 3mo ago
CS 101, no? Recursion is easier to write, but less performant and more risky than iteration.
- valleyer 3mo ago
  It's not CS 101 that JavaScript apparently sucks at TCO. That was surprising to me.
  - dnbfbfhf 3mo ago
    The CS 101 model of computing doesn’t have TCO… which makes it pretty accurate to the real world.
    - ckcheng 3mo ago
      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 https://stackoverflow.com/a/34129 [2]: https://stackoverflow.com/a/37224563 https://stackoverflow.com/a/37224563 [3]: https://stackoverflow.com/a/34097339 https://stackoverflow.com/a/34097339 [4]: https://stackoverflow.com/a/3114245 https://stackoverflow.com/a/3114245
  - ignoramous 3mo ago
    Heh, reminds me of this talk at !!conf: Tail Call Optimization: The Musical, https://youtu.be/-PX0BV9hGZY https://youtu.be/-PX0BV9hGZY (2019).
- sras-me 3mo ago
  >Recursion is easier to write And read..
  - LPisGood 3mo ago
    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.
    - palata 3mo ago
      Bad code is hard to read, that is orthogonal to the fact that it is recursive.
    - tikhonj 3mo ago
      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.
      - LPisGood 3mo ago
        Oh don’t worry it had more than a half dozen of those nested as well
- veqq 3mo ago
  Risky?
  - makr17 3mo ago
    Presumably stack depth and overflow.
  - mypalmike 3mo ago
    I once wrote a Xbox 360 indie game that would crash only in unusual situations due to stack overflow. The game involved essentially gluing together balls, and it would detect if the balls surrounded something. I used recursive DFS to check connectivity of the balls. And most of the time, there would be a couple dozen balls max connected. But you could definitely intentionally connect many many more balls if you wanted to. At a certain point, it would crash with a stack overflow. Changing it to not use recursion (explicit data structures) fixed the crash.
- dreamcompiler 3mo ago
  Tail recursive functions on a tail-jump optimized compiler can be as performant as loops. If the compiler was written by someone who has read the Steele papers, it generates the same assembly code in both cases.
ventana 3mo ago
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: n | result | # of calls 1 | 1 | 1 2 | 1 | 3 3 | 2 | 5 4 | 3 | 9 5 | 5 | 15 6 | 8 | 25 7 | 13 | 41 8 | 21 | 67 9 | 34 | 109 10 | 55 | 177 11 | 89 | 287 12 | 144 | 465 13 | 233 | 753 14 | 377 | 1219 15 | 610 | 1973 16 | 987 | 3193 17 | 1597 | 5167 18 | 2584 | 8361 19 | 4181 | 13529 20 | 6765 | 21891 A curious person will then calculate the actual ratio: n | result | # of calls | ratio 1 | 1 | 1 | 1 2 | 1 | 3 | 3 3 | 2 | 5 | 1.6666666666666667 4 | 3 | 9 | 1.8 5 | 5 | 15 | 1.6666666666666667 6 | 8 | 25 | 1.6666666666666667 7 | 13 | 41 | 1.64 8 | 21 | 67 | 1.6341463414634145 9 | 34 | 109 | 1.626865671641791 10 | 55 | 177 | 1.6238532110091743 11 | 89 | 287 | 1.6214689265536724 12 | 144 | 465 | 1.6202090592334495 13 | 233 | 753 | 1.6193548387096774 14 | 377 | 1219 | 1.6188579017264275 15 | 610 | 1973 | 1.6185397867104183 16 | 987 | 3193 | 1.6183476938672072 17 | 1597 | 5167 | 1.6182273723770748 18 | 2584 | 8361 | 1.6181536675053223 19 | 4181 | 13529 | 1.6181078818323167 20 | 6765 | 21891 | 1.6180796806859339 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ⁿ).
- Chinjut 3mo ago
  Yes, because the number of calls in this setup is 2 * the next result - 1, and the Fibonacci sequence itself grows at this Θ(φⁿ) rate.
- veltas 3mo ago
  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).
a-dub 3mo ago
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."
- senkora 3mo ago
  This exists in clang for C++ as the statement attribute [[clang::musttail]] and in gcc as [[gnu::musttail]]
- winstonlee 3mo ago
  Been a while since I last used it but there is @tailrec in Scala. The compiler does enforce it and optimize the resulting bytecode.
- dataflow 3mo ago
  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?
  - vanviegen 3mo ago
    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.
    - dataflow 3mo ago
      This feels like a strawman and doesn't really attempt to answer my question. These kinds of broad generalizations really need good evidence/citation.
kelseyfrog 3mo ago
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.
- n0blenote 3mo ago
  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.
  - kelseyfrog 3mo ago
    You're absolutely right. Recursion is tied to the shape of the data being recursed. It can be expressed a number of ways, but generally having a functor for the data type gives a lot of milage in operating over it. See https://github.com/passy/awesome-recursion-schemes https://github.com/passy/awesome-recursion-schemes for more of what I'm getting after.
- Jhsto 3mo ago
  I've been writing a language around recursion schemes! Insofar it's just a library for Lean, but I wish to one day release it as an array programming language. I'm submitting a thesis in ~3 months, after which I'll be open-sourcing it.
Chinjut 3mo ago
Recursion isn't lying to you. Rather, many JavaScript implementations are screwing you over.
- xedrac 3mo ago
  I suspect scheme would handle this much better.
10000truths 3mo ago
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.
abratabia 3mo ago
[flagged]
eventualcomp 3mo ago
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.
okzgn 3mo ago
Reference link: https://v8.dev/blog/modern-javascript#proper-tail-calls 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.
WolfeReader 3mo ago
The thread title should be updated to clarify that it's a JavaScript-specific article.

CS 101, no? Recursion is easier to write, but less performant and more risky than iteration.

valleyer 3mo ago
It's not CS 101 that JavaScript apparently sucks at TCO. That was surprising to me.
- dnbfbfhf 3mo ago
  The CS 101 model of computing doesn’t have TCO… which makes it pretty accurate to the real world.
  - ckcheng 3mo ago
    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 https://stackoverflow.com/a/34129 [2]: https://stackoverflow.com/a/37224563 https://stackoverflow.com/a/37224563 [3]: https://stackoverflow.com/a/34097339 https://stackoverflow.com/a/34097339 [4]: https://stackoverflow.com/a/3114245 https://stackoverflow.com/a/3114245
- ignoramous 3mo ago
  Heh, reminds me of this talk at !!conf: Tail Call Optimization: The Musical, https://youtu.be/-PX0BV9hGZY https://youtu.be/-PX0BV9hGZY (2019).
sras-me 3mo ago
>Recursion is easier to write And read..
- LPisGood 3mo ago
  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.
  - palata 3mo ago
    Bad code is hard to read, that is orthogonal to the fact that it is recursive.
  - tikhonj 3mo ago
    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.
    - LPisGood 3mo ago
      Oh don’t worry it had more than a half dozen of those nested as well
veqq 3mo ago
Risky?
- makr17 3mo ago
  Presumably stack depth and overflow.
- mypalmike 3mo ago
  I once wrote a Xbox 360 indie game that would crash only in unusual situations due to stack overflow. The game involved essentially gluing together balls, and it would detect if the balls surrounded something. I used recursive DFS to check connectivity of the balls. And most of the time, there would be a couple dozen balls max connected. But you could definitely intentionally connect many many more balls if you wanted to. At a certain point, it would crash with a stack overflow. Changing it to not use recursion (explicit data structures) fixed the crash.
dreamcompiler 3mo ago
Tail recursive functions on a tail-jump optimized compiler can be as performant as loops. If the compiler was written by someone who has read the Steele papers, it generates the same assembly code in both cases.

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: n | result | # of calls 1 | 1 | 1 2 | 1 | 3 3 | 2 | 5 4 | 3 | 9 5 | 5 | 15 6 | 8 | 25 7 | 13 | 41 8 | 21 | 67 9 | 34 | 109 10 | 55 | 177 11 | 89 | 287 12 | 144 | 465 13 | 233 | 753 14 | 377 | 1219 15 | 610 | 1973 16 | 987 | 3193 17 | 1597 | 5167 18 | 2584 | 8361 19 | 4181 | 13529 20 | 6765 | 21891 A curious person will then calculate the actual ratio: n | result | # of calls | ratio 1 | 1 | 1 | 1 2 | 1 | 3 | 3 3 | 2 | 5 | 1.6666666666666667 4 | 3 | 9 | 1.8 5 | 5 | 15 | 1.6666666666666667 6 | 8 | 25 | 1.6666666666666667 7 | 13 | 41 | 1.64 8 | 21 | 67 | 1.6341463414634145 9 | 34 | 109 | 1.626865671641791 10 | 55 | 177 | 1.6238532110091743 11 | 89 | 287 | 1.6214689265536724 12 | 144 | 465 | 1.6202090592334495 13 | 233 | 753 | 1.6193548387096774 14 | 377 | 1219 | 1.6188579017264275 15 | 610 | 1973 | 1.6185397867104183 16 | 987 | 3193 | 1.6183476938672072 17 | 1597 | 5167 | 1.6182273723770748 18 | 2584 | 8361 | 1.6181536675053223 19 | 4181 | 13529 | 1.6181078818323167 20 | 6765 | 21891 | 1.6180796806859339 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ⁿ).

Chinjut 3mo ago
Yes, because the number of calls in this setup is 2 * the next result - 1, and the Fibonacci sequence itself grows at this Θ(φⁿ) rate.
veltas 3mo ago
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).

a-dub 3mo ago

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."

senkora 3mo ago
This exists in clang for C++ as the statement attribute [[clang::musttail]] and in gcc as [[gnu::musttail]]
winstonlee 3mo ago
Been a while since I last used it but there is @tailrec in Scala. The compiler does enforce it and optimize the resulting bytecode.
dataflow 3mo ago
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?
- vanviegen 3mo ago
  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.
  - dataflow 3mo ago
    This feels like a strawman and doesn't really attempt to answer my question. These kinds of broad generalizations really need good evidence/citation.

kelseyfrog 3mo ago

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.

n0blenote 3mo ago
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.
- kelseyfrog 3mo ago
  You're absolutely right. Recursion is tied to the shape of the data being recursed. It can be expressed a number of ways, but generally having a functor for the data type gives a lot of milage in operating over it. See https://github.com/passy/awesome-recursion-schemes https://github.com/passy/awesome-recursion-schemes for more of what I'm getting after.
Jhsto 3mo ago
I've been writing a language around recursion schemes! Insofar it's just a library for Lean, but I wish to one day release it as an array programming language. I'm submitting a thesis in ~3 months, after which I'll be open-sourcing it.

Chinjut 3mo ago

Recursion isn't lying to you. Rather, many JavaScript implementations are screwing you over.

xedrac 3mo ago
I suspect scheme would handle this much better.

10000truths 3mo ago

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.

abratabia 3mo ago

[flagged]

eventualcomp 3mo ago

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.

okzgn 3mo ago

Reference link: https://v8.dev/blog/modern-javascript#proper-tail-calls 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.

WolfeReader 3mo ago

The thread title should be updated to clarify that it's a JavaScript-specific article.