4 ms·

> I can't imagine programming without the knowledge of how things work at assembly level. The author's point is that recursion is a pervasive concept that is e

> I can't imagine programming without the knowledge of how things work at assembly level. The author's point is that recursion is a pervasive concept that is essential to understand even how modern computer hardware works: > the very concept of a digital computer is grounded in recursive self-reference (the cross-connection of gates to form a latch), which, needless to say, does not involve a stack. Not only do real programmers use recursion, there could not even be programmers were it not for that. The author is not suggesting that we forget about "what's really going on". He's rightly pointing out that you actually cannot understand what's really going on at all without first understanding recursive self-reference.

michaelt 11y ago
Personally, I think that analogy conceals more than it reveals. Recursion in computer software requires nested definitions that eventually reach a simple base case resulting in termination. An sram cell or J/K flip-flop, on the other hand, doesn't involve nesting or reach a simple base case. In my mind recursion is a snake that has eaten a smaller snake, whereas an sram cell is a snake eating its own tail.
- chriswarbo 11y ago
  > Recursion in computer software requires nested definitions that eventually reach a simple base case resulting in termination. I think you've just illustrated the article's point. You're describing well-founded recursion, which is very useful, but doesn't include e.g. continuation-passing ( https://en.wikipedia.org/wiki/Continuation-passing_style https://en.wikipedia.org/wiki/Continuation-passing_style ) or co-recursion ( https://en.wikipedia.org/wiki/Corecursion https://en.wikipedia.org/wiki/Corecursion ), hence perpetuating the myths the article is complaining about. The really unfortunate thing is that sub-sets of these ideas keep getting re-invented (AKA "reinventing the square wheel"), for example exception handlers in place of continuations, iterable objects in place of co-recursive data, etc. As for J/K flip-flops, they're recursive because their output is their own input. For example, given co-inductive stream of `j` and `k` values (the flip-flop inputs), we can generate a co-inductive stream of outputs `q`: function flipflop(init_js, init_ks) { function ff(js, ks, q_old) { var j = car(js); var k = car(ks); var q_new = j * not(q_old) + not(k) * q_old; return cons(q, ff(cdr(js), cdr(ks), q_new); } return ff(init_js, init_ks, 0); // Initiate the co-recursion with 0, arbitrarily } Whilst I've used co-recursive data for convenience, the fact that the result `q_new` becomes the argument `q_old` for the next call is unavoidably recursive.

michaelt 11y ago

Personally, I think that analogy conceals more than it reveals. Recursion in computer software requires nested definitions that eventually reach a simple base case resulting in termination. An sram cell or J/K flip-flop, on the other hand, doesn't involve nesting or reach a simple base case. In my mind recursion is a snake that has eaten a smaller snake, whereas an sram cell is a snake eating its own tail.

chriswarbo 11y ago
> Recursion in computer software requires nested definitions that eventually reach a simple base case resulting in termination. I think you've just illustrated the article's point. You're describing well-founded recursion, which is very useful, but doesn't include e.g. continuation-passing ( https://en.wikipedia.org/wiki/Continuation-passing_style https://en.wikipedia.org/wiki/Continuation-passing_style ) or co-recursion ( https://en.wikipedia.org/wiki/Corecursion https://en.wikipedia.org/wiki/Corecursion ), hence perpetuating the myths the article is complaining about. The really unfortunate thing is that sub-sets of these ideas keep getting re-invented (AKA "reinventing the square wheel"), for example exception handlers in place of continuations, iterable objects in place of co-recursive data, etc. As for J/K flip-flops, they're recursive because their output is their own input. For example, given co-inductive stream of `j` and `k` values (the flip-flop inputs), we can generate a co-inductive stream of outputs `q`: function flipflop(init_js, init_ks) { function ff(js, ks, q_old) { var j = car(js); var k = car(ks); var q_new = j * not(q_old) + not(k) * q_old; return cons(q, ff(cdr(js), cdr(ks), q_new); } return ff(init_js, init_ks, 0); // Initiate the co-recursion with 0, arbitrarily } Whilst I've used co-recursive data for convenience, the fact that the result `q_new` becomes the argument `q_old` for the next call is unavoidably recursive.