# Recursions without names: Introduction to the Y combinator in ruby

This is an introductory article to the Y combinator from `lambda-calculus`

. But we won’t mention the `Y combinator`

in this article.

This article is the first one of a serie about the Y combinator in `ruby`

:

- Recursions without names: Introduction to the Y combinator in ruby
- The Y combinator in ruby
- Y combinator real life application: recursive memoization in ruby

In this article, we are going to show how to write recursive functions in `ruby`

without giving names to any function.

(If you are curious to see it in other languages, there is a version of the code in `clojure`

and `javascript`

.)

At first glance, it seems impossible: how could we refer to something that we are currently defining without using its name?

All the code snippets of this page are **live** and **interactive** powered by the klipse plugin:

**Live**: The code is executed in your browser**Interactive**: You can modify the code and it is evaluated as you type

## Begin with the end in mind

The end result of this article is the recursive implementation of the `factorial`

function without using neither names nor loops.

Here is the code:

```
->(f){
f[f]
}[->(func){
->(n) { n == 0 ? 1 : n * func[func][n-1]}
}][19]
```

As you can check, no mention of any names.

At first, it feels like magic.

Now, we are going to show the 4 step process that leads to this wonderful piece of code.

(We were inspired by this long but awesome article by Mike Vanier.)

## The process

# Step 0: recursive function

Let’s start with the recursive implementation of `factorial`

:

```
$factorial = ->(n) {
(n === 0) ? 1 : n * $factorial[n - 1]
}
$factorial[10]
```

# Step 1: simple generator

Let’s write a function that is a generator of the `factorial`

function:

```
$factorial_gen = ->(f) {
->(n) {(n === 0) ? 1 : n * f[n - 1]}
}
nil
```

One one hand, `factorial_gen`

is not recursive.

On the other hand, `factorial_gen`

is not the `factorial`

function.

But the interesting thing is that if we pass `factorial`

to `factorial_gen`

it returns the `factorial`

function:

```
$factorial_gen[$factorial][19]
```

Before going on reading make sure you understand why it is true that:

`$factorial_gen[factorial]`

is equivalent to`$factorial`

# Step 2: weird generator

Now, we are going to do something very weird: instead of using `func`

, we are going to use `(func func)`

. Like this:

```
$factorial_weird = ->(f) {
->(n) {(n === 0) ? 1 : n * f[f][n - 1]}
}
nil
```

The funny thing now is that if we apply `factorial_weird`

to itself we get the `factorial`

function:

```
$factorial_weird[$factorial_weird][19]
```

Before going on reading make sure you understand why it is true that:

`$factorial_weird[factorial_weird]`

is equivalent to`factorial`

# Step 3: Recursion without names

Now, let’s write down the application of `factorial_weird`

to itself, using the body of `factorial_weird`

instead of its name:

```
$factorial_no_names = ->(f) {
->(n) {(n === 0) ? 1 : n * f[f][n - 1]}
}[->(f) {
->(n) {(n === 0) ? 1 : n * f[f][n - 1]}
}]
$factorial_no_names[19]
```

And we got a recursive implementation of `factorial`

without using any names!

We gave it a name just for the convenience of using it.

As you can check, this is a completely valid implementation of `factorial`

:

```
(1..11).map(&$factorial_no_names).to_a
```

Do you understand why this is equivalent to the code we shown in the beginning of the article?

```
->(f){
f[f]
}[->(func){
->(n) { n == 0 ? 1 : n * func[func][n-1]}
}][19]
```

Can you write your own implementation of other recursive functions without names?

Share in the comments your implementation for:

- Fibonacci
- Quicksort
- max
- min
- …

In our next article, we are going to show the Y combinator in action in `ruby`

.