# 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)

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