Recursion is lying to you(blog.gaborkoos.com) |
Recursion is lying to you(blog.gaborkoos.com) |
> 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
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
Proper Tail Calls were implemented behind experimental flags but never shipped by default — the flags were later removed.
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.
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.
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.
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
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.
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.
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.