Deriving Recursion

The definitions provided here are intended to work with OCaml; some require the -rectypes option (or #rectypes directive in the interpreter)

Imagine that we're trying to implement the factorial function in a programing language without recursion. We might start with what we know; that the factorial of zero is one. A first attempt might be:

let fact0 x = if x = 0 then 1 else 0

Well, this function works when x is zero. But it's wrong for every other argument. However, since we now have a factorial function that works for zero, we could try to use it to create one that works up to one:

let fact1 x = if x = 0 then 1 else x * fact0 (x-1)

And now that we have a factorial function that works up to one, we can make one that works up to two:

let fact2 x = if x = 0 then 1 else x * fact1 (x-1)

A pattern is emerging where the only varying part of the previous definitions is which factorial function to delegate the rest of the work to, so we can abstract this:

let generate_next_fact fact_rest x = if x = 0 then 1 else x * fact_rest (x-1)

So now fact0, fact1, and fact2 can be rewritten as:

let fact0 = generate_next_fact z
let fact1 = generate_next_fact fact0
let fact2 = generate_next_fact fact1

Or, in expanded form:

let fact0 = generate_next_fact z
let fact1 = generate_next_fact (generate_next_fact z)
let fact2 = generate_next_fact (generate_next_fact (generate_next_fact z))

Where z can be any function with the right type because it's only used when trying to compute the factorial of a number greater than the function can handle. This exposes the limitation of our factorial functions - the maximum value that we can compute the factorial of is hardcoded into the program. What we need is a way to dynamically generate factn for any n, the expansion of which looks like this:

generate_next_fact (generate_next_fact (generate_next_fact ...))

with at least n+1 total repetitions of generate_next_fact. This means that the z we choose now matters - we want it to be able to expand into generate_next_fact z, so that as many repetitions of generate_next_fact as we need can be created. If the value of n at runtime is three, then we could have z 3 expand to:

generate_next_fact (generate_next_fact (generate_next_fact (generate_next_fact z))) 3

Which will evaluate to 6:

generate_next_fact (generate_next_fact (generate_next_fact (generate_next_fact z))) 3
=>
if 3 = 0 then 1 else 3 * (generate_next_fact (generate_next_fact (generate_next_fact z)) 2)
=>
3 * (if 2 = 0 then 1 else 2 * (generate_next_fact (generate_next_fact z) 1))
=>
3 * (2 * (if 1 = 0 then 1 else 1 * (generate_next_fact z 0)))
=>
3 * (2 * (1 * (if 0 = 0 then 1 else 0 * (z (-1)))))
=>
3 * (2 * (1 * 1))
=>
6

There may be many ways to define z, but it would be nice if we could create it from generate_next_fact. So we're looking for a function, call it fix, such that fix generate_next_fact can be expanded to generate_next_fact (fix generate_next_fact). To find such a function, called a fixpoint combinator, we can either think really hard about it or use a search engine; either way might result in the discovery of the y combinator:

let fix f = (fun x -> f (x x)) (fun x -> f (x x))

We can see that:

fix generate_next_fact
=
(fun x -> generate_next_fact (x x)) (fun x -> generate_next_fact (x x))
=
generate_next_fact ((fun x -> generate_next_fact (x x)) (fun x -> generate_next_fact (x x)))

So we get what we wanted. Except if we try running fix generate_next_fact in a language with eager evaluation we get an infinite loop, likely ending with a stack overflow. This is because the expansion from fix generate_next_fact to generate_next_fact (fix generate_next_fact) occurs immediately, then just keeps going. We can resolve this problem by modifying fix to delay the expansion until explicitly forced. Since most programming languages don't evaluate the body of a function until the function is applied to an argument, we can implement this delay by adding an extra parameter to a function in the definition of fix such that fix f = f (fun () -> fix f):

let fix f = (fun x -> f (x x)) (fun x () -> f (x x))

And we also have to modify generate_next_fact to perform the explicit expansion:

let generate_next_fact fact_rest x = if x = 0 then 1 else x * fact_rest () (x-1)

Finally we have what we set out for:

let fact = fix generate_next_fact

Mutual Recursion

What about mutually recursive functions? Although rare in practice, it would still be nice to figure out how to implement them without explicit recursion. Let's use the canonical even/odd. We know that zero is even and not odd:

let even0 x = if x = 0 then true else false
let odd0 x = if x = 0 then false else true

These are correct when x is zero. They are also correct about half the time otherwise, but this is coincidental. We can follow a similar sequence of steps that were taken for factorial to arrive at:

let generate_next_even odd_rest x = if x = 0 then true else odd_rest (x-1)
let generate_next_odd even_rest x = if x = 0 then false else even_rest (x-1)

And the functions that work up to three:

let even3 = generate_next_even (generate_next_odd (generate_next_even (generate_next_odd z)))
let odd3 = generate_next_odd (generate_next_even (generate_next_odd (generate_next_even z)))

The alternation of generate_next_even and generate_next_odd complicates the description of the fixpoint combinator we are looking for. Instead we can try generating the even and odd functions simultaneously as a pair:

let generate_next_even_odd even_odd_rest =
  ((fun x -> if x = 0 then true else snd even_odd_rest (x-1)),
   (fun x -> if x = 0 then false else fst even_odd_rest (x-1)))
let even3_odd3 = generate_next_even_odd (generate_next_even_odd (generate_next_even_odd (generate_next_even_odd z)))

Now what we are looking for is a more familiar fix generate_next_even_odd = generate_next_even_odd (fix generate_next_even_odd). We again have to make modifications so that we can use our definition of fix that prevents immediate expansion:

let generate_next_even_odd even_odd_rest =
  ((fun x -> if x = 0 then true else snd (even_odd_rest ()) (x-1)),
   (fun x -> if x = 0 then false else fst (even_odd_rest ()) (x-1)))

And now we can define the functions we set out for:

let even_odd = fix generate_next_even_odd
let even = fst even_odd
let odd = snd even_odd