## Introduction

Most of the programmers are quite familiar with the common definition of a recursive function.
Let's take factorial for example, using C#:

static int Factorial(int n)
{
return n == 0 ? 1 : n * Factorial(n - 1);
}

Using lambda expression:

int n => n == 0 ? 1 : n * (???)(n - 1);

A lambda expression basically is a description of how the function works. The left of `=>`

is the function parameter,
for the prior one, the parameter is an integer called `n`

.
The right side of `=>`

is the way to produce the result of the function. for the prior one,
the result is also an integer (suppose the largest result we need is no bigger than the biggest value the integer in C# can present).
The only question need to be solved is the `(???)`

part.
It should be the function itself, but the function does not have a name so we can call it.

So, it seems if we need recursion, we have to give the function a name, like this:

Func<int, int> FactorialFunc = n => n == 0 ? 1 : n * FactorialFunc(n - 1);

`Func<int, int>`

means the type of `FactorialFunc`

is a delegate (aka, a type of function)
that takes a parameter of type `int`

,
and returns a result of type `int`

.
Actually, this code will give us a compilation error,
says that you cannot use `FactorialFunc`

before you have assigned it to some value.
(There is a hack to solve this problem, we'll see in the following part.)
Now, the question is, **how do we describe a recursive function without naming it?** The answer will lead us to the Y Combinator.

## Background

Mike Vanier wrote an excellent article about the Y Combinator, which this one is inspired a lot.
Mike uses Scheme language in his article to demonstrate, we will use C# here.
C# is a static and strong type language, so the extra work is to explicitly define what type a variable is.

## Derive the Y Combinator Step by Step

### C# Hacking

Now we are going to derive the Y Combinator step by step. But before we start,
remember you can't use a variable before you have assigned it to some value? So the hack is:

Func<int, int> fac1 = null;
fac1 = n => n == 0 ? 1 : n * fac1(n - 1);
int i1 = fac1(5);

It works! What have we done?
Well, we first declared a function `fac1`

and assigned it to a value of whatever, then we "redefined" it using recursion.
Since `fac1`

has already "assigned", we can use it in the "re-definition" and there is no compilation error.

### One Straight-Forward Approach

Take a look at the problem we need to solve again:

n => n == 0 ? 1 : n * (???)(n - 1);

Since we don't have the name of the function, why not pass the function itself as a parameter?

(self, n) => n == 0 ? 1 : n * self(n - 1);

When you need to calculate the factorial of `n`

, you not only supply `n`

as a parameter,
but also supply the function itself as another parameter.
But this will not work, since the function takes two parameters, and the `self(n - 1)`

is only supplied by one.
It should be like this:

(self, n) => n == 0 ? 1 : n * self(self, n - 1);

We know `self`

is a function (delegate) that takes two parameters,
one is a function type, the other is an `int`

type,
and returns `int`

type. We can define it in C#:

Func<Delegate, int, int> fac2Partial = (self, n) => n == 0 ? 1 : n * (int)self.DynamicInvoke(new[] { (object)self, n - 1 });
Func<int, int> fac2 = n => fac2Partial(fac2Partial, n);
int i2 = fac2(5);

It works! But note that the function which need "self" as a parameter is not really the factorial function
that takes an integer and returns an integer,
the real factorial function is the function when you put `fac2Partial`

to `fac2Partial`

as parameter.
Like this:

Func<int, int> fac2 = n => fac2Partial(fac2Partial, n);

Another thing we need to notice is that we have not specified the first parameter's type of `fac2Partial`

.
The first parameter's type of `fac2Partial`

is also the type of `fac2Partial`

itself.
The only thing we know is that it is a function, aka `Delegate`

.
And when we call the function, we don't know the function's signature,
So we have to use `DynamicInvoke`

method and try to pass two parameters to the function.

### If You Need to Know Its Type, You Need to Know Its Type First

C# is a static-type language, so what is the type of `fac2Partial`

?
Well, it is a function with two parameters, one of the parameters is `int`

type,
and the return is `int`

type, so basically its type is `Func<first-parameter-type, int, int>`

,
and the first parameter's type is just the function type itself,
so it's `Func<Func<first-parameter-type, int, int>, int, int>`

,
it's an infinite loop, if you need to know its type, you need to know its type first.

But things are not going to end. With some tricks:

delegate TR SelfApplicable<T1, T2, TR>(SelfApplicable<T1, T2, TR> self, T2 p);

We defined a function type with two parameters, `self`

and `p`

,
the type of `self`

is `SelfApplicable<T1, T2, TR>`

, that is the type of the function itself.
The other parameter's type is `T2`

, and the return type is `TR`

.

With this definition, we can define the type of the self-feeded function:

SelfApplicable<Func<int, int>, int, int> fac3Partial = (self, n) => n == 0 ? 1 : n * self(self, n - 1);
Func<int, int> fac3 = n => fac3Partial(fac3Partial, n);
int i3 = fac3(5);

And it works!

### Take It the Lambda Way

`fac3Partial`

is a function that takes two parameters. Using lambda calculus, we can convert it to a nested function,
the outer one takes the first parameter, and the inner one takes the second parameter:

fac4Partial = self => n => n == 0 ? 1 : n * self(self)(n - 1);

`fac4Partial`

takes one parameter `self`

,
and what it returns is a function `n => n == 0 ? 1 : n * self(self)(n - 1)`

.
This makes `fac4Partial`

a **high-order function**, that is, it produces functions.
By eliminating the parameter `n`

, the return value of `fac4Partial`

is no longer an integer,
but a function of `n`

. This is referred to **partial evaluation**.
The return type of `fac4Partial`

is `Func<int, int>`

,
so does the parameter's type of `fac4Partial`

. We can define it:

delegate T SelfApplicable<T>(SelfApplicable<T> self);
SelfApplicable<Func<int, int>> fac4Partial = self => n => n == 0 ? 1 : n * self(self)(n - 1);
Func<int, int> fac4 = n => fac4Partial(fac4Partial)(n);
int i4 = fac4(5);

It works! Note that in `n => n == 0 ? 1 : n * self(self)(n - 1)`

, we use `self`

,
which is defined out of the function's scope.
This is referred to a **closure**.

We can also write `fac4`

as:

Func<int, int> fac4 = fac4Partial(fac4Partial);

It works too, but they have a little but important difference.
`fac4 = fac4Partial(fac4Partial)`

means `fac4`

is **the product of** `fac4Partial`

when you supply `fac4Partial`

as the parameter, this expression defines **what the function is**.
`fac4 = n => fac4Partial(fac4Partial)(n)`

describes **how the function works**.
Keep this important difference in mind, it will solve big problems later.

### The Fix Point

Take a look back at the first attempt we try to construct the recursive factorial function:

n => n == 0 ? 1 : n * (???)(n - 1);

Since we don't know what `(???)`

should be, make it a parameter:

(Func<int, int> f, int n) => n == 0 ? 1 : n * f(n - 1);

Make it the lambda way, and define it with name `AlmostRecursiveFactorial`

AlmostRecursiveFactorial = f => n => n == 0 ? 1 : n * f(n - 1);

What is the type of `AlmostRecursiveFactorial`

? It's parameter is `f`

,
which is a function takes `int`

as parameter and returns `int`

,
and it returns `n => n == 0 ? 1 : n * f(n - 1)`

, which is also a function takes `int`

as parameter and returns `int`

.
We can define:

delegate Func<TIn, TOut> AlmostRecursiveFuncType<TIn, TOut>(Func<TIn, TOut> p);
static AlmostRecursiveFuncType<int, int> AlmostRecursiveFactorial = f => n => n == 0 ? 1 : n * f(n - 1);

Here comes the magic. Suppose that we have a real recursive factorial function named `RealRecursiveFactorial`

that will calculate the factorial of `n`

,
and use it as the parameter of `AlmostRecursiveFactorial`

, what will it produce?

AlmostRecursiveFactorial(RealRecursiveFactorial) = n => n == 0 ? 1 : n * RealRecursiveFactorial(n - 1);

`n => n == 0 ? 1 : n * RealRecursiveFactorial(n - 1)`

looks like a real recursive factorial function!
Actually, we can prove that the production of `AlmostRecursiveFactorial(RealRecursiveFactorial)`

is identical to `RealRecursiveFactorial`

.
This means `RealRecursiveFactorial`

is the **fix point** of `AlmostRecursiveFactorial`

.

Again, the fix point of the "almost-recursive function" is the "real-recursive function".

### Place the Recursion to Somewhere Else

OK, now we have an "almost-recursive" function, if we find its fix point, we find the "real-recursive" function.
And Here the magic Y Combinator comes. It can give the fix point of an "almost-recursive function":

fix-point-of-AlmostRecursiveFactorial = Y(AlmostRecursiveFactorial);
RealRecursiveFactorial = Y(AlmostRecursiveFactorial);

And we have: `RealRecursiveFactorial`

is identical to `AlmostRecursiveFactorial(RealRecursiveFactorial)`

,
we can derive:

Y(AlmostRecursiveFactorial) = AlmostRecursiveFactorial(Y(AlmostRecursiveFactorial));
Y = f => f(Y(f));

Here we get a definition of `Y`

. Let's practice this in C#, but first we need to define its type:

delegate Func<TIn, TOut> YType<TIn, TOut>(AlmostRecursiveFuncType<TIn, TOut> f);

`Y`

takes a parameter of "almost-recursive function" type and returns the "real-recursive" function.
Then we can define the Y Combinator using C# function and lambda expressions:

static Func<int, int> YIntRecursiveFunc(AlmostRecursiveFuncType<int, int> f)
{
return f(x => YIntRecursiveFunc(f)(x));
}
static YType<int, int> YIntRecursiveDelegate1 = f => n => f(YIntRecursiveDelegate1(f))(n);
static YType<int, int> YIntRecursiveDelegate2 = f => f(YIntRecursiveDelegate2(f));

Still, notice that the difference of **what** and **how** between `YIntRecursiveDelegate1`

and `YIntRecursiveDelegate2`

.
Sadly, we have to use explicit recursions in the definition of `Y`

.
It looks like we just replace the recursions from the recursive functions to the body of `Y`

.
But, at least this is one step forward. Let's see if this will work.

var fac5 = YIntRecursiveFunc(AlmostRecursiveFactorial);
int i5 = fac5(5);
var fac6 = YIntRecursiveDelegate1(AlmostRecursiveFactorial);
int i6 = fac6(5);
var fac7 = YIntRecursiveDelegate2(AlmostRecursiveFactorial);
int i7 = fac7(5);

`fac5`

works fine, but that's not a surprise, it still uses recursive functions.
`fac6(5)`

seems to work fine too.
But the real interesting thing is, when evaluating `fac7`

, stack overflows. It looks like that it has gone into some infinite loop.
Actually, you can try evaluating `fac7`

using `YIntRecursiveDelegate2`

, the evaluation will be infinite.
But why `YIntRecursiveDelegate1`

works? Take a look at the definition of `Y`

:

Y = f => f(Y(f));

When you supply `f`

with the "almost-recursive" function, you will get the "real-recursive" function. That is,
`Y(f)`

is a function. But when you try to get it, you go into infinite loop.
However, if you just accept that you will never get the function, all you can do is describing **how it works**, the problem is solved.
The function itself will never be evaluated, but when you use it, like `Y(f)(5)`

, because you have described how it works,
you will get the result of the function. The principal is **avoiding evaluating functions, but describing it**.
How to describe a function? The answer is lambda expression:

Y = f => f(n => Y(f)(n));

Here we describe `Y(f)`

by using lambda expression `n => Y(f)(n)`

.
So `fac6`

won't be evaluated when you define it as `var fac6 = YIntRecursiveDelegate1(AlmostRecursiveFactorial)`

.
But you have clearly described how `fac6`

should work, so when you apply the parameter `5`

to `fac6`

,
it will give you the answer.

Still notice that in `YIntRecursiveFunc`

we use "describing".
If we write the function like this `return f(YIntRecursiveFunc(f));`

, it won't work, I think you have got the idea.
And here's a question for you: will the following code work? And why?

Func<int, int> facX = n => YIntRecursiveDelegate2(AlmostRecursiveFactorial)(n);
int iX = facX(5);

### Infinite Loops

As for now, we have solved the problem, partially, by replacing the recursion into Y Combinator. The final goal is to eliminate recursions totally.
But before that, let's go through some infinite loops, hope that we can still come back.

Let's start from `fac4`

, but define the `self(self)`

thing as a variable `f`

:

SelfApplicable<Func<int, int>> fac8Partial = self => { var f = self(self); return new Func<int, int>(n => n == 0 ? 1 : n * f(n - 1)); };
var fac8 = fac8Partial(fac8Partial);
int i8 = fac8(5);

Looks like the `n => n == 0 ? 1 : n * f(n - 1)`

is the "almost-recursive" function, so `f`

could be the fix point!
However, this won't works, because evaluating `f`

leads to infinite loop.

We can use our pre-defined "almost-recursive" function here:

SelfApplicable<Func<int, int>> fac9Partial = self => AlmostRecursiveFactorial(self(self));
var fac9 = fac9Partial(fac9Partial);
int i9 = fac9(5);

Again, infinite loop.

Define the `AlmostRecursiveFactorial`

in the "partial" function:

SelfApplicable<Func<int, int>> fac10Partial = self => new AlmostRecursiveFuncType<int, int>(f => n => n == 0 ? 1 : n * f(n - 1))(self(self));
var fac10 = fac10Partial(fac10Partial);
int i10 = fac10(5);

Same.

Take a look back at `fac8`

. What about put the evaluation of `f`

into the `n != 0`

branch?

SelfApplicable<Func<int, int>> fac11Partial = self => new Func<int, int>(n => { if (n == 0) return 1; else { var f = self(self); return n * f(n - 1); } });
var fac11 = fac11Partial(fac11Partial);
int i11 = fac11(5);

It works! Because the evaluation of `f`

will only happens when `n`

is bigger than `0`

.
When `n`

decreases to `0`

, the infinite loop breaks.

Still start from `fac8`

, we place the "partial" function into lambda expression:

Func<int, int> fac12 = n => { SelfApplicable<Func<int, int>> fac12Partial = self => AlmostRecursiveFactorial(self(self)); return fac12Partial(fac12Partial)(n); };
int i12 = fac12(5);

Although infinite loop, we are closer and closer to Y Combinator. this time we do not define the "partial" function:

Func<int, int> fac13 = n => new Func<SelfApplicable<Func<int, int>>, Func<int, int>>(x => x(x))(self => AlmostRecursiveFactorial(self(self)))(n);
int i13 = fac13(5);

If we don't use `n`

explicitly, like this:

Func<int, int> fac14 = new Func<SelfApplicable<Func<int, int>>, Func<int, int>>(x => x(x))(self => AlmostRecursiveFactorial(self(self)));
int i14 = fac14(5);

The evaluation of `fac14`

leads to infinite loop, because we are not "describing" it.

Take `AlmostRecursiveFactorial`

out and make it a parameter, we get the Y Combinator:

YType<int, int> NormalOrderY1 = f => new Func<SelfApplicable<Func<int, int>>, Func<int, int>>(x => x(x))(self => f(self(self)));
var fac15 = NormalOrderY1(AlmostRecursiveFactorial);
int i15 = fac15(5);

By applying the lambda expression `self => f(self(self))`

to `x => x(x)`

, then we get:

YType<int, int> NormalOrderY2 = f => new Func<SelfApplicable<Func<int, int>>, Func<int, int>>(x => f(x(x)))(x => f(x(x)));
var fac16 = NormalOrderY2(AlmostRecursiveFactorial);

These Y Combinators has no explicit recursions. They are referred to the **normal-order Y Combinators**.
However, they won't work in C#, all we have got are infinite loops.

### I'm Not Going to Tell you, I Will Only Describe for You

Take a while to recall the way we have done to solve infinite loops: describing. Delay the evaluation to when it is really needed,
until then, everything has to be described but not defined. Take a look at `fac8`

. Because we defined a variable `f`

,
then the evaluation of `f`

leads us to infinite loop. What if we just describe `f`

?

SelfApplicable<Func<int, int>> fac17Partial = self => { Func<int, int> f = y => self(self)(y); return new Func<int, int>(n => n == 0 ? 1 : n * f(n - 1)); };
var fac17 = fac17Partial(fac17Partial);
int i17 = fac17(5);

It works! Just by changing the definition to description. So, let's also try changing the `x(x)`

thing in `NormalOrderY2`

:

YType<int, int> ApplicativeOrderY1 = f => new Func<SelfApplicable<Func<int, int>>, Func<int, int>>(x => f(y => x(x)(y)))(x => f(y => x(x)(y)));
var fac18 = ApplicativeOrderY1(AlmostRecursiveFactorial);
int i18 = fac18(5);

Actually it could also be like this:

YType<int, int> ApplicativeOrderY2 = f => new Func<SelfApplicable<Func<int, int>>, Func<int, int>>(x => f(x(x)))(x => f(y => x(x)(y)));
var fac19 = ApplicativeOrderY2(AlmostRecursiveFactorial);
int i19 = fac19(5);

Both of these works! Finally we have eliminated all explicit recursions and get our usable Y Combinators.
These are referred to the **applicative-order Y Combinators**. Problem solved!

## Summary

Functional programming makes us to think how things works, not what they are. When we describe how the functions should work,
they don't really do the work. Nothing is produced. We can apply more and more functions to make a nested description,
and when we apply the input parameter to the function, the nested functions just expand automatically and produce the answer.

With this article would help you think in a functional way!

## History

Revision 0.1, May 27th, 2014