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/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).
This is near causing dissonance for me. I'm certain I had seen a version of his where he did use recursion. Rereading, you are definitely correct that he doesn't.
I know he has program in one of his books where he uses recursion to print the contents of a tree. Maybe I was just confusing that. (Don't have my books handy.)
That said, this is definitely going to make me study those programs more. Hilarious how off I was in my memory.
(The use of goto statements like he does in the main routine cracks me up, btw. Curious to know if these made a measured difference. With Knuth, I would assume so.)
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).