Recursion – the ALGOL60 years

Algol 60 was the first imperative language to truly embrace the concept of recursion. Early on, very little was written about it though. One of the earlier textbooks on ALGOL, “Introduction to Algol Programming“, written by Torgil Ekman and Carl-Erik Fröberg, and published in 1965. Its section on recursion took up less than a page, basically provided a very brief explanation of the form:

If a procedure is constructed in such a way that it calls itself either directly or through another procedure it is said to be recursive.

pp.86 of Introduction to Algol Programming

The example provided was a Chebyshev polynomial with the formulas: T(0) = 1; T(1) = x; T(n) = 2xT(n-1)-T(n-2). Here is the Algol code:

They don’t really provided anything in the way of an explanation or how recursion works, but they do note that “The recursive description is often more elegant, but on the other hand we can expect object programs which demand longer running times on a computer.” They suggested writing recursive procedures in iterative form, because in many instances the compilers did not as yet have recursion implemented. (Side-note: in the 1960s, languages were often published as specs, which people used to build compilers on their particular machines, hence all the versions of Algol).

In the 1965 edition of “An Introduction to Algol Programming“, the authors (Wooldridge and Ractliffe) note that “a procedure can in particular make use of itself“. They illustrate recursion using a function which calculates the sum of the cubes of the first n positive integers.

They describe the functionality as sumcubes() calling itself if n≠0. So sumcubes(4) would result in sumcubes being assigned the value 4³+sumcubes(3), etc. Their take on this is that while this illustrates the elegance of ALGOL, it is not the most rapid means of calculating this summation, for that iteration is better.

What is clear from these texts is that recursion was considered a fun thing to try, but not to be considered in any serious manner. This was largely due to the system resources that would be required. Why would such resources be expended when an iterative solution would be faster?

By the late 1960s, recursion had still not caught on. Practical Programming by Corbett and Tinsley (1968) includes a program for calculating the highest common factor (HCF) between two numbers, but does not actually describe the process of recursion (I guess it is left to the reader to decipher).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.