Recursion is lying to you

RajT88

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

ventana

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ⁿ).

a-dub

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

kelseyfrog

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.

Chinjut

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

10000truths

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.

eventualcomp

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

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.

WolfeReader

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