7 points | by theanonymousone an hour ago
7 comments
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
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
CS 101, no? Recursion is easier to write, but less performant and more risky than iteration.
It's not CS 101 that JavaScript apparently sucks at TCO. That was surprising to me.
The CS 101 model of computing doesn’t have TCO… which makes it pretty accurate to the real world.
>Recursion is easier to write
And read..
Risky?
Presumably stack depth and overflow.
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:
A curious person will then calculate the actual ratio: 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ⁿ).CS 101, no? Recursion is easier to write, but less performant and more risky than iteration.
It's not CS 101 that JavaScript apparently sucks at TCO. That was surprising to me.
The CS 101 model of computing doesn’t have TCO… which makes it pretty accurate to the real world.
>Recursion is easier to write
And read..
Risky?
Presumably stack depth and overflow.