-- Alan Perlis

# Prelude

In the previous post where we discovered the Y-Combinator by mistake, we set on to solve the following odd challenge.

**n**. You may only use function calls, but you may not call a function from inside its body i.e. no explicit recursion! In other words, your solution should be rewritable as a lambda expression which returns the factorial of

**n**. Also, assume that you language doesn’t support looping mechanisms.

And we concluded that we can re-write the following definition of calculating factorial of a given number `n`

:

```
def factorial(n):
return 1 if n == 0 else n*factorial(n-1)
factorial(11) #39916800
```

as a lambda expression,

```
(lambda copy0: lambda n: 1 if n==0 else n*copy0(copy0)(n-1))(
lambda copy0: lambda n: 1 if n==0 else n*copy0(copy0)(n-1))(11) # 39916800
```

To summarize the previous post, we wanted to solve the problem of calculating the factorial of a number recursively, only this time, without calling named functions in their own bodies i.e. without explicit recursion.

# So, where is the Y-Combinator?

The lambda expression given above allows for the recursive computation of factorial, and yet, it doesn’t use explicit any recursion i.e. it doesn’t refer to a function by name in its own body. The lambda expression solution guarantees that as long as our programming language environment of choice provides us with a mechanism to write and evaluate lambda expressions, we can achieve recursion, even if explicit recursion is not provided by the language by default!

A visual form of recursion known as the Droste effect(source: Wikipedia)

**A combinator, in lambda calculus lingo, is a lambda expression that contains no free-variables. And a Y-Combinator is fixed-point combinator that returns a fixed point of its argument function such that the returned value (i.e. the argument function passed to the Y-combinator) can be called again and again.**

In other words, the Y-combinator modifies a function such that the return value of the function can be a copy of the original function itself (which can then be applied again and again)! It shouldn’t come as a surprise then that the Y-Combinator is a mechanism which can achieve recursion by applying the same function again and again, and yet it can be written as a lambda expression i.e. without calling a function in its own body (since the Y-combinator ia combinator).

In the previous post, I claimed that the Y-Combinator is hidden somewhere in the mechanisms of the code above. Now, in the above lambda expression, we notice the following boilerplate code:

```
lambda x: lambda y: ... x(x)(y)(
lambda x: lambda y: ... x(x)(y))
```

And most of the actual application specific (in our case, factorial calculation) logic is in the `...`

part. Let’s try to separate the boilerplate of the recursion mechanism (i.e. the Y-combinator) and the recursive logic.

## Extracting the Y-Combinator

In this part we will try to decouple our above lambda expression into two parts, **1.** a general purpose Y-Combinator (hopefully), and **2.** the actual logic for calculating the factorial or whatever you might need recursion for.

Let’s use assignment to make avoid having to use the large lambda expressions.

```
partial_factorial = lambda copy0: lambda n: 1 if n==0 else n*copy0(copy0)(n-1)
```

Then, the original lambda expression equivalent would be,

```
partial_factorial(partial_factorial)(11) #39916800
```

The `partial_factorial(partial_factorial)`

part can be generalized by

```
recursive = lambda f: f(f) #recursive(partial_factorial)(11) gives 39916800
```

Now, we would be able to solve the factorial problem as follows:

```
recursive(lambda recurse: lambda n: 1 if n==0 else n*recurse(recurse)(n-1))(11) #39916800
```

Nothing cool here, but can get rid of the ugly bit `recurse(recurse)`

in the above style inside the inner lambda. We can write another lambda expression to avoid having to write `recurse(recurse)`

. Let’s call it `double_apply_inside`

to stand for applying the function passed to it applied to itself but in an inner lambda expression.

```
double_apply_inside = lambda f: lambda g: f(lambda y: g(g)(y))
```

`double_apply_inside`

needs some explanation since it’s too far from usual style of Python programming. Basically, the outer lambda argument `f`

will point to the definition of the function we pass to it, for example, `partial_factorial`

. Think of it as currying of some flavor. When `f`

is `partial_factorial`

, then `lambda f: lambda g: f(lambda y: g(g)(y))(foo)`

would result in an expression of type `lambda g: lambda n: 1 if n==0 else n*foo(foo)(n-1)`

, exactly what we needed.

** NOTE-** do not ever confuse yourself by thinking that

`g(g)(y)`

in `lambda y: g(g)(y)`

would get evaluated right away. `g(g)(y)`

would be evaluated only when the lambda expression is *applied*to the argument

`y`

, otherwise the lambda expression in itself serves as a value.Equipped with all that we have, we can simplify the definition of `partial_factorial`

as follows:

```
partial_factorial = lambda recurse: lambda n: 1 if n==0 else n*recurse(n-1)
# Here's how you'd call it
recursive(double_apply_inside(partial_factorial))(11) #39916800
```

Now we have `recursive`

and `double_apply_inside`

doing our general purpose recursion job, and the factorial job is handled by `partial_factorial`

. Decoupling complete! And what is worth celebrating here is that each decoupled part is a combinator itself- i.e. no free variables. A combinator, since it contains no free-variables, can be used to substitute its name with its lambda expression, or vice-versa, anywhere in the program.

One last time, let’s combine `recursive`

and `double_apply_inside`

into one and, lo and behold, we have something really beautiful:

```
# expects function 'f' as argument
recursion_combinator = lambda f: recursive(double_apply_inside(f))
# since `recursive` and `double_apply_inside` are both combinators,
# we can substitute their names accordingly.
recursion_combinator = lambda f: \
double_apply_inside(f)(double_apply_inside(f))
# NOTE: Substitute function calls with the result of evaluations!
recursion_combinator = lambda f: \
(lambda g: f(lambda y: g(g)(y)))\
(lambda g: f(lambda y: g(g)(y)))
recursion_combinator(partial_factorial)(11) #39916800
```

`recursion_combinator`

is the combinator that allows for achieving recursion!

You could use it for any general purpose recursion (without having to use explicit recursion!). For instance, you can reverse a string as follows:

```
reverse_string = lambda recurse: \
lambda n: '' if len(n)==0 else n[-1]+recurse(n[:-1])
recursion_combinator(reverse_string)('abcde') #edcba
```

**You might be asking yourself- isn’t recursion_combinator exactly the Y-combinator we have been looking for?**

## Y-Combinator and the Z-Combinator?

Python is a strict programming language and only allows functions whose parameters must be evaluated completely before they may be called. It turns out to be the case that in such a language, the Y-combinator will never halt since it will run into an infinite recursion in an attempt to evaluate the recursive function argument(s).

Therefore, strictly speaking, `recursion_combinator`

is not the ‘common’ Y-combinator, but it is also the closest you will get to in Python.
What we have is more precisely what is called the Z-combinator- it prevents the infinite recursive by using a lambda expression as a value.

Practically, the Z-combinator is the ad hoc Y-Combinator for a strict programming language. For the sake of completeness, if Python were not a strict language (Haskell, for example, uses *lazy evaluation*), the ideal Y-combinator in python would look like this.

```
# recursive, but would cause stack overflow!
Y_combinator = lambda f: \
(lambda g: f(g(g)))\
(lambda g: f(g(g)))
```

But this would then run into an infinite recursion, and hence not suitable for a strict language like Python. For practical purposes, you would have to use the Z-combinator instead.

You could, however, refactor `recursion_combinator`

into a beast that resembles a bit of the Y-combinator and a bit of the Z-combinator. You name it yourself, please. Here’s how it looks:

```
recursion_combinator = lambda f: \
(lambda g: f(g(g)))\
(lambda g: f(lambda *y: g(g)(*y)))
```

As a bonus, using `*y`

would now also allow for handling multiple arguments in recursive problems. Interestingly enough, RosettaCode entry for the Y-combinator in Python features a ‘Y-combinator’ entry that resembles the above refactored version of `recursion_combinator`

.