Recursion – the trouble with early Fortran

While various ALGOL compilers allowed recursion, Fortran didn’t, or at least not in the 1960s or 70s. Basically in Fortran a subprogram could not call itself, neither could a subprogram A call subprogram B, which then calls subprogram A.

The design of Fortran never considered the possibility of implementing recursion. Even though Fortran II evolved at the same time as Lisp, it may have been a concept too early for inclusion into Fortran. Both direct and indirect recursion were forbidden until Fortran 90. But why did Fortran have issues with recursion? When a subroutine or function is called, its return address is stored. Control is handed back to this address when the return statement in the function being called is invoked. In early versions of Fortran, the subroutine or function could only store one return address at a time. Recursion is therefore not possible, because a stack of return addresses would be required. In addition, if the function or subroutine contains local variables, then these too must be stored on a stack, so they may be restored when the recursive call is ended. 

In 1963 James Ayers wrote a small article in Communications of the ACM, “Recursive Programming in Fortran II”, describing a technique that would “…draw the poison from the Fortraner’s wounds by allowing them to recurse to their complete satisfaction.”. But these techniques were specific to the compiler being used. IBM’s System/360 Fortran IV language manual of 1966 identified recursion as an “invalid statement function definition”.

BAD(A,B)=A+B+BAD(C,D)      (recursive definition not permitted)

In 1969 Herbert Kugel wrote an article in Software Age [1] exploring the notion of recursive subroutines in Fortran on IBM’s System 360, which did allow recursion (however it used two assembly language subroutines, SET and RESET, that dealt with the problem of saving and restoring the initial contents of the general registers).

One of the key differences between Algol 60 and Fortran was storage allocation, and this is necessary in order to appreciate the difference between the languages in their treatment of subprograms. Fortran was designed so that the storage requirements of the program were calculated at run-time. The storage requirements were therefore fixed. In Algol conversely, storage requirements are not calculated at compile time – the language makes allowances for requisitioning storage space at runtime. This convergence means that some capabilities available to the Algol 60 programmer were not available to the Fortran programmer. 

[1] Kugel, H.C., “An experimental approach to recursive fortran subroutine programming under operating system 360”, Software Age, 3(12), pp.14-17 (1969)

Leave a Reply

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

You are commenting using your 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.