Recursion

Ordinary FORTRAN procedures (subroutine and function) are not recursive, i.e., they cannot invoke themselves in their body. We can use the RECURSIVE keyword to implement recursive procedures.

Recursive subroutine

Calculate factorial using recursive subroutine:

src/21_recursive_subroutine.f90

! Calculate factorial
!      | n(n -1)  n >= 1 
! n! = |
!      | 1        n = 0
PROGRAM recursive_subroutine
    IMPLICIT NONE
    INTEGER :: input, output

    PRINT *, "This program calculates factorial:"
    PRINT '(a,$)', "Input = "
    READ *, input

    CALL factorial(input, output)

    PRINT *, input, "! = ", output

CONTAINS
    RECURSIVE SUBROUTINE factorial(n, result)
        INTEGER, INTENT(IN) :: n
        INTEGER, INTENT(OUT) :: result
        INTEGER :: tmp

        IF (n >= 1) THEN
            CALL factorial(n-1, tmp)
            result = n * tmp
        ELSE
            result = 1
        END IF
    END SUBROUTINE factorial
END PROGRAM recursive_subroutine

Recursive function

Calculate fibonacci series using recursive function:

src/21_recursive_function.f90

! Fibonacci series
! F(0) = 0
! F(1) = 1
! F(n) = F(n-1) + F(n-2)  for n > 1
PROGRAM recursive_function
    IMPLICIT NONE
    INTEGER :: lim, i

    PRINT *, "This program calculates fibonacci series:"
    PRINT '(a,$)', "Limit = "
    READ *, lim

    DO i = 0, lim
        PRINT *, "Fib(", i, ") = ", fibonacci(i)
    END DO

CONTAINS
    RECURSIVE FUNCTION fibonacci(n) RESULT(output)
        INTEGER, INTENT(IN) :: n
        INTEGER :: output

        IF (n > 1) THEN
            output = fibonacci(n - 1) + fibonacci(n - 2)
        ELSE IF (n == 1) THEN
            output = 1
        ELSE
            output = 0
        END IF
    END FUNCTION fibonacci
END PROGRAM recursive_function