In my recent post about TRIMRANGE (https://www.linkedin.com/posts/activity-7267473059383582720-mhJG) I mentioned that I would follow up with more to say about recursion.
Recursion is tricky in any context but probably even more so in Excel as it is not natively supported. However #Excel does support first-class functions and with that we can use a trick first discovered by Alan Turing which also goes by the scare name of "Theta Combinator", the lesser known but equally if not more useful cousin of the "Y Combinator" (if those terms don't scare you then have a look at https://en.wikipedia.org/wiki/Fixed-point_combinator). Incidentally the Y Combinator goes back to Haskell Curry after which the concept of "Currying" is named - a fascinating subject in its own right but a topic for another day.
In my TRIMRANGE implementation I defined a "_loop" LAMBDA which mimics a while loop in other languages. Now Excel Formulas are a "functional programming language" which limits what you can do with iteration because there are no "side-effects", i.e. you can't change anything except the value returned by the function or LAMBDA in our case. Nonetheless there are some useful things you can do with this so let's explore this below.
As alluded to above, recursion in Excel can be a bit tricky to get right and in order to simplify things I've bit I've created the RECURSIVE♾ LAMBDA function in order to hopefully simplify it a bit. RECURSIVE♾ takes two arguments:
- a
functionto make recursive - the
argument_countof the function
In order to make recursion work in Excel the function also has to take another argument, let's call it self (although you can call it whatever you like really). Note that the argument_count is the number of arguments without including self as you'll see below.
The canonical example of a recursive function is fib which returns the n-th Fibonacci number. Let's see how to implement FIB♾ in Excel:
FIB♾ = RECURSIVE♾(LAMBDA(self, n,
IF(n <= 2, 1, self(self, n - 1) + self(self, n - 2))
), 1);
- First note how the first argument of the LAMBDA function is
self. If you know Python then this might remind you of the self argument of methods in Python orthisin methods in Java. I chose this naming convention since this might already be familiar to you. If not then just remember thatselfmust always be the first argument and can be used to refer to the function you are writing inside the function. Crucially it also must be passed as the first parameter in any recursive calls, for example inself(self, n - 1).self(self, ...)is a bit of a mouthful but it's the best we can do in this setup. - The second argument to
RECURSIVE♾is 1 since our recursiveFIB♾function will only take 1 argumentn. Note that the functionselfhas 2 arguments,selfandn, butselfis a "nuisance" parameter and an implementation detail so we don't include it in our count. - You might be wondering about the ♾ in
RECURSIVE♾andFIB♾. That doesn't have any special meaning but I thought it would be a nice touch to have a convention to name all recursive LAMBDAs with a ♾ (the infinity symbol) at the end to mark that you might potentially get yourself in an infinite loop. That's not strictly true since you'll probably hit a Stack Overflow error instead of waiting indefinitely while contemplating the Halting Problem (another Turing contribution) but I thought it was a nice touch nonetheless.
With this in hand you can now use this anywhere in the Excel grid, for example:
=FIB♾(7)
which should hopefully give you 13.
Great, so we've seen that we can do recursion in Excel but can we do anything actually useful with it?
Just this week one of our Portfolio Managers asked me to assist with a portfolio optimisation problem. While I used the Excel Solver Add-in for that, objective function maximisation and root finding are a nice application so let's explore that.
Over the next two weeks, the festive "spirits" of many people can be approximated by the following XMAS function:
XMAS = LAMBDA(d, 1 + MAX(-1, -(d - 45651.5) * (d - 45651.5) *
(d - 45658) * (d - 45658) / 200));
The parameter d is an Excel date value and the output is scaled to the range [0,1]. Let's try to determine if the function has any maxima over the next two weeks. Hopefully you'll recall from calculus that in order to find the turning points of a function you need to find the derivative of the function and set that to zero. We can do this numerically in Excel with the following DERIVATIVE LAMBDA:
DERIVATIVE = LAMBDA(f, [step_size], [order],
LET(
_eps, IFOMITTED(step_size, 0.000001),
_order, IFOMITTED(order, 2),
CHOOSE(
_order,
LAMBDA(x, (f(x + _eps) - f(x)) / _eps),
LAMBDA(x, (f(x + _eps) - f(x - _eps)) / _eps / 2)
)
)
);
This function takes a function f as parameter and returns another LAMBDA which approximates the derivative numerically. In order to find where this derivative is zero we can use a "root-finding" algorithm such as the Newton-Raphson method. This is a recursive procedure which I've implemented as follows:
FINDROOT♾ = RECURSIVE♾(
LAMBDA(self, function, [guess], [target], [derivative_function], [tolerance],
// Uses Newton-Raphson method and numerical derivative to find function roots
LET(
_x, IFOMITTED(guess, 0),
_target, IFOMITTED(target, 0),
_f, IF(_target = 0, function, LAMBDA(x, function(x) - _target)),
_tolerance, IFOMITTED(tolerance, 0.000001),
_fprime, IFOMITTED(derivative_function, DERIVATIVE(function)),
_xn, _x - _f(_x) / _fprime(_x),
IF(ABS(_xn - _x) < _tolerance, _xn,
self(self, _f, _xn, 0, _fprime, _tolerance))
)
),
5
);
You'll notice that we again used RECURSIVE♾ and this time the argument_count was 5. Some of you will have noticed that only 1 argument is required and the last 4 arguments are optional. Please note that argument_count must include all required and optional parameters, with the exception of self.
If you try:
=FINDROOT♾(DERIVATIVE(XMAS))
you'll get an error. That is because the XMAS function is 0 outside the range [DATE(2024,12,23), DATE(2025,01,03)] and the Newton-Raphson needs a non-zero gradient to work. We can remedy the situation by supplying guess starting value near a suspected root/maximum. If you try:
=FINDROOT♾(DERIVATIVE(XMAS), DATE(2024,12,24))
you should get 2024-12-25 12:00 (be sure to include HH:MM in your output formatting). We can check that this is indeed a maximum with:
=AND(DERIVATIVE(XMAS)(DATE(2024,12,25)+0.5)=0,
DERIVATIVE(DERIVATIVE(XMAS))(DATE(2024,12,25)+0.5)<0)
which should return TRUE so this is indeed a maximum. So according to our XMAS function, festive "spirits" might peak around 2024-12-25 12:00 PM. 🎄
There's another maximum hidden in the XMAS function. Can you find the date and time? Share your approach in the comments!
I will be taking a break over the next few weeks and will be back next year with a follow up on CURRYing. Whether you're celebrating and/or taking a break or not, have a Merry Festive Season and all the best for the New Year! 🍾🥂
#Excel #Recursion #FunctionalProgramming