It's time to take a break from practical applications of functional programming to something less practical, but very interesting to know 😎

You may have heard of Y Combinator, one of the first and most well known startup accelerator. Have you ever wondered what the name means?

Y Combinator comes from a branch of mathematics called combinatorial logic. As usual, we will skip the maths and jump to look at what the Y Combinator does.

## Recursive Functions

Recursive functions are functions that call themselves. The most common example given is a factorial function, so let us go with that.

``````def factorial(x):
if x == 0: return 1
return x * factorial(x - 1)``````

So if we were to calculate `factorial(3)` that would evaluate to `3*factorial(2)` which in turn would evaluate to `3*2*factorial(1)`, then `3*2*1*factorial(0)` and finally `3*2*1*1` which is `6`.

Imagine the ability for a function to call itself by its name did not exist in our language (Early versions of many languages did not support recursion for example).

It turns out that if the language supports higher order functions then you can use that property to create recursive functions – even without the ability for a function to call itself by name. Let us see how.

## Building a recursive factorial

We want to build a recursive factorial implementation where the factorial function doesn't call itself directly.

We start with this base implementation. We will call it `fact_nr` since it is not recursive

Take a look at the `inner` function first. It looks just like a factorial function, but in the recursion step, instead of calling itself like `n * inner(n - 1)` instead it calls `n * fn(n - 1)`. What is `fn`? That is the function that we pass in as a parameter to `fact_nr`.

So this implementation allows us to configure a function `fn` which will be used during the recursion step. Lets see how it works

``````def error(n):
raise Exception()

fact_1 = fact_nr(error)
print(fact_1(0)) # 1
print(fact_1(1)) # Exception``````

Here we pass in an `error` function to `fact_nr` to create `fact_1`. The `error` function will always just raise an exception when called. When we call `fact_1(0)` then it goes into the `if n == 0` line and returns `1`. When we call `fact_1(1)` then the execution goes into the recursion step where it executes `fn`. Since `fn` is configured to `error`, that will execute and raise the exception.

What we really want is that when going into the recursion step we want it to call itself again. Suppose we pass in `fact_nr` function as its own parameter, like this

``````fact_2 = fact_nr(fact_nr(error))
print(fact_2(0)) # 1
print(fact_2(1)) # 1
print(fact_2(2)) # Exception``````

This time when it needs to recurse once then it executes the second `fact_nr` that was passed in and we get the right output. But if we need to recurse a second time we end up executing the `error` function.

We can extend this however long we want by doing something like this

``````# this will recurse until depth 6
fact_6 = fact_nr(fact_nr(fact_nr(fact_nr(fact_nr(fact_nr(error))))))``````

But eventually we need to pass in some terminating function (`error` in this case). A true recursive function would be like

``factorial = fact_nr(fact_nr(fact_nr(fact_nr(fact_nr(fact_nr(..... # forever``

## Y Combinator

The Y Combinator can take a non-recursive function like `fact_nr` and convert it to a true recursive version.

Here is the Y Combinator definition in the form usually found in literature

``````def Y(fn_nr):
return (lambda x: fn_nr(lambda y: x(x)(y)))(lambda x: fn_nr(lambda y: x(x)(y)))``````

or in a simpler form

``````def Y(fn_nr):
def _inner(cc):
return fn_nr(lambda x: cc(cc)(x))
return _inner(_inner)``````

It is pretty daunting to look at. If you are interested in how it works in detail, check out the reference section below.

The main thing here is that `Y` takes the non-recursive function `fn_nr` as input and returns another function as output which is fully recursive. Here it is in action

``````factorial = Y2(fact_nr)

print(factorial(10)) # 3828800
``````

Isn't that magical?

You can use the same trick with other recursive functions. You just make the function take a `fn` parameter and in the recursion step you call that function instead of itself. Any function of that form can be passed into `Y` to get a true recursive version.

For instance here is a non-recursive version to calculate the length of a list

``````def len_nr(fn):
def inner(lst):
if lst == []:
return 0
return 1 + fn(lst[1:])
return inner``````

Pass it to `Y` and we now have a recursive implementation of length of a list

``````len_lst = Y(len_nr)

print(len_lst([1, 2, 3])) # 3``````

## But Is It Useful?

Well thats great and all but as python natively supports recursion, is there any point to all of this. Well, short answer is no 😆

Well there is one practical application. When you need to modify the recursive function at runtime then you might want to implement the code in the non-recursive form shown here. Then you can pass it in to higher order functions to do runtime transformations before finally sending it along to `Y` to get a recursive version.

This technique is described in more detail by Bruce McAdam in his paper "That About Wraps It Up" which you can read here.

Apart from that, there isn't a place that I'd use the Y Combinator in practical use. Ultimately it is a fun bit of magic that's nice to know and marvel at.

And that magic is what caused Paul Graham – a hardcore functional programmer himself – to name his startup accelerator Y Combinator. An apt metaphor for a company that takes a not-quiet-finished product as input and turns out a fully working version as output.

If you liked this article, consider subscribing to this site. Subscribing is free.

Why subscribe? Here are three reasons:

1. You will get every new article as an email in your inbox, so you never miss an article
2. You will be able to comment on all the posts
3. Once in a while, I will be posting conference talk slides, longer form articles (such as this one), and other content as subscriber-only

I first came across the Y Combinator in the book The Little Schemer. This is a fantastic book which is very accessible to even to beginner programmers. If you are interested in functional programming, then I would highly recommend checking it out. Chapter 9 of this book contains the section on the Y Combinator where it is derived from first principles with an explanation of every step.

And for those interested in the math of combinatoric logic, check out Raymond Smullyan's book To Mock a Mockingbird, where combinatoric logic is explained in the form of puzzles involving birds that sing various songs.