# 9. Recursion

A completely new possibility of Fortran 90 is recursion. Note that
it requires that you give a new property `RESULT ` for the output variable
in the function declaration. This output variable is
required inside the functions 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 recursive calculation of the
factorial, then recursive calculations of the Fibonacci-numbers. The
later is very inefficient. An efficient but not recursive method is
given by Brainerd,
Goldberg and Adams (1990), page 226.

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.
An interesting use of recursive technique is given by Brainerd,
Goldberg and Adams (1990), page 222, for the calculation of an
exponential function of a matrix. They give the immediate (straight
forward) expression, with the successive multiplication with a matrix,
and also 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 at 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.

Not only functions but also subroutines 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
from three numbers (all 1 at the start) and every time add
the three latest numbers to get the next one. Run
and calculate `TRIBONACCI (15)`. Note that the calculation time
grows very fast 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: 16 November 1995

`boein@nsc.liu.se`