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 `clojure`:

In this article, we are going to show how to write recursive functions in `clojure` without giving names to any function.

(If you are curious to see it in other languages, there is a version of the code in `javascript`, `EcmaScript6` and `ruby`.)

At first glance it seems impossible: how could we refer to something that we are currently defining without using its name? 1. Live: The code is executed in your browser
2. 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:

``````(((fn [f]
(f f))
(fn [func]
(fn [n]
(if (zero? n)
1
(* n ((func func) (dec n)))))))
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.)

# Step 0: recursive function

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

``````(defn factorial [n]
(if (zero? n)
1
(* n (factorial (dec n)))))
``````
``````(factorial 10)
``````

# Step 1: simple generator

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

``````(defn factorial-gen [func]
(fn [n]
(if (zero? n)
1
(* n (func (dec n))))))
``````

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 exactly `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:

``````(defn factorial-weird [func]
(fn [n]
(if (zero? n)
1
(* n ((func func)(dec n))))))
``````

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 exactly `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:

``````(def factorial-no-names
((fn [func]
(fn [n]
(if (zero? n)
1
(* n ((func func) (dec n))))))
(fn [func]
(fn [n]
(if (zero? n)
1
(* n ((func func) (dec n))))))))
``````

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`:

``````(map factorial-no-names (range 20))
``````

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

``````(((fn [f]
(f f))
(fn [func]
(fn [n]
(if (zero? n)
1
(* n ((func func) (dec n)))))))
19)
``````

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

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