Recursion

A recursive procedure calls itself. Fortran requires the word recursive on the declaration, which is the only ceremony the language adds: everything else is the two parts every recursion has, a case that calls and a case that stops. This lesson writes three recursions, counts the work one of them does, and looks at the depth a stack allows.

RECURSIVE

recursive function factorial(n) result(f) is a function with the prefix and a result variable. Inside the body the name factorial is the procedure and f is its result, so the call factorial(n - 1) is an expression and not an assignment to the result. The result clause is what keeps the two apart, and it is why almost every recursive function in modern Fortran has one.

The file fact.f90:

program fact_demo implicit none integer :: i do i = 0, 6 print '(i2,a,i8)', i, "! =", factorial(i) end do contains recursive function factorial(n) result(f) integer, intent(in) :: n integer :: f if (n <= 1) then f = 1 else f = n * factorial(n - 1) end if end function factorial end program fact_demo

gfortran -Wall -Wextra -std=f2018 fact.f90 -o fact
./fact

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720

A integer of 32 bits holds factorials up to twelve, and the function would overflow silently above that, which is the first thing a recursive factorial teaches: the recursion is correct, the type is the limit.

The base case

n <= 1 is the base case, and it is not decoration: without it the function calls itself until the stack ends and the program dies with a signal. Every recursion has one, it is tested first, and it is the line to read when a recursive procedure misbehaves.

A second rule follows from the first: every call must move towards the base case. n - 1 does; n + 1 or a mistake in the sign does not, and the compiler cannot see the difference. A recursion whose argument does not approach the base case compiles and loops.

What a recursion costs

A naive Fibonacci is the classic example of a recursion that is correct and slow: every call asks for two more, and the same values are computed again and again. The program counts the calls so the cost is visible.

program fib_demo implicit none integer :: calls calls = 0 print *, "fib(10) =", fib(10, calls) print *, "calls :", calls contains recursive function fib(n, calls) result(f) integer, intent(in) :: n integer, intent(inout) :: calls integer :: f calls = calls + 1 if (n < 2) then f = n else f = fib(n - 1, calls) + fib(n - 2, calls) end if end function fib end program fib_demo

gfortran -Wall -Wextra -std=f2018 fib.f90 -o fib
./fib

fib(10) = 55
calls : 177

Fifty-five needs a hundred and seventy-seven calls. The count grows like the golden ratio to the power n, so fib(30) needs about two and a half million calls for a value of 832040. A loop that keeps the last two values does the same work in thirty steps, and that is the comparison to remember: recursion expresses a definition well and evaluates it badly unless the results are reused.

Mutual recursion

Two procedures may call each other, which is the same idea with a cycle. Inside one program both are contained procedures and see each other without an interface; the program below asks whether a number is even by subtracting one and asking whether the result is odd.

program mutual_demo implicit none print *, "even(10) :", is_even(10) print *, "even(7) :", is_even(7) contains recursive function is_even(n) result(r) integer, intent(in) :: n logical :: r if (n == 0) then r = .true. else r = is_odd(n - 1) end if end function is_even recursive function is_odd(n) result(r) integer, intent(in) :: n logical :: r if (n == 0) then r = .false. else r = is_even(n - 1) end if end function is_odd end program mutual_demo

gfortran -Wall -Wextra -std=f2018 mutual.f90 -o mutual
./mutual

even(10) : T
even(7) : F

The two functions are correct and the recursion is the slowest possible way to test a parity: ten calls for ten, where mod(n, 2) == 0 is one operation. Mutual recursion earns its place in a parser, where one rule of the grammar calls another, and not in arithmetic.

How deep a recursion may go

Every call uses a stack frame, and the stack of a process is a fixed size, so a recursion has a depth it cannot pass. On a default Linux stack of eight megabytes a frame of a few dozen bytes allows tens of thousands of calls, and a frame with a large local array allows far fewer. The exact number depends on the compiler, the flags and the frame, which is why a program that must recurse deeply is written with an explicit stack instead.

A recursion that passes the limit does not return an error: the process dies with a segmentation fault, and the debugging lessons are where that is read. The practical rule is the one this lesson opened with: a recursion needs a base case, and a recursion over data of unknown size needs a bound the program controls.

Exercises

  1. Print factorial(13) and compare it with 13!. Which value is wrong, and why?
  2. Rewrite factorial as a loop and print the same seven values. Which version is easier to read?
  3. Count the calls for fib(15) and for fib(20). How does the count grow?
  4. Add an is_divisible(a, b) that uses the mutual pair and test 10 and 7 against 2. What does each answer say?

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does the RECURSIVE prefix on a procedure declare?

    Answer

    That the procedure may call itself

    Fortran requires the word on a self-calling procedure.

  2. What is the base case of a recursion?

    Answer

    The case that returns without calling itself, which stops the recursion

    Without it the calls never end.

  3. What does this program print? program p implicit none print *, gcd(12, 8) contains recursive function gcd(a, b) result(g) integer, intent(in) :: a, b integer :: g if (b == 0) then g = a else g = gcd(b, mod(a, b)) end if end function gcd end program p

    Answer

    4

    Four is the greatest common divisor of 12 and 8.

  4. Why does the naive Fibonacci make so many calls?

    Answer

    Each call asks for two more and recomputes values it has already computed

    The recursion tree repeats its subtrees.

  5. How many calls does the naive fib(10) make on this page?

    Answer

    177

    The program counts the calls and prints 177.

  6. What must every recursive call do?

    Answer

    Move towards the base case

    A call that does not approach the base case never stops.

  7. Why does a recursive function need a RESULT clause?

    Answer

    So that the procedure name in the body is the call, not the result variable

    The clause separates the name of the call from the value.

  8. What happens when a recursion passes the stack limit?

    Answer

    The process dies with a segmentation fault

    The stack is a fixed region and running past it is fatal.

  9. What is mutual recursion?

    Answer

    Two procedures that call each other

    The cycle is between two procedures rather than within one.

  10. Which loop replaces the naive Fibonacci recursion?

    Answer

    A loop that keeps the last two values and adds them

    The two previous values are all the next one needs.

The programs on this page were built with GNU Fortran (Alpine 15.2.0) 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev