Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Recursion is lying to you

blog.gaborkoos.com

Post reply on HN
Print view View original

11–20 of 51 posts

Re: Recursion is lying to you

#11

Post by senkora »

a-dub wrote: post #9

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…

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

Re: Recursion is lying to you

#12

Post by kelseyfrog »

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.

Re: Recursion is lying to you

#14

Post by veltas »

ventana wrote: post #8

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…

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

Re: Recursion is lying to you

#15

Post by winstonlee »

a-dub wrote: post #9

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…

Been a while since I last used it but there is @tailrec in Scala. The compiler does enforce it and optimize the resulting bytecode.

Re: Recursion is lying to you

#16

Post by dataflow »

a-dub wrote: post #9

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…

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?

Re: Recursion is lying to you

#17

Post by LPisGood »

sras-me wrote: post #4
RajT88 wrote: post #2

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

>Recursion is easier to write And read..

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.

Re: Recursion is lying to you

#18

Post by palata »

LPisGood wrote: post #17
sras-me wrote: post #4

Earlier quoted context omitted.

>Recursion is easier to write And read..

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.

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

Re: Recursion is lying to you

#19

Post by palata »

a-dub wrote: post #9

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…

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

Re: Recursion is lying to you

#20

Post by 10000truths »

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.
Post reply on HN