Fortran recursion
last modified November 14, 2026
A recursive procedure solves a problem by solving a smaller copy of
the same problem. It needs two parts: a base case, a small input whose
answer is known directly, and a recursive case, which reduces the
input and calls the procedure again. The calls pile up until the base case is
reached, and the answers are then combined on the way back. Fortran has
supported recursion since Fortran 90, and a procedure that calls itself must be
declared with the recursive keyword; gfortran rejects the program
otherwise, even in Fortran 2018 mode.
This article computes factorials and Fibonacci numbers, solves the Towers of Hanoi, evaluates the Ackermann function, sums and searches an array, reverses and checks strings, and finally adds a cache so that a recursive function stops repeating work. The examples also show the price of recursion: every pending call occupies memory, and a naive implementation can be exponentially slower than a careful one.
A function that calls itself
The factorial of n is the product of all integers from 1 to
n. The recursive definition is shorter: the factorial of 0 or 1 is
1, and the factorial of n is n times the factorial of
n - 1. The function below follows that definition literally, and
the recursion stops when the argument reaches 1. A module variable counts the
calls so that the program can show how many frames the recursion needed.
module facts
implicit none
private
public :: fact, calls
integer :: calls = 0
contains
recursive integer function fact(n) result(r)
integer, intent(in) :: n
calls = calls + 1
if (n <= 1) then
r = 1
else
r = n * fact(n - 1)
end if
end function fact
end module facts
program r1
use facts
implicit none
print '(a, i0, a, i0)', '5! = ', fact(5), ', calls ', calls
calls = 0
print '(a, i0, a, i0)', '12! = ', fact(12), ', calls ', calls
print '(a, i0)', 'huge(0) = ', huge(0)
calls = 0
print '(a, i0, a, i0)', '13! = ', fact(13), ', calls ', calls
end program r1
Five factorial takes five calls, one per value from 5 down to 1, and returns
120. Twelve factorial is 479001600 and takes twelve calls. The last line shows
the limit of the default integer kind: 13 factorial is 6227020800, far above
huge(0), and the value that appears is the wrapped result of an
overflow. A recursive function is no protection against a result that does not
fit its type; the type must be chosen for the largest answer the program
expects, which the big integers article takes up.
$ gfortran r1.f90 -o r1 $ ./r1 5! = 120, calls 5 12! = 479001600, calls 12 huge(0) = 2147483647 13! = 1932053504, calls 13
The cost of naive recursion
The Fibonacci numbers have an equally simple recursive definition: the first
two are 0 and 1, and every later one is the sum of the previous two. Written
directly, the function calls itself twice per step, so the same values are
computed again and again. The number of calls grows exponentially even though
the answer grows only exponentially in the value of n, which makes
this the standard warning example for recursion.
module fibs
implicit none
private
public :: fib, calls
integer :: calls = 0
contains
recursive integer function fib(n) result(r)
integer, intent(in) :: n
calls = calls + 1
if (n < 2) then
r = n
else
r = fib(n - 1) + fib(n - 2)
end if
end function fib
end module fibs
program r2
use fibs
implicit none
integer :: n
do n = 5, 10
calls = 0
print '(a, i2, a, i4, a, i6)', 'fib(', n, ') = ', fib(n), &
', calls ', calls
end do
end program r2
The answers are correct, but the call count explodes: 15 calls for
fib(5) and 177 for fib(10), roughly doubling with each
extra step. A loop that keeps the last two values would compute the same
numbers in ten additions, and the caching example at the end of the article
reaches the same effect while keeping the recursive definition. Recursion is a
way to express a solution, not a promise that the computer will do less work.
$ gfortran r2.f90 -o r2 $ ./r2 fib( 5) = 5, calls 15 fib( 6) = 8, calls 25 fib( 7) = 13, calls 41 fib( 8) = 21, calls 67 fib( 9) = 34, calls 109 fib(10) = 55, calls 177
The Towers of Hanoi
The Towers of Hanoi puzzle has three pegs and a stack of disks of different
sizes, and the task is to move the whole stack to another peg, one disk at a
time, never placing a larger disk on a smaller one. The recursive solution is
famous for its brevity: move the top n - 1 disks out of the way,
move the largest disk to the target, then move the smaller stack onto it. Two
recursive calls and one move are enough, and no loop appears anywhere.
module hanoi_mod
implicit none
private
public :: hanoi, moves, trace
integer :: moves = 0
logical :: trace = .false.
contains
recursive subroutine hanoi(n, from, to, via)
integer, intent(in) :: n
character(len=*), intent(in) :: from, to, via
if (n == 0) return
call hanoi(n - 1, from, via, to)
moves = moves + 1
if (trace) print '(a, i0, a, a, a, a)', 'move disk ', n, &
' from ', from, ' to ', to
call hanoi(n - 1, via, to, from)
end subroutine hanoi
end module hanoi_mod
program r3
use hanoi_mod
implicit none
trace = .true.
call hanoi(3, 'A', 'C', 'B')
print '(a, i0)', 'moves for 3 disks: ', moves
trace = .false.
moves = 0
call hanoi(10, 'A', 'C', 'B')
print '(a, i0)', 'moves for 10 disks: ', moves
moves = 0
call hanoi(20, 'A', 'C', 'B')
print '(a, i0)', 'moves for 20 disks: ', moves
end program r3
Seven moves solve three disks, which is 2**3 - 1; ten disks need
1023 moves and twenty need 1048575, again one less than a power of two. The
recursion tree has a call for every move plus the calls that do nothing,
because a call with n = 0 returns at once. The count is computed
by incrementing a module variable at each real move, so the printed numbers are
the number of print statements the verbose version would execute.
$ gfortran r3.f90 -o r3 $ ./r3 move disk 1 from A to C move disk 2 from A to B move disk 1 from C to B move disk 3 from A to C move disk 1 from B to A move disk 2 from B to C move disk 1 from A to C moves for 3 disks: 7 moves for 10 disks: 1023 moves for 20 disks: 1048575
A function that grows very fast
The Ackermann function is a classic exercise because it is not primitive
recursive: its definition nests one call inside the argument of another, and
the result grows faster than any tower of exponentials. The three cases are
ack(0, n) = n + 1, ack(m, 0) = ack(m - 1, 1), and
ack(m, n) = ack(m - 1, ack(m, n - 1)). It is a good test of a
compiler's call handling, and a good reminder that a short definition can hide
an enormous amount of work.
module ackermann_mod
implicit none
private
public :: ack, calls
integer :: calls = 0
contains
recursive integer function ack(m, n) result(r)
integer, intent(in) :: m, n
calls = calls + 1
if (m == 0) then
r = n + 1
else if (n == 0) then
r = ack(m - 1, 1)
else
r = ack(m - 1, ack(m, n - 1))
end if
end function ack
end module ackermann_mod
program r4
use ackermann_mod
implicit none
integer :: ms(4) = [0, 1, 2, 3], ns(4) = [0, 2, 3, 3], i
do i = 1, size(ms)
calls = 0
print '(a, i0, a, i0, a, i0, a, i0)', 'ack(', ms(i), ', ', ns(i), &
') = ', ack(ms(i), ns(i)), ', calls ', calls
end do
end program r4
Even the small arguments in the table show the growth: ack(3, 3)
is 61 but already needs 2432 calls. The nested call in the last case is
evaluated first, and its result becomes the second argument of the outer call,
so the recursion depth is not the only cost. Values such as
ack(4, 1) are still within reach of a default integer but take
millions of calls, and larger ones exhaust both time and stack.
$ gfortran r4.f90 -o r4 $ ./r4 ack(0, 0) = 1, calls 1 ack(1, 2) = 4, calls 6 ack(2, 3) = 9, calls 44 ack(3, 3) = 61, calls 2432
Recursion over an array
A recursive procedure does not need to divide its input in half; it can also peel off one element at a time. The three functions below take an array and a count of the elements still to process, handle the last element, and call themselves with one element fewer. The count is the recursion control, and the base case is a count of zero or one. The same program shows a recursive greatest common divisor, whose arguments shrink by the remainder at every step.
module array_rec
implicit none
private
public :: total, largest, count_even, gcd
contains
recursive integer function total(a, n) result(s)
integer, intent(in) :: a(:)
integer, intent(in) :: n
if (n == 0) then
s = 0
else
s = a(n) + total(a, n - 1)
end if
end function total
recursive integer function largest(a, n) result(m)
integer, intent(in) :: a(:)
integer, intent(in) :: n
if (n == 1) then
m = a(1)
else
m = max(a(n), largest(a, n - 1))
end if
end function largest
recursive integer function count_even(a, n) result(c)
integer, intent(in) :: a(:)
integer, intent(in) :: n
if (n == 0) then
c = 0
else if (mod(a(n), 2) == 0) then
c = 1 + count_even(a, n - 1)
else
c = count_even(a, n - 1)
end if
end function count_even
recursive integer function gcd(a, b) result(g)
integer, intent(in) :: a, b
if (b == 0) then
g = a
else
g = gcd(b, mod(a, b))
end if
end function gcd
end module array_rec
program r5
use array_rec
implicit none
integer :: data(8)
data = [17, 4, 9, 22, 6, 15, 8, 3]
print '(a, i0)', 'total: ', total(data, size(data))
print '(a, i0)', 'largest: ', largest(data, size(data))
print '(a, i0)', 'even count: ', count_even(data, size(data))
print '(a, i0)', 'gcd(84, 36): ', gcd(84, 36)
print '(a, i0)', 'gcd(1071, 462): ', gcd(1071, 462)
end program r5
The total is 84, the largest value 22, and four of the eight numbers are even.
Euclid's algorithm returns 12 for 84 and 36 and 21 for 1071 and 462, and it
needs only a handful of steps because the remainder shrinks quickly. The array
version is easy to read but it is not the fastest way to sum an array: the
intrinsic sum, maxval and count do the
same work without a call per element, and a compiler can vectorise them. The
recursive form is shown here because the shape recurs in tree algorithms, where
no intrinsic exists.
$ gfortran r5.f90 -o r5 $ ./r5 total: 84 largest: 22 even count: 4 gcd(84, 36): 12 gcd(1071, 462): 21
Recursion over a string
A character string can be reduced in the same way. Reversing a string means
reversing everything after the first character and then appending that
character, and a string of length one or zero is its own reverse. A palindrome
check compares the first and last characters and recurses on the string without
them. Both functions take character(len=*), so the length is
carried with the argument and len(s) shrinks at every call.
module text_rec
implicit none
private
public :: reverse, is_palindrome
contains
recursive function reverse(s) result(r)
character(len=*), intent(in) :: s
character(len=len(s)) :: r
if (len(s) <= 1) then
r = s
else
r = reverse(s(2:)) // s(1:1)
end if
end function reverse
recursive logical function is_palindrome(s) result(flag)
character(len=*), intent(in) :: s
if (len(s) <= 1) then
flag = .true.
else if (s(1:1) /= s(len(s):)) then
flag = .false.
else
flag = is_palindrome(s(2:len(s) - 1))
end if
end function is_palindrome
end module text_rec
program r6
use text_rec
implicit none
character(len=*), parameter :: words(4) = [character(len=9) :: &
'level', 'fortran', 'racecar', 'abcdefgh']
print '(a, a, a, a)', 'reverse(fortran) = ', reverse('fortran')
print '(a, a, a, l1)', 'reverse(level) = ', reverse('level')
print '(a, a, a, l1)', 'palindrome? ', trim(words(1)), ': ', is_palindrome(trim(words(1)))
print '(a, a, a, l1)', 'palindrome? ', trim(words(2)), ': ', is_palindrome(trim(words(2)))
print '(a, a, a, l1)', 'palindrome? ', trim(words(3)), ': ', is_palindrome(trim(words(3)))
print '(a, a, a, l1)', 'palindrome? ', trim(words(4)), ': ', is_palindrome(trim(words(4)))
end program r6
fortran becomes nartrof, while level
reads the same in both directions. The palindrome test accepts
level and racecar and rejects fortran
and abcdefgh. The array of words is declared with a fixed length
of nine, so the program passes trim(words(i)); without the
trim the padding blanks would be compared with the letters and
every word would fail. The reversal creates a new string at every call, which
is fine for short words and wasteful for long text.
$ gfortran r6.f90 -o r6 $ ./r6 reverse(fortran) = nartrof reverse(level) = level palindrome? level: T palindrome? fortran: F palindrome? racecar: T palindrome? abcdefgh: F
Caching the answers
The exponential Fibonacci function repeats work because it has no memory. A memo is an array that stores each answer the first time it is computed, and the function checks the array before recursing. The table is allocated by the program, filled with a value that cannot be a real answer, and the function uses the argument itself as the index. The recursion is still written the same way; only the repeated branches disappear.
module memo
implicit none
private
public :: fib, calls, table
integer, allocatable :: table(:)
integer :: calls = 0
contains
recursive integer function fib(n) result(r)
integer, intent(in) :: n
calls = calls + 1
if (n < 2) then
r = n
else if (table(n) >= 0) then
r = table(n)
else
r = fib(n - 1) + fib(n - 2)
table(n) = r
end if
end function fib
end module memo
program r7
use memo
implicit none
allocate (table(0:45))
table = -1
print '(a, i0, a, i0)', 'fib(40) = ', fib(40), ', calls ', calls
calls = 0
print '(a, i0, a, i0)', 'fib(45) = ', fib(45), ', calls ', calls
print '(a, i0)', 'table(30) is now ', table(30)
end program r7
fib(40) needs 79 calls instead of more than three hundred million,
and fib(45) needs only eleven because the table from the first
call is still valid for the smaller arguments. The table entry for 30 reads
832040, which is the correct value. The cost of the memo is one array of
n + 1 integers, and the price is that the function can no longer
be pure, since it modifies module state.
$ gfortran r7.f90 -o r7 $ ./r7 fib(40) = 102334155, calls 79 fib(45) = 1134903170, calls 11 table(30) is now 832040
Next steps
Recursion is the natural language of the binary trees article, where insertion, traversal and deletion all descend into subtrees, and of the sorting article, where merge sort and quick sort split an array and sort the halves. The procedure arguments and callbacks article shows how a recursive routine can take another procedure as an argument, and the procedures article covers the interface rules that every recursive call follows.
Source
Fortran 2018 standard (J3/18-007r1)
Fortran-lang: learning resources
In this article we have written recursive functions with a base case and a recursive case, counted the calls of a factorial and of a naive Fibonacci function, solved the Towers of Hanoi in two recursive calls, evaluated the Ackermann function, summed and searched an array one element at a time, reversed and tested strings, and replaced repeated work with a memo table. The previous article, Fortran binary trees, uses the same technique on a structure of pointers.
Author
List all Fortran tutorials.