Recursion & the Man or Boy Test

ALGOL 60 procedures may call themselves directly or indirectly:

17.1 Recursive procedures

ALGOL 60 procedures may call themselves directly or indirectly:

'begin'
    'integer' 'procedure' factorial(n); 'value' n; 'integer' n;
        factorial := 'if' n = 0 'then' 1 'else' n * factorial(n - 1);

    'integer' 'procedure' fib(n); 'value' n; 'integer' n;
        fib := 'if' n < 2 'then' n 'else' fib(n - 1) + fib(n - 2);

    'integer' i;
    'for' i := 0 'step' 1 'until' 10 'do'
    'begin'
        outinteger(1, factorial(i));
        outinteger(1, fib(i));
        outstring(1, "\n")
    'end'
'end'

17.2 Towers of Hanoi

'begin'
    'procedure' hanoi(n, from, to, via);
        'value' n, from, to, via; 'integer' n, from, to, via;
    'begin'
        'if' n > 0 'then'
        'begin'
            hanoi(n - 1, from, via, to);
            outstring(1, "move disk "); outinteger(1, n);
            outstring(1, "from "); outinteger(1, from);
            outstring(1, "to "); outinteger(1, to);
            outstring(1, "\n");
            hanoi(n - 1, via, to, from)
        'end'
    'end';
    hanoi(3, 1, 3, 2)
'end'

17.3 Ackermann's function

'integer' 'procedure' ackermann(m, n); 'value' m, n; 'integer' m, n;
    ackermann := 'if' m = 0 'then' n + 1
                 'else' 'if' n = 0 'then' ackermann(m - 1, 1)
                 'else' ackermann(m - 1, ackermann(m, n - 1));
'comment' ackermann(2, 3) = 9, ackermann(3, 3) = 61;

17.4 Mutual recursion

ALGOL 60 needs no forward declarations: all declarations in a block head are visible throughout the block, so two procedures declared in the same block can call each other.

'boolean' 'procedure' even(n); 'value' n; 'integer' n;
    even := 'if' n = 0 'then' 'true' 'else' odd(n - 1);
'boolean' 'procedure' odd(n); 'value' n; 'integer' n;
    odd := 'if' n = 0 'then' 'false' 'else' even(n - 1);

17.5 Knuth's "Man or Boy" test

In 1964 Donald Knuth published (ALGOL Bulletin 17) a program "to separate the man-compilers from the boy-compilers". It exercises recursion, call by name, nested procedures referring to non-local variables, and procedures passed as parameters — all at once:

(Knuth's original omits the specification of x1 ... x5; MARST requires it, so 'real' x1, x2, x3, x4, x5; is added.)

The correct answer for k = 10 is -67. Values for other starting k:

Why it is hard:

Each activation of a creates a new b that refers to that activation's k, x1 ... x4 — the compiler must maintain correct static links through deep recursion.

b is passed as a by-name actual parameter (x1 of the next activation), and later invoked from within other activations.

Recursion depth and the number of live activations grow exponentially with k — large k exhausts the stack.

Knuth himself did not know the right answer when he published it; most compilers of the time got it wrong or crashed. Today it is a standard test of closure implementation in many languages (see Rosetta Code).

'begin'
    'real' 'procedure' a(k, x1, x2, x3, x4, x5);
        'value' k; 'integer' k;
        'real' x1, x2, x3, x4, x5;
    'begin'
        'real' 'procedure' b;
        'begin'
            k := k - 1;
            b := a := a(k, b, x1, x2, x3, x4)
        'end';
        'if' k <= 0 'then' a := x4 + x5 'else' b
    'end';
    outreal(1, a(10, 1, -1, -1, 1, 0));
    outstring(1, "\n")
'end'