Recursion – Fortran bends the rules

Until Fortran formally allowed recursion in Fortran 90, there were many ways of skirting the issue. One of the more interesting was that posed by John Morris in 1969 [1]. Fortran generally didn’t offer recursion as part of the languages abilities because recursive function calls required special treatment. The simplest solution, at least for the purpose of recursive mathematical functions is to turn the recursions into iterations. A factorial doesn’t need to be calculated in a recursive manner.

So things don’t convert very neatly into iterations, largely because their recursive definition is not easily thwarted. Instead of true recursion, which stores the return address in a stack, Morris suggested storing the arguments of the function in one or more stacks. He provided solutions to three such problems: (i) Ackerman’s function, (ii) a combinatorial problem, and (iii) calculating Kendall’s rank correlation coefficient tau. Ackermann’s function is of no real value, except for testing the ability of systems to handle hungry calculations (at least in early days). Here is the recursive function:

If m=0 then ACKER(0,n) = n+1
If m≠0 and n=0 then ACKER(m,0) = ACKER(m-1,1)
IF m≠0 and n≠0 then ACKER(m-1,ACKER(m,n-1))

Here is Morris’s “recursive” version of the Ackerman function:

      FUNCTION ACKER(M,N)   
      COMMON /SCTCH/ STAK(3000)   
      ACKER=0.   
      IF(M.LT.0.OR.N.LT.0) RETURN   
      ACK=0.   
      XM=M   
      XN=N   
      INDEX=0
    7 IF(XM.GT..01) GO TO 3   
      ACK=XN+1   
      IF(INDEX.GE.1) GO TO 4   
      ACKER=ACK   
      RETURN
    3 IF(XN.GT..01) GO TO 5   
      XM=XM-1.   
      XN=1.   
      GO TO 7 
    5 IF(INDEX.LT.3000) GO TO 6   
      WRITE(*,*) 'STACK CAPACITY EXCEEDED'   
      ACKER=0.   
      RETURN 
    6 INDEX=INDEX+1   
      STAK(INDEX)=XM-1.   
      XN=XN-1.   
      GO TO 7 
    4 XM=STAK(INDEX)   
      XN=ACK   
      INDEX=INDEX-1   
      GO TO 7   
      END

The program stores the values of m-1 in the stack STAK, while evaluating the right-hand argument in the last form of the function, then returning to the stack to retrieve the value. It is in essence, a form of recursive iteration.

[1] Morris, J., “Programming recursive functions in Fortran”, Software Age, 3(1), pp.38-42 (1969)

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.