All code is in Python.
So, the basic problem is how to implement a recursive algorithm with a non-recursive function. The fibonacci sequence is a good example of this:
def fib(n):
return n if n < 2 else fib(n - 2) + fib(n - 1)
print fib(10)
So, how do we turn this function into a non-recursive one? A first attempt might look like this:
def fib(f, n):
return n if n < 2 else f(f, n - 2) + f(f, n - 1)
print fib(fib, 10)
So the basic idea is to pass fib itself so that it doesn't have to know its own name in order to call itself. Note, however, that we have to pass f to itself every time, even in the kernel of the fibonacci algorithm. Ignoring this for now, the proof that we have eliminated direct recursion is in the fact that we can now define fib using a lambda:
fib = lambda f, n: n if n < 2 else f(f, n - 2) + f(f, n - 1)
print fib(fib, 10)
There is an obvious problem here: it's rather annoying to have to pass fib to itself in order to recurse. A wrapper function fixes this:
def fib(n):
f = lambda f, n: n if n < 2 else f(f, n - 2) + f(f, n - 1)
return f(f, n)
print fib(10)
We don't want to have to write a wrapper function for each recursive function we want to write. Can we write a generalised function that will take our fibonacci and any other recursive algorithm kernel and convert it into a recursive function? As a stepping stone, let's change our latest fib to a function creator, rather than a simple wrapper:
def fib_maker():
f = lambda f, n: n if n < 2 else f(f, n - 2) + f(f, n - 1)
return lambda n: f(f, n)
fib = fib_maker()
We can see that the fibonacci kernel is just a function inside the fib_maker function. So let's replace fib_maker with a general-purpose recursive function generator:
def recursive(f):
return lambda n: f(f, n)
fib = recursive(lambda f, n: n if n < 2 else f(f, n - 2) + f(f, n - 1))
It seems that we are almost there. We must now tackle the hard part, that we've been putting since near the beginning. The lambda should not have to forward the recursive function to itself. We want to be able to write this:
fib = recursive(lambda f, n: n if n < 2 else f(n - 2) + f(n - 1))
Clearly, the function being passed in has to be a full copy of the created recursive function. Allowing, 'recursive' to use recursion itself makes this quite simple:
def recursive(f):
return lambda n: f(recursive(f), n)
fib = recursive(lambda f, n: n if n < 2 else f(n - 2) + f(n - 1))
print fib(10)
(Note carefully that the nested call to recursive(f) occurs inside the lambda n. If you try to compute it in advance, you'll trigger an immediate infinite recursion and blow the stack.)
But can we go one step further, and define 'recursive' without directly using recursion? Loaded question. It turns out that our original trick of passing a function to itself to help it recurse is just the ticket.
def recursive(f):
def recurse(r):
return lambda n: f(r(r), n)
return recurse(recurse)
Further reductions are possible:
def recursive(f):
recurse = lambda r: lambda n: f(r(r), n)
return recurse(recurse)
def recursive(f):
recurse = lambda r: lambda n: f(r(r), n)
return (lambda R: R(R))(recurse)
recursive = lambda f: (lambda R: R(R))(lambda r: lambda n: f(r(r), n))
Finally, we have arrived at a non-recursive function that converts other non-recursive functions into recursive algorithms! This is what's commonly known as a fixed-point combinator, renamed here and Pythonified:
fix = lambda f: (lambda R: R(R))(lambda r: lambda *args, **kwargs: f(r(r), *args, **kwargs))
fib = fix(lambda f, n: n if n < 2 else f(n - 2) + f(n - 1))
Footnote: This is not quite the fixed-point combinator you'll see written up elsewhere. Usually, the kernel is written as a nested lambda and passed to a Z-combinator, thus:
fib = Z(lambda f: lambda n: n if n < 2 else f(n - 2) + f(n - 1))
This is a minor detail, however. The principles are the same. Also, the (lambda R: R(R))(lambda r:...) is my special touch. Z-combinators usually pass the lambda r:... to a full copy of itself.
Correction: The Z-combinator is not quite the same thing. This warrants further investigation.
