hackernews client

Recursion is lying to you

29 pointsposted 9 hours ago

by theanonymousone

(blog.gaborkoos.com)

41 Comments

ventana

8 hours 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

8 hours 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

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

recursive

6 hours ago

Big O analysis never implies size in bits. It's just often done. In this case, n is just the numerical value of the input, so I don't think this is correct.

RajT88

8 hours ago

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

valleyer

8 hours ago

It's not CS 101 that JavaScript apparently sucks at TCO. That was surprising to me.

dnbfbfhf

8 hours ago

The CS 101 model of computing doesn’t have TCO… which makes it pretty accurate to the real world.

ckcheng

7 hours 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

[2]: https://stackoverflow.com/a/37224563

[3]: https://stackoverflow.com/a/34097339

[4]: https://stackoverflow.com/a/3114245

ignoramous

6 hours ago

Heh, reminds me of this talk at !!conf: Tail Call Optimization: The Musical, https://youtu.be/-PX0BV9hGZY (2019).

dreamcompiler

2 hours 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.

sras-me

8 hours ago

>Recursion is easier to write

And read..

LPisGood

7 hours 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

7 hours ago

Bad code is hard to read, that is orthogonal to the fact that it is recursive.

tikhonj

6 hours 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

6 hours ago

Oh don’t worry it had more than a half dozen of those nested as well

veqq

8 hours ago

Risky?

mypalmike

4 hours 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.

makr17

8 hours ago

Presumably stack depth and overflow.

eventualcomp

6 hours 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.

10000truths

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

okzgn

6 hours ago

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.

kelseyfrog

7 hours 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

6 hours 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

5 hours 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 for more of what I'm getting after.

Jhsto

4 hours 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.

WolfeReader

6 hours ago

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

a-dub

8 hours 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

8 hours ago

This exists in clang for C++ as the statement attribute [[clang::musttail]] and in gcc as [[gnu::musttail]]

dataflow

7 hours 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?

a-dub

7 hours ago

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?

dataflow

6 hours ago

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

a-dub

6 hours ago

let me try arguing it this way: it is impossible for a non-tail-call-optimized recursion to use constant space. the stack grows with O(depth) and therefore memory usage does as well. a consequence of this is that the finite storage lru caches and registers are polluted with one-time-use variables which reduces their availability for actually useful caching.

it IS possible for a loop to use constant space. pre-allocate temporaries and inline any function calls. everything lives in one stack frame. simply iterating the loop itself does not come with fixed space overheads from allocating new stack frames.

i suppose one thing i should mention, i am thinking of extreme optimization use cases where the entire data structure fits in cache (or close to it). think like in-cache tries or similar. if you're hitting main memory with each iteration anyway, it doesn't really matter.

dataflow

5 hours ago

> let me try arguing it this way: it is impossible for a non-tail-call-optimized recursion to use constant space. [...]

What you're really saying here is that if you have a non-tail-call-optimizing compiler (i.e. if your compiler and/or language suck at optimizing recursion), and your algorithm uses enough stack space that the resulting cache pollution affects the performance (absolutely not every algorithm falls in this bucket!), then recursion is likely (not certain!) to be slower than recursion.

I'm sure you know that even your first assumption immediately fails for all the (many) tools that handle tail-recursion just fine. Isn't it then a gross overgeneralization to just claim "iterative algorithms are faster than recursive ones", as if your situation is universally representative of everyone's?

> i suppose one thing i should mention, i am thinking of extreme optimization use cases where the entire data structure fits in cache (or close to it). think like in-cache tries or similar. if you're hitting main memory with each iteration anyway, it doesn't really matter.

FWIW, the scenario you're imagining is even more niche than that. You're assuming a case where, for example, the hardware prefetcher isn't able to predict (or doesn't have enough bandwidth to) fetch the next cache line before you need it. You're also assuming the data structure is large enough (or your access pattern unlucky enough) that cache misses are actually affecting you -- i.e. not just "fits in cache", but takes up most of the room, too. You're also assuming that compilers are equally good at optimizing recursion and iteration (aside from tail-recursion), which is also not true -- for example, large functions tend to get optimized more poorly than smaller ones (including more stack accesses!), and your iteration is much more likely result in large functions being generated.

Are there situations in which your assumptions hold? Definitely. Are you way, way overgeneralizing? Sure looks like that too.

rstuart4133

4 hours ago

I'm not the OP, but I think he's saying something much simpler than that. Typically with a recursive algorithm, the state you need to push is tiny. Usually a word or two. But often you need a lot of temporaries to calculate that state.

If you use recursion, both the absolutely necessary state and the temporaries are pushed onto the stack (along with the stack frame the language runtime wants). If you use iteration, the programmer just pushes the necessary state onto the stack, and reuses the temporaries in place.

The rest of his claims follow from those facts. Space consumption is less because you are saving less. Cache locality is better both because the temporaries aren't scattered across the stack, and because you are reusing the same locations over and over again.

The downside of iterative solutions is stacks are more efficient memory allocators than heap algorithms - especially if you are forced to grow the array your pushing things onto many times. But if you know that in advance so you can allocate the full amount up front, then at the limit when N -> ∞ iteration will always win over recursion.

vanviegen

7 hours 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

6 hours 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.

palata

7 hours ago

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