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:
- 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.
- 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.
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.
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.
(1,1). If we then use
(1,1) as the starting point for calculating the next pair, we get
(1,2) can be used to generate
(2,3) can be used to generate
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:
- We need an additional error function to trap the times when we push our little one-step engine too far.
- Rename function
- Rename function
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.
"KABOOM!" result when we call
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
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
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...
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
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
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 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...
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_next just to avoid having two different names for the same value.
So we'll now do two things:
fib_stepa copy of itself as its parameter. Notice that since
fib_stepexpects a function as a parameter and not a list of numbers, we must pass
fib_stepas the first parameter to itself. Then, since
fib_stepreturns 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.
- Rename all occurances of
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:
- We have a partial function that receives a parameter called
(fib_next => fib_next(fib_next))
- This partial functions calls whatever function it receives as a parameter and immediately passes that function to itself as a parameter. In other words:
- Some function is received in parameter
- We call this function
- When calling this function, we pass it a copy of itself
fib_next(fib_next). This ensures that no matter what function
fib_nextactually does, it always receives a copy of itself and can therefore take one more step down the recursive rabbit hole.
- Some function is received in parameter
- The value of parameter
fib_nextis 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));
- 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.
- 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 < 1becomes 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.
All source code from the Mindshift blog series can be found on GitHub