# Recursion

Insert some tired, self-referential joke here.

For more information, see also this enlightening post on recursion

It’s fucking weird. It’s also the crucial property of a language that makes it *Turing-complete* (that is, powerful enough to compute anything which can be computed). An equivalent property is to be able to write looping procedures which last an arbitrary number of iterations.

It’s often baked into a language and while it works it makes no sense intuitively.

So, we are going to pretend the Scheme language **doesn’t** have recursion, and **create it ourselves**. Our goal will be to write a factorial function which works while not referring to itself.

For reference, here is the procedure we are trying to emulate This will blow up the stack and fail miserably on even moderately large numbers. It is purely for pedagogical purposes.

:

# 1 Let’s go

Without recursion, we have the following hole in our logic:

Since we can’t call `fact`

(as it hasn’t been defined yet), what can we do?

What if - and please bear with me - somehow we were able to *give* `fact`

the next function it should call? Like this:

```
(define fact-sort-of
(lambda (call-me-next)
(lambda (n)
(if (zero? n)
1
(* n (call-me-next (- n 1)))))))
```

`fact`

is a function which returns *another* anonymous function with an argument `call-me-next`

, which otherwise wraps our original function. Well, what if you were able to do something like this:

That is to say, what if you could get that anonymous function from `fact`

and then apply it to itself?

# 2 The universe is a snake beating itself

We want to automate the process of applying a function to itself, returning the composition of the two functions and saving the galaxy from the bug invaders.

Things we know:

This recursion-maker-function-thing will accept one argument, the function to be fucked with.

It will return the application of a function to itself.

Let’s sketch something:

When I run this, it tells me I’m a huge loser who will never find true love. But why?

`F`

and `fact-sort-of`

are functions which accept other functions as arguments. They return … functions which accept other functions as arguments. Passing in `5`

just isn’t going to cut it.

# 3 Time is a cat circle

Let’s back up and think much more simply. `fact-sort-of`

returns a function which accepts a function, and we know that the one it accepts is going to be itself. Make your goddamn *Inception* jokes now, if you must.

Our goal is to write a factorial function that receives itself as an argument instead of referring to its own name.

We know that since this argument is itself, and

*it*needs to be fed itself to work, that this argument is going to have to be fed to itself.Thus, we define the correct function, and then we define it

*again*as an*argument*to the first one.

```
(define fact-sort-of
((lambda (call-me-maybe)
(lambda (n)
(if (zero? n)
1
(* n ((call-me-maybe call-me-maybe) (- n 1))))))
(lambda (call-me-maybe)
(lambda (n)
(if (zero? n)
1
(* n ((call-me-maybe call-me-maybe) (- n 1))))))))
(fact-sort-of 5)
```

HOLY JUMPING JEHOSEPHAT it worked. *It worked!* **IT WORKED.**

… why, again?

Imagine that the `lambda`

calls were replaced with `foo`

. Then the thing looks like this:

Okay, so this worked. But as wise men once said,

Our work is never over

Daft Punk

# 4 I hate you so fucking much Gatlin

So how do we write a general function-fucker that works for any (single-argument) function? Let’s abstract our general technique:

`target`

is a function which wishes to receive itself so that it can begin autophagia. The two `lambda`

expressions are going to be identical, though, so figuring out one means figuring out the other.

Indeed, the `lambda`

s are *also* functions which expect to be given themselves as their next move, with the understanding that the first will receive the second as an argument **OH MY GOD I’M CROSS EYED**

The whole fucking point of this is to turn the `target`

into a recursive function, so we may as well cut the foreplay and call it:

So far, so good. Resisting the tempation to replace the ellipses with `target`

and be mocked again by the cruel lifetime of loneliness ahead, what should we give it?

It wants to receive a function it can call when it’s ready to call itself. The *itself* part expects to receive the actual function argument and do something with it. Let’s add this:

```
(define function-fucker
(lambda (target)
((lambda (f)
(target (lambda (arg) ...)))
(lambda (f)
(target (lambda (arg) ...))))))
```

And what should *that* inner function do with its argument? Why, it should use `f`

, the roundabout reference back to `target`

, to –

**HOLD IT RIGHT THERE DON’T YOU FUCKING DARE GIVE arg TO f**

`f`

is a function expecting another function. It will not accept a number. FUCK WHEN DOES THIS END

wait wait wait didn’t we tie the knot earlier, so-to-speak, by passing `call-me-maybe`

to itself?

# 5 VIOLA!

```
(define function-fucker
(lambda (target)
((lambda (f)
(target (lambda (arg) ((f f) arg))))
(lambda (f)
(target (lambda (arg) ((f f) arg)))))))
(define fact-sort-of
(lambda (k)
(lambda (n)
(if (zero? n)
1
(* n (k (- n 1)))))))
(define fact (function-fucker fact-sort-of))
(fact 5)
```

We get `120`

, as expected. Let’s walk through what happens when we fuck the function:

```
(function-fucker fact-sort-of) ; =>
((lambda (target)
((lambda (f)
(target (lambda (arg) ((f f) arg))))
(lambda (f)
(target (lambda (arg) ((f f) arg))))))
fact-sort-of)
; =>
((lambda (f)
(fact-sort-of (lambda (arg) ((f f) arg))))
(lambda (f)
(fact-sort-of (lambda (arg) ((f f) arg)))))
; =>
(fact-sort-of
(lambda (arg)
((lambda (f)
(fact-sort-of (lambda (arg) ((f f) arg))))
(lambda (f)
(fact-sort-of (lambda (arg) ((f f) arg)))))))
; =>
(lambda (n)
(if (zero? n)
1
(* n
((lambda (arg)
((lambda (f)
(fact-sort-of (lambda (arg) ((f f) arg))))
(lambda (f)
(fact-sort-of (lambda (arg) ((f f) arg))))))
(- n 1)))))
; => ...
```

And that’s what the body of `fact-sort-of`

becomes.

`function-fucker`

has an actual name. A fellow named Haskell Curry drummed it up, and it’s called the **Y combinator** (“combinator” is a fancy word for “function with one argument you ignorant pigfucker”).

Its name derives from the two identical lambda functions. Cute, huh?

xoxo Gatlin gatlin@niltag.net