9. Recursion

A completely new capability of Fortran 90 is recursion. Note that it requires that you assign a new property RESULT to the output variable in the function declaration. This output variable is required inside the function as the "old" function name in order to store the value of the function. At the actual call of the function, both externally and internally, you use the outer or "old" function name. The user can therefore ignore the output variable.

Here follows two examples: first the recursive calculation of factorials, then the recursive calculations of the Fibonacci-numbers. The later is very inefficient. Brainerd, Goldberg and Adams (1990), page 226, propose an efficient, but non-recursive method.

The listings of the routines follow. The output variables are called FAC_RESULT and FIBO_RESULT, respectively.

       RECURSIVE FUNCTION FACTORIAL(N) RESULT (FAC_RESULT)
       IMPLICIT NONE
       INTEGER, INTENT(IN)      :: N
       INTEGER                  :: FAC_RESULT
       IF ( N <=1 ) THEN
               FAC_RESULT = 1
       ELSE
               FAC_RESULT = N * FACTORIAL(N-1)
       END IF
       END FUNCTION FACTORIAL

       RECURSIVE FUNCTION FIBONACCI(N) RESULT (FIBO_RESULT)
       IMPLICIT NONE
       INTEGER, INTENT(IN)      :: N
       INTEGER                  :: FIBO_RESULT
       IF ( N <= 2 ) THEN
               FIBO_RESULT = 1
       ELSE
               FIBO_RESULT = FIBONACCI(N-1) + FIBONACCI(N-2)
       END IF
       END FUNCTION FIBONACCI

The reason that the above calculation of the Fibonacci-numbers is so inefficient is that each call with a certain value of N generates two calls for the routine, which in its turn generates four calls, and so on. Old values (or calls) are not re-used.

On page 222 Brainerd, Goldberg and Adams (1990) demonstrate an interesting use of recursive technique for the calculation of an exponential function of a matrix. They give the immediate (straight forward) expression, with the successive multiplication with a matrix, as well as a recursive variant, which can pick out the suitable squares to optimize the calculation. Recursion is also excellent to code an adaptive algorithm, see exercise (9.2) below.

Another very important usage of the RESULT property and the output variable is with array valued functions. It is very easy to specify an output variable so that it can store all the values of such a function. Actually, it is the combination of recursive functions and array valued functions that have forced the committee to introduce the RESULT property.

We note that not only functions, but subroutines too, can be recursive.

Exercises

(9.1) Write a routine for the calculation of Tribonacci numbers. These are formed like the Fibonacci-numbers, but you start with three numbers (all 1 at the start). At each step you then add the last three numbers to get the next one. Run and calculate TRIBONACCI(15). Note that the calculation time increases very quickly with the argument.
Solution.

(9.2) Write an adaptive routine for quadrature, i.e. calculation of a definite integral on a certain interval.
Solution.

Last modified: 6 April 1998
boein@nsc.liu.se