# Recursion Using Only Anonymous Functions

Maybe I should start with a warning: Before reading this blog, please ensure that you understand the principles of functional refactoring described in the previous Mindshift: Part 9 blog. If you don't understand these principles already, what follows might well appear cryptic or even nonsensical.

Remember back in Mindshift: Part 4 we stated that we would confine ourselves to writing code that:

1. Uses only anonymous functions - well OK, we cheated here and named the functions, but the principle of inline function definition demonstrated that such function names are actually unnecessary.
2. These (mostly) anonymous functions should take only one parameter

Well, this is all pretty straightforward up till the point we need to write a recursive function.

The classic example of recursion is the good old factorial function - which is exactly why I'm not going to use it. Instead, I'll use another common recursive function that calculates the n'th Fibonacci number.

However, we have a problem. Our rules state that all our functions should be anonymous; therefore, how can an anonymous function call itself recursively? What name should it use to identify itself?

In the above example, the definition of the `fib` function contains a reference to itself, and this breaks the rules.

So, we need to start refactoring things.

## Refactoring The `fib` Function

### Attempt 1

We could try the following approach. Since `fib` contains a reference to itself, why don't we wrap it in another function that takes the definition of `fib` as a parameter.

Hmmm, think about that for a moment... That won't work, will it.

All we've done here is move the problem to the point where we call `make_fib`. We haven't done anything to change the fact that function `fib` still contains a self-reference.

### Attempt 2

Let's think about the way the Fibonacci series is calculated. We know it works in a stepwise manner: it starts with the number pair `(0,1)`, then it performs a "shift and add" operation and outputs the next number pair.

So `(0,1)` becomes `(1,1)`. If we then use `(1,1)` as the starting point for calculating the next pair, we get `(1,2)`; then `(1,2)` can be used to generate `(2,3)`, and `(2,3)` can be used to generate `(3,5)` etc.

So in general, we can say that given a number pair `(a,b)`, we shift and add these numbers to generate the output `(b,a+b)`, and we do this as many times as needed.

So to start with, we will alter the definition of `make_fib` so that, given the starting number pair of `(0,1)`, it moves us only one step further down the series.

We need to change several things here:

1. We need an additional error function to trap the times when we push our little one-step engine too far.
2. Rename function `make_fib` to be `fib_next`
3. Rename function `fib` to be `fib_step`

Here, we pass the `fib_next` function the `error` function as its parameter. This function then appears as the parameter `fib_step` and will be called when `n` is greater than or equal to one.

Hence, the `"KABOOM!"` result when we call `fib0(1,0,1)`.

Ok, that's a start - but it doesn't get us very far does it?

But let's look at how function `fib_next` works. Its a higher order function that takes a single function as a parameter and gives back a partial function in three parameters. When this partial function (here called `fib0`) is supplied with the relevant parameters, it is then able to calculate the first number in the Fibonacci series.

So if we start nesting `fib_next` calls inside each other, we should get back functions that calculate the number of the Fibonacci series corresponding to the number of nested `fib_next` calls...

Well that works, but all those nested calls are just silly...

OK, let's remove the nested calls by passing `fib0` back into `fib_next`, to generate `fib1`, then use `fib1` to generate `fib2` etc...

Well we're getting closer to the goal. All we need to do is decide what the highest number we be that we will ever need from the Fibonacci series, and call `fib_next` that many times...

Uh, no! That's not much of a solution is it?

Yeah, you're right...

### Attempt 3

Ok, so let's refactor function `fib_next` using the function wrapping technique we saw in the previous blog. Remember how this works? This is where we wrap a function inside another function and then immediately call the new wrapper function. It is optional whether you pass the new wrapper function a parameter, but in this case, we're going to pass an inline definition of `fib_next`.

In the code below, we have wrapped `fib_next` in an anonymous function that takes a single parameter. Then, we immediately call this wrapper function passing in the definition of `fib_next` as an inline function.

In the previous code samples, we gave these generated partial functions names like `fib0` or `fib1` etc, but now, we'll just call it `fib_x`. This is to indicate we are detaching this partial function from any specific number in the Fibonacci series.

The new, anonymous wrapper function is a higher-order function that takes a single parameter called `fib_next`. `fib_next` needs to be a function because we then make two nested calls to it.

The two levels of nested call make this exactly the same as the line of code we saw in attempt 2 above where we defined:

`fib1 = fib_next(fib_next(error))`.

Next, we need to immediately invoke this new, anonymous function. But we can't just invoke the function without passing it a value to work with, so we surround the inline definition of `fib_next` in parentheses, making it the parameter value to the wrapper function.

`(fib_step => (n,a,b) => n < 1 ? a : fib_step(n-1,b,a+b))`

Hmmmm, we've added another layer of indirection here, but it looks like a backward step because we can only calculate the first and second numbers in the series. We still don't seem to be much closer to a general solution...

### Attempt 4

We know that the wrapper function we've just created is a higher-order function that takes a function as its parameter; however, the only function we've ever passed it so far has been the `error` function. But the `error` function doesn't serve any useful purpose in terms of calculating numbers in the Fibonacci series: it simply writes a silly string to the console when called. So let's try doing without it.

Huh, that's odd! This works for the first number in the Fibonacci series (index zero), but returns a function when asked for any number further down the series.

But take a look at the returned function - haven't we seen that before? Yes, of course! Its the original Fibonacci function!

So for any index number higher than 0, we get back a copy of the Fibonacci function. Well in the same way that we created nested calls to `fib_next` in attempt 2, we need to pass this Fibonacci function to another function in order to get it to calculate the next number in the series.

Well, the perfect function to use here is `fib_step`, because this already does exactly what we want.

So we have now arrived at the point where we can start to see why all this refactoring was necessary. Since we have turned our recursive function into an inline definition that is then passed around as a parameter, we can implement recursion without ever needing to assign that function a global name.

And just for the sake of clarity, it is somewhat redundant to use the name `fib_step` inside the function definition, because this hides the fact that this value is nothing more than the definition of `fib_next`. So although it is not a technical requirement, we can rename `fib_step` to `fib_next` just to avoid having two different names for the same value.

So we'll now do two things:

1. Pass `fib_step` a copy of itself as its parameter. Notice that since `fib_step` expects a function as a parameter and not a list of numbers, we must pass `fib_step` as the first parameter to itself. Then, since `fib_step` returns a partial function, the existing parameters `(n-1,b,a+b)` become the parameters to the partial function that actually calculates the required number in the Fibonacci series.
2. Rename all occurances of `fib_step` to be `fib_next`, because the same functionality used in both places.

Ok, so where does that leave us?

In the immortal words of First Mate Gibbs from the Pirates of the Caribbean:

"Slap me thrice and hand me to my Mamma!"

We've implemented recursion using only anonymous functions!

Let's break down what we've done so far:

1. We have a partial function that receives a parameter called `fib_next`.
`(fib_next => fib_next(fib_next))`
2. This partial functions calls whatever function it receives as a parameter and immediately passes that function to itself as a parameter. In other words:
1. Some function is received in parameter `fib_next`
2. We call this function
3. When calling this function, we pass it a copy of itself `fib_next(fib_next)`. This ensures that no matter what function `fib_next` actually does, it always receives a copy of itself and can therefore take one more step down the recursive rabbit hole.
3. The value of parameter `fib_next` is the function that actually knows how to calculate the Fibonacci series. However, this calculation is wrapped in a higher-order function that expects a definition of the function that must be called when another recursive step is required.
All of this information is supplied as the following inline definition:
```(fib_next => (n,a,b) => n < 1 ? a : fib_next(fib_next)(n-1,b,a+b)); ```
4. The call to `fib_next(fib_next)` returns a partial function that expects three numbers as parameters. This is the function that actually performs the required Fibonacci series calculation.
5. The function generated in the previous step now disappears down a recursive rabbit hole until it reaches the point at which the termination condition is satisfied (which in this case is when `n < 1` becomes true).
At this point, recursion stops and the required values are returned.

So, we have succeeded in implementing recursion using nothing but anonymous functions!

This is great if we want only to calculate the Fibonacci series; but unfortunately, its still not the generic Y-Combinator we're after.

Some refactoring is still needed before this recursive example is the actual Y-Combinator. This will be the subject of my next blog.

Chris W

All source code from the Mindshift blog series can be found on GitHub