Birbla

Comments

Hacker News

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

by RajT88

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

by a-dub

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.

by kelseyfrog

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

by ventana

Join the discussion

Write your take first — we'll ask for email only when you're ready to publish.

Sign in
  • Hacker News
  • CS 101, no? Recursion is easier to write, but less performant and more risky than iteration.
    by RajT88
  • 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."

    by a-dub
  • 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.

    by kelseyfrog
  • 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ⁿ).
    by ventana