Michael Harrison recently wondered why recursion was emphasized so much in Scheme and noted that it was perfectly natural for a language designed to model algorithms to do so. Notice the repetitive application inherent in Euclid’s algorithm: “Given two natural numbers a and b, not both equal to zero: check if b is zero; if yes, a is the gcd. If not, repeat the process using, respectively, b, and the remainder after dividing a by b.” Notice that step 6 of the Sieve of Eratosthenes is to “Repeat steps 4 and 5 until no more numbers are left in List A.” Step three of the Babylonian method for calculating square roots is “Repeat step 2 until r and x / r are as close as desired.” From the dawn of mathematical thought, recursion has naturally emerged in the study of algorithms. A computer language built to express algorithms concisely would necessarily include recursion.

But can’t we do without recursion in a programming language? Aren’t FOR…NEXT loops and DO…UNTIL loops sufficient? Those are nice friendly abstractions, of course, but they are just two special case forms of iteration. As we see in SICP lecture 1b (and section 1-2 in the book), recursive functions can be used to define any recursive or iterative process. Simpler language concepts will allow you to get by on most business programming assignments, but sooner or later you’ll come to a problem where you will actually need recursion to solve it. It is better to be fluent in the more general tool than to limit your mind to expressing itself with a small subset of what is possible.

But there’s something deeper here than the convulsions of Blub programmers sparing with smug functional dweebs. Recursion lies in the very heart of the “accurate reckoning for inquiring into things, and the knowledge of all things, mysteries… all secrets.” Recursive functions are the only functions that can be computed mechanically: Alonzo Church developed his lambda calculus in order to explore function definition, application, and recursion. Thanks to his work on the lambda calculus and to the work of Kurt Godel, he was able to demonstrate that Hilbert’s famous Entscheidungsproblem was impossible to solve. All known computational processes are equivalent to lambda calculus and Turing machines… and both of those have been shown to be equivalent to recursion.

Later on, John McCarthy (who was a student of Church) used the lambda calculus as a basis for the Lisp programming language. Recursion is inescapable in any dialect of Lisp. Not only is the list data type itself defined recursively (as Chuck Hoffman recently pointed out), but as we are reminded in SICP lecture 1-b, the evaluation process of Lisp is defined recursively as well. I expect recursion to be a continuing theme in the course as our work culminates into an understanding of the Metacircular Evaluator. At any rate, given the title of Macarthy’s original paper on Lisp, it is evident that the language itself is designed primarily as a means of expressing recursive functions.

As ~~Leo Comerford~~ Matthias Benkard said, “Lisp, in its most general sense, is a uniform notation for programs.” SICP will gradually develop our ability to think and implement code in Metalinguistic terms. Theoretically, this will allow us to conceptualize and solve problems without having our minds hindered by the limitations of procedural, OOP, or even functional methodologies– even while we cherry pick from those approaches whenever we feel inclined. Lisp’s homoiconic and multi-paradigmatic nature would seem to facilitate such thinking. It seems to me that someone who had mastered such techniques would be quite far from being “restricted and narrow-minded.”

September 27, 2007 at 1:20 am |

Actually that was the commenter below me, Matthias Benkard.

September 27, 2007 at 10:22 pm |

Sorry about that; I’ve corrected the post.