Algol 68 recursion
last modified November 13, 2026
A recursive procedure calls itself with a smaller problem, and a base case stops the descent. Recursion is the natural way to describe a computation whose shape repeats: a factorial, a tree walk, a search that halves its range with every step.
This article shows the pattern on factorials, Fibonacci numbers, the towers of Hanoi, Euclid's algorithm, fast exponentiation, and rows and strings. It also shows what recursion costs and where it ends.
A procedure that calls itself
The declaration of factorial mentions factorial in
its own body. The base case, n <= 1, returns 1 without another
call, and every other value multiplies n by the result of the
call with n - 1.
PROC factorial = (INT n) INT:
IF n <= 1 THEN 1 ELSE n * factorial(n - 1) FI;
BEGIN
FOR i TO 10 DO
print((whole(i, 0), "! = ", whole(factorial(i), 0), newline))
OD
END
Each call waits for the one it made, and the multiplications happen on the way back out of the recursion. Ten calls produce the ten factorials, and the values grow quickly: 10! is 3628800.
$ a68g fact.a68 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 362880 10! = 3628800
The cost of naive recursion
The Fibonacci procedure is the textbook example of a recursion that repeats
work. fib(n) calls fib(n - 1) and
fib(n - 2), and the two branches compute the same smaller values
again and again. A counter incremented at the start of every call measures the
damage.
INT calls := 0;
PROC fib = (INT n) INT:
(
calls +:= 1;
IF n < 2 THEN n ELSE fib(n - 1) + fib(n - 2) FI
);
BEGIN
print(("fib(15) = ", whole(fib(15), 0), newline));
print(("calls = ", whole(calls, 0), newline))
END
For fib(15) the procedure is called 1973 times, although only
sixteen different values are needed. The number of calls grows exponentially,
so fib(30) already needs more than a million calls, and the
program spends its time repeating work it has done before.
$ a68g fib.a68 fib(15) = 610 calls = 1973
Memoisation
The cure for repeated work is to remember the answers. A row of integers is filled with -1, which marks a value that has not been computed, and the procedure stores each result before it returns it. A call that finds a stored value returns it at once instead of recursing.
[0:90] INT memo;
FOR i FROM LWB memo TO UPB memo DO memo[i] := -1 OD;
PROC fib = (INT n) INT:
IF n < 2 THEN n
ELIF memo[n] >= 0 THEN memo[n]
ELSE memo[n] := fib(n - 1) + fib(n - 2);
memo[n]
FI;
BEGIN
print(("fib(40) = ", whole(fib(40), 0), newline));
print(("fib(46) = ", whole(fib(46), 0), newline))
END
The first call computes the chain of values once, and every later call finds
its answer in the row. fib(40) and fib(46) are
instant, while the naive procedure would need billions of calls for the first
of them. fib(46) is the largest Fibonacci number that fits in an
INT of this build, whose maximum is 2147483647.
$ a68g memo.a68 fib(40) = 102334155 fib(46) = 1836311903
Towers of Hanoi
The towers of Hanoi has a recursive solution of three steps: move the upper
n - 1 disks to the spare peg, move the largest disk to the target,
and move the n - 1 disks onto it. The procedure prints every move
and counts them.
INT moves := 0;
PROC hanoi = (INT n, CHAR from, CHAR to, CHAR via) VOID:
IF n > 0 THEN
hanoi(n - 1, from, via, to);
moves +:= 1;
print(("move disk ", whole(n, 0), " from ", from, " to ", to, newline));
hanoi(n - 1, via, to, from)
FI;
BEGIN
hanoi(3, "A", "C", "B");
print(("total moves ", whole(moves, 0), newline))
END
Three disks need seven moves, which is 2 ** 3 - 1. The pattern of
the moves repeats at every level, and the recursion is what makes the
repetition visible: the first three moves clear the small disks out of the way,
the fourth moves the largest one, and the last three rebuild the tower on top
of it.
$ a68g hanoi.a68 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 total moves 7
Euclid's algorithm
The greatest common divisor of two numbers is the divisor of the second number
and the remainder of the first divided by it. The recursion is short because
the remainder is smaller than the divisor, so the pair shrinks at every step
and the base case b = 0 is reached quickly.
PROC gcd = (INT a, b) INT:
IF b = 0 THEN a ELSE gcd(b, a MOD b) FI;
PROC lcm = (INT a, b) INT:
a OVER gcd(a, b) * b;
BEGIN
print(("gcd(84, 36) = ", whole(gcd(84, 36), 0), newline));
print(("lcm(84, 36) = ", whole(lcm(84, 36), 0), newline))
END
Twelve divides both 84 and 36, and the least common multiple is built from the
same value: the product divided by the gcd, written as
a OVER gcd(a, b) * b so that the intermediate result stays small.
$ a68g gcd.a68 gcd(84, 36) = 12 lcm(84, 36) = 252
Fast exponentiation
Raising a number to a power by repeated multiplication needs as many multiplications as the exponent. Halving the exponent instead needs only as many as there are bits in it: an even exponent squares the result of half the exponent, and an odd one multiplies once and then continues with the even number.
PROC power = (INT base, n) INT:
IF n = 0 THEN 1
ELIF ODD n THEN base * power(base, n - 1)
ELSE (INT half = power(base, n OVER 2); half * half)
FI;
BEGIN
print(("2 ** 10 = ", whole(power(2, 10), 0), newline));
print(("3 ** 5 = ", whole(power(3, 5), 0), newline));
print(("7 ** 0 = ", whole(power(7, 0), 0), newline))
END
2 ** 10 is computed with five multiplications instead of the ten that
the naive loop would need, and the result is the same. The count grows with
the number of bits of the exponent rather than with its size. The declaration
inside the ELSE branch is a serial clause in parentheses, whose
value is the last expression.
$ a68g power.a68 2 ** 10 = 1024 3 ** 5 = 243 7 ** 0 = 1
Working on a row
Recursion over a row is a recursion over subscripts. The procedure takes the row and the range it still has to visit, adds the first element to the result for the rest of the range, and stops when the range is empty.
PROC total = ([]INT r, INT from, INT to) INT:
IF from > to THEN 0
ELSE r[from] + total(r, from + 1, to)
FI;
PROC largest = ([]INT r, INT from, INT to) INT:
IF from = to THEN r[from]
ELSE
(INT rest = largest(r, from + 1, to);
(r[from] > rest | r[from] | rest))
FI;
BEGIN
[]INT values = (3, 9, 2, 7, 5);
print(("total ", whole(total(values, 1, UPB values), 0), newline));
print(("largest ", whole(largest(values, 1, UPB values), 0), newline))
END
total adds the five values and largest compares the
first value with the largest of the rest. The base case of largest
is a single element, which is its own maximum, and the conditional clause picks
the larger of the two.
$ a68g sumrow.a68 total 26 largest 9
Reversing a string
A string reverses by taking its last character and putting it in front of the reversal of the others, or by taking the first character and appending it to the reversal of the rest. The base case is a string of one character or none, which is already reversed.
PROC reverse = (STRING s) STRING:
IF UPB s <= 1 THEN s ELSE reverse(s[2:]) + s[1] FI;
BEGIN
print((reverse("Algol 68"), newline));
print((reverse("a"), newline));
print(("[" + reverse("") + "]", newline))
END
The first character is appended after the recursive call, so the characters
come back in the opposite order. The empty string is handled by the same base
case, because its upper bound is 0 and 0 <= 1, so the call
returns the string unchanged.
$ a68g reverse.a68 86 loglA a []
The limits
Every active call keeps a frame with its parameters and local variables, so a
recursion that never meets its base case runs out of stack. This build stops
with stack overflow when a procedure calls itself a hundred
thousand times, which is far beyond the depth of the examples above but well
within reach of a loop that was meant to be a recursion.
Two procedures may call each other, as the even and odd tests of a number do, because each body names the other. The pair is declared before the block that uses it, and the calls alternate until one of the base cases is reached. The same care is needed as with a single procedure: a cycle without a base case is an endless descent.
The size of the values is a second limit. An INT in this build
holds values up to 2147483647, so a factorial stops at 12! and a Fibonacci
number at fib(46). The
procedures article describes the
PROC declarations that the examples use, and the
rows article explains the row parameters of
total and largest.
Next steps
The procedures article covers parameter
modes, procedure values, and partial parametrisation, and
rows explains the subscripts that the recursive
row procedures use. The strings article
describes the slicing behind reverse, and
loops shows the iterative form of the same
computations.
Source
Revised Report on the Algorithmic Language Algol 68
In this article we have written recursive procedures for factorials, Fibonacci numbers, the towers of Hanoi, Euclid's algorithm, fast exponentiation, row totals, and string reversal, measured the cost of naive recursion, removed it with memoisation, and seen the depth and value limits of the implementation.
Author
List all Algol 68 tutorials.