2 ms·
Personally, I think that analogy conceals more than it reveals. Recursion in computer software requires nested definitions that eventually reach a simple base c
by 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.