4 ms·

Oh sorry, to be clear, by "his idea of it" I meant "the way he thinks about it [recursion]". What's different is that when most people learn programming, they p

• taeric 8y ago
  I think some of this is likely to be a product of the times. The vast majority of early programming languages were not friendly to recursion. It wasn't at all uncommon for functions not to be reentrant, and to rely on self manipulation to set the return stack, if I recall. Even today, for many "systems level" programs, you have to take extreme care around recursion, since you are likely to blow the stack limits. (That is, you can't just use recursion freely, but instead have to prove the maximum depth that you will trigger it.) That is to say, I don't see what makes this different than how most others view recursion. If you can afford to do it, then you should do so. If you can't, then you should be ready for a lot of his other tricks. (Threaded trees being my personal favorite, at the moment. DFS with no stacks? Crazy talk! :) )
  • svat 8y ago
    Definitely a product of his times (like everyone). Let me put it this way: to my knowledge, Knuth is the only programmer from his times, still writing, programming, and writing about programming. So you get a 1960s perspective from someone who's seen (and programmed in) 2018; that's not very usual. (BTW I'm not sure that Knuth would wholeheartedly agree with “If you can afford recursion, then you should use recursion”. Perhaps he'd consider the program half-written. That's in some sense the crux of what I think is different.) Let me put it another way: I thought I knew how to generate all permutations of a set of numbers. When I saw questions about it on Stack Overflow or Quora, I answered. When I opened Volume 4A, it disposed of what I knew in the first half-page, and proceeded to discuss the problem for over 50 more pages. I thought I knew about backtracking, having written backtracking programs hundreds of times (always implemented using recursion). Knuth's section on backtracking obliterated everything I knew (and with no recursion in sight). So I'm looking forward to when he gets around to writing about recursion, to see what I can (un)learn about something so fundamental.
    • taeric 8y ago
      His dlx algorithm makes heavy use of recursion. As do many of his cweb programs. In one, he comments it as "textbook" stuff. Your point on him being one of the main programmers from his time still programming is fair.
      • svat 8y ago
        Ah but see, his DLX program is not written using recursion! Look at his CWEB program dance.w from his website (or if you don't have cweave handy, download the program from here: https://github.com/shreevatsa/knuth-literate-programs/blob/master/programs/dance.pdf https://github.com/shreevatsa/knuth-literate-programs/blob/m... and click around on the hyperlinks) — all the backtracking happens inside “main”; there are only two subroutines “cover” and “uncover”, and neither of them is recursive. Here is what he says in the (very early) draft of fasc16a (only 2.5 pages written): > We've already seen hundreds of examples of recursion in previous chapters. Early on, we encountered sequences of numbers that were defined by relating each member to earlier members after getting started; these “recurrence relations” were sometimes simple formulas like […], sometimes more involved like […], and sometimes considerably more elaborate and complex. We also found that basic data structures for trees are inherently recursive, because all but the simplest trees are composed of subtrees. We discussed numerous instances where problems of sorting or searching or optimization could be solved effectively by a “divide and conquer” approach, with which a large problem is reduced to smaller problems of the same kind. > Yet we didn't dwell on the recursive nature of those concepts. We transformed them into equivalent notions that could be dealt with directly and nonrecursively. Because “at bottom” a computer operates by means of the physical properties of electrons, which are not recursive. > For example, in Algorithm 2.3.1T we traversed the nodes of a binary tree by using an auxiliary stack A, not by using the recursive definition of symmetric order to define that algorithm in terms of itself. Don't want to quote the whole thing (though there isn't much), but from the sample I feel I'm going to learn from a new perspective (new to me, anyway).
• black-tea 8y ago
  It's completely bizarre that it is taught in this way. Knuth is absolutely right. Recursion is easy but the problem is computers don't actually work that way. I don't understand how anyone who has programmed for a while can think recursion is the cool or tricky thing to do. Even worse is that recursion is taught using stupid examples like the fibonacci numbers rather than something that actually needs it like quicksort.
  • svat 8y ago
    I agree: as much as I love the Fibonacci numbers, it's better to teach recursion with something like (say) implementing directory traversal (printing all files under a current directory, like ls -R) -- some problem both where the recursive nature of the problem itself is obvious, and where it would be more awkward to implement without recursion. I'm looking forward to seeing what problems he thinks really merit recursion.