Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 39 ยท Procedures and Modules

Recursion, Pure and Elemental Procedures

Write recursive Fortran procedures with the recursive keyword and result clause, and use pure and elemental to make side-effect-free, array-friendly functions.

Three prefixes change how a Fortran procedure behaves. recursive allows it to call itself. pure promises that it has no side effects. elemental writes a scalar procedure once and lets it work on whole arrays. They are small keywords with large consequences for correctness and speed.

Recursion

A procedure that calls itself must carry the recursive prefix in portable code, and a recursive function needs a result clause. Always write both:

FORTRAN
recursive function factorial(n) result(f)
  integer, intent(in) :: n
  integer(kind=8) :: f
  if (n <= 1) then
    f = 1
  else
    f = n * factorial(n - 1)
  end if
end function factorial

Why result? Inside a function the bare function name means "the function being called". With result(f) the name f is the variable you assign and factorial(n - 1) is clearly a call. Each active call gets its own copy of the local variables, held on the stack.

Depth and the stack

Every pending call uses stack memory, so a recursion ten million levels deep will crash with a stack overflow, while a loop would not. Use recursion when the problem is naturally recursive (trees, divide and conquer, grammars) and loops when it is a simple count or accumulation.

Python Stand-in: factorial and Fibonacci recursion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A classic example is Euclid's greatest common divisor:

FORTRAN
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

gcd(48, 18) calls gcd(18, 12), then gcd(12, 6), then gcd(6, 0) and returns 6.

Pure procedures

A pure procedure has no side effects: it does not change anything except its own result (or its intent(out/inout) arguments, for a pure subroutine). The compiler checks the rules:

  • Function dummy arguments must be intent(in) (or value).
  • No I/O to external files and no stop.
  • No changes to module variables or other global state.
  • It may only call other pure procedures.
FORTRAN
pure function clamp(x, lo, hi) result(y)
  real, intent(in) :: x, lo, hi
  real :: y
  y = max(lo, min(x, hi))
end function clamp

Why bother? Purity is a guarantee the compiler can exploit: calls may be reordered, run in parallel inside do concurrent (see do concurrent and elemental), or removed if unused. It also makes the function easy to test and reason about. Only pure procedures may be called from do concurrent or from other pure procedures.

Elemental procedures

Write a pure scalar procedure and mark it elemental, and it accepts arrays of any rank:

FORTRAN
elemental function celsius(f) result(c)
  real, intent(in) :: f
  real :: c
  c = (f - 32.0) * 5.0 / 9.0
end function celsius

Now all of these are legal:

FORTRAN
real :: t(4) = [32.0, 50.0, 68.0, 212.0]
print *, celsius(98.6)     ! scalar
print *, celsius(t)        ! array, applied element by element

Rules: an elemental procedure is pure, its arguments are scalars, and its result is a scalar. With several array arguments they must have the same shape (a scalar argument is broadcast). Elemental subroutines work the same way. This is how the intrinsics sin, exp and abs behave on whole arrays.

Python Stand-in: applying a scalar function to a whole array

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

flowchart TD
    A["procedure"] --> B["recursive<br/>may call itself"]
    A --> C["pure<br/>no side effects"]
    C --> D["elemental<br/>scalar code, array use"]

Elemental implies pure; pure and recursive can combine (recursive pure function).

Choosing between them

Need Use
A function that calls itself recursive ... result(r)
No hidden state, safe to run in parallel pure
Same formula for scalar and arrays elemental
A compiler-verified guarantee in do concurrent pure or elemental

You can combine prefixes in any order: pure elemental function f(x), or elemental alone (which already implies pure). Since Fortran 2018 elemental procedures are pure unless you write impure elemental, handy for a procedure that prints or counts.

Performance note

Elemental functions are not magic loops hidden in the language: they are still loops, but the compiler knows there are no dependencies between iterations, so it can vectorize them. Always compile with optimization on (-O2) to see the benefit.

Common mistakes

  • Omitting recursive and relying on a compiler flag or default; the code may break on another compiler.
  • Recursing without a base case, or one that is never reached (negative n in factorial; the code above stops at n <= 1 for that reason).
  • Putting a print in a pure function. The compiler rejects it.
  • Overflowing an integer: factorial with default 4-byte integers fails at 13. Use integer(kind=8) as above, which handles up to 20.
  • Giving elemental a non-scalar argument.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does a recursive function normally use a result clause?

    Inside a function the plain name refers to the call, so a separate result variable avoids confusion.
  2. 2. Which is forbidden inside a pure function?

    External I/O is a side effect, so a pure procedure cannot do it.
  3. 3. What does elemental let you do?

    An elemental procedure is written for scalars and applied element by element when given arrays.
  4. 4. gcd(48, 18) with the recursive Euclid function returns what?

    48,18 -> 18,12 -> 12,6 -> 6,0, which returns 6.

Summary

  • recursive plus result(r) lets a procedure call itself; watch stack depth.
  • pure forbids side effects and enables safe parallel use.
  • elemental writes scalar code that works on arrays of any rank and implies pure.
  • impure elemental allows I/O when you need it.

Next: Derived types