How recursion got into programming: a comedy of errors

The article doesn&#x27;t mention <i>why</i> people didn&#x27;t want recursion to be a requirement. It was probably because the idea of using a call stack was still controversial.<p>For instance, on a PDP-8 (released some years after ALGOL) the calling convention was that the return address was written to the word of memory before the called function. This was simple, but pretty much precludes recursive calls.<p>These days we take for granted that the CPU will provide some sort of stack pointer that gets automatically managed by a CALL&#x2F;RET instruction pair. Before that was provided in hardware, the compiler would have to do that itself. So if you decided to support recursion, you&#x27;d end up requiring a stack and adding a small cost to every function call.<p>Once you decide to have a stack, allowing recursion is a freebee so of course you&#x27;d include it.

This has some solid political advice courtesy of Peter Naur: If you want to get a committee to do what you want, show up with most of the work already done. That work became the starting point for all the future negotiations. And his influence on Algol-60 spec was a strong contributor to him receiving a Turing award years later.

There is a book called The Little Schemer (was The Little Lisper) - a book all about recursion. This is a quote from a review:<p><i>Little Schemer is without a doubt one of the best books I have ever read on the subject of recursion, and what is interesting because they never really go into a formal definition of what recursion is, as most texts on computer science try to. Instead they show the reader time and time again what recursion is, while providing a great series of rules (commandments) on how to get the most out of recursion, particually in a tail-recursive language like Scheme.</i> <a href="http://www.amazon.com/The-Little-Schemer-4th-Edition/product-reviews/0262560992/ref=cm_cr_dp_synop?ie=UTF8&amp;showViewpoints=0&amp;sortBy=bySubmissionDateDescending#RCZ626B7P2J1C" rel="nofollow">http:&#x2F;&#x2F;www.amazon.com&#x2F;The-Little-Schemer-4th-Edition&#x2F;product...</a><p>You can read more about The Little Lisper here: <a href="http://thelittlelisper.blogspot.com.au/2010/06/little-lisper-chapter-1-toys.html" rel="nofollow">http:&#x2F;&#x2F;thelittlelisper.blogspot.com.au&#x2F;2010&#x2F;06&#x2F;little-lisper...</a><p>Or you can read about working through it in Clojure here: <a href="http://juliangamble.com/blog/2012/07/20/the-little-schemer-in-clojure-chapter-1/" rel="nofollow">http:&#x2F;&#x2F;juliangamble.com&#x2F;blog&#x2F;2012&#x2F;07&#x2F;20&#x2F;the-little-schemer-i...</a>

It may seem trivial now, but when this was being considered stacks were not a built-in CPU feature. In fact I wonder what was the first architecture that included one?<p>The machine I learned assembler on would rewrite the instruction at the start of a function with a jump instruction to return to the caller. You returned from the function by jumping back to its beginning. Recursion wasn&#x27;t an option!

Recursion isn&#x27;t allowed for safety critical code in automotive or avionics applications<p><a href="http://spinroot.com/p10/rule1.html" rel="nofollow">http:&#x2F;&#x2F;spinroot.com&#x2F;p10&#x2F;rule1.html</a>

Peter Naur is actually The Unterminator: a robot from the future, in which machines running non-recursive programming languages ruled the world. SkyNet had hit the wall of complexity because it consisted of so much legacy code written in non-recursive FORTRAN. Its only means of recursion was to build a robot and send it back into the past to change the course of history, and introduce recursion into Algol, against the wishes of the wiser committee members who suspiciously and correctly viewed recursion as a means by which computers could take over the world.

To me recursive thinking was more important than recursive execution of functions. For instance, I find the recursive solving of the powerset function so appealing. ... (here in scheme).<p><pre><code> ;;; power set = power {set-X} as sub (+.) {X U sub} (define (power set) (if (null? set) &#x27;(()) (let ((sub (power (cdr set))) (augment (lambda (subset) (cons (car set) subset)))) (append (map augment sub) sub)))) </code></pre> Seeking self-similarity often lead to tiny solutions.

<p><pre><code> &gt; Ritchie relaxed the definition-before-use rule by allowing &gt; redundant declarations of procedure headings. At the &gt; expense of a redundant advance declaration the programmer &gt; can define mutually recursive procedures in C. </code></pre> Point of order: C didn&#x27;t have a declaration-before-use rule until C99. C had ‘implicit int’; no redundant declarations necessary.

This is a wonderful piece of computer science history, and is of interest less for its nominal topic (recursion) than for the insight it gives into an early slice of languages research. Well worth a full read.

The most interesting part of this story is considering what it would&#x27;ve been like if they decided to forbid recursion. Protecting the call stack from it would&#x27;ve been incredible overhead back then - either that or they would&#x27;ve had to enforce strict dependency ordered compilation and even then..<p>I imagine John McCarthy and the others who wanted recursion just sitting back and smiling, recognizing that that there was no need to press - it was just a matter of time.

How often is recursion used in everyday, imperative-style code? Do stack limits make it impractical to use?

So I guess, if we look past the topic of recursion itself - that the moral of the story is that design by committee works if kept in check by a benevolent dictator? Perhaps it works both ways: that a benevolent dictator can be properly grounded by a committee.

&quot;<i>For example, in [6] the lambda calculus is defined in 86 lines distributed over ten definitions. It seems clear in this compact definition that lambda calculus does not allow recursive function definitions. Yet already by 1935 at least two versions had been discovered of the Y combinator, an expression of the lambda calculus. And this combinator makes recursive function definitions possible in lambda calculus.</i>&quot;<p>My understanding was that without recursion the lambda calculus is not Turing-complete. Is that correct?<p>It should also be noted that recursion is a close relative of induction, an indispensable tool that is not without its own problematic history.

&quot;Oh whoops, I accidentally called this function inside of its self! Silly syntax error....but it looks like I traversed a binary tree...&quot;

I didn&#x27;t know that F.L. Bauer was against recursion :-) In 1996 I participated in a summer school where he attended the talks we gave (mine was about Petri nets). Funny to see him mentioned here as a figure of history.

re.curse <i>v.</i> To curse again.