A fun quote from the article, discussing a basic Fibonacci recursive implementation:<p>> Each call branches into two more calls, so the total number of calls grows as O(2ⁿ).<p>Well, no, not really. If anyone bothers counting how many recursive calls are <i>actually</i> made, the result is far from powers of two:<p><pre><code> 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
</code></pre>
A curious person will then calculate the actual ratio:<p><pre><code> 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
</code></pre>
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 <i>size</i> 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).
CS 101, no? Recursion is easier to write, but less performant and more risky than iteration.
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.<p>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.
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.<p>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."
[delayed]
This exists in clang for C++ as the statement attribute [[clang::musttail]] and in gcc as [[gnu::musttail]]
Been a while since I last used it but there is @tailrec in Scala. The compiler does enforce it and optimize the resulting bytecode.
Recursion isn't lying to you. Rather, many JavaScript implementations are screwing you over.