MS Excel: Recursive functions

In MS Excel: Functions are first-class objects, we saw how a custom Excel function, using LAMBDA, can call another function passed to it as a parameter. To recap, in the formula below, x is the name of the LAMBDA function. That function takes two parameters, f and n. f is a function and n is an integer and x then calls f passing n as an argument. So, calling x returns the value returned by f, which in this case happens to be _mult.

=LET(x,LAMBDA(f,n,f(n)),
? ? _mult,LAMBDA(n,PRODUCT(SEQUENCE(n))),
? ? x(_mult,9))
        

The function x can do more than simply return the value of f. It can be a formula in itself. An extension of the above is to call _mult with a modified value of n and to call it only if n is other than 1.

=LET(x,LAMBDA(f,n,IF(n=1,1,n*f(n-1))),
? ? _mult,LAMBDA(n,PRODUCT(SEQUENCE(n))),
? ? x(_mult,9))        

So far, we have passed the named function _mult as an argument to x. But, that is not necessary. We can have x call itself by passing x as an argument to x.

So, with a slight modification to how we call f - it goes from f(n-1) to f(f, n-1), we get the same result as above but with f calling itself recursively.

=LET(x,LAMBDA(f,n,IF(n<=1,1,n*f(f,n-1))),
? ? x(x,9))        

This is the classic recursive function, one that calls itself with a decrementing value for the argument. It also happens to be the definition of the factorial function, which is defined as the product of all integers 1..n where n is a non-negative integer.

In our case, the recursion ends when n is less than or equal to 1.

Recursion using the Name Manager

In the above section, we saw how to write a completely self-contained recursive function. It is also possible to write a recursive function using the Name Manger - and in some ways, it is easier to do so.

Instead of using the LET function to name a recursive function, we do the same through the Name Manager. It also lets us call the function without passing it as an argument.

The downside is every such formula becomes globally accessible in the worksheet or even the workbook. Those with a developer background know how much of a no-no it is to create global objects.

In Name Manager, define a name such as, say, _fact as

=LAMBDA(n,IF(n<=1,1,n*_fact(n-1)))        

Now, we can use it as _fact(9) to get the same result as above, i.e., 362880.

Is recursion always the way to go?

Recursion may appeal technically to some. However, it is not always necessary. Calling a function repeatedly is less efficient than non-recursive solutions such as loops or, even better, built-in functions.

For example, the factorial function is a great candidate for learning recursion. However, the straightforward PRODUCT(SEQUENCE(n)) also does the job.

Similarly, you will find examples through a 'Net search for recursive solutions to reverse a text string. One example, using the Name Manager to define the name Reverse is

=LAMBDA(str,IF(LEN(str)<=1,str,Reverse(RIGHT(str,LEN(str)-1))&LEFT(str,1)))        

And, the non-recursive solution is

=LAMBDA(s,TEXTJOIN("",,MID(s,SEQUENCE(LEN(s),,LEN(s),-1),1)))        

[For more on splitting a string into individual characters, see Split a string into its individual characters]

The Fibonacci series

Of course, there are instances where recursion is the only way to go. Examples include navigating a tree (looking up employees in an organizational hierarchy or navigating the nodes in a fishbone), searching for a target value using either a breadth-first or a depth-first search, or computing values that are defined recursively. An example of last is the Fibonacci series, in which the first 2 values are 0 and 1 with each successive value defined as the sum of the previous two. This gives us

F(0)=0
F(1)=1
F(n)=F(n-1)+F(n-2)        

The n-th term of the Fibonacci series is easily found by computing each of the values F(0), F(1), F(2), ...F(n-1), F(n)

=LAMBDA(i,
? ? LET(a,0,b,1,n,i,
? ? ? ? fib,LAMBDA(f,a,b,n,IF(n<=1,a,f(f,b,a+b,n-1))),
? ? ? ? fib(fib,a,b,n)))        

We can also return the entire Fibonacci series to the n-th term with the following modification - I have not seen an Excel function for this on the 'Net.

=LAMBDA(i,
? ? LET(a,0,b,1,n,i,
? ? ? ? fib,LAMBDA(fib,a,b,n,IF(n<=1,a,VSTACK(a,fib(fib,b,a+b,n-1)))),
? ? ? ? fib(fib,a,b,n)))        

Summary

Excel has dramatically enhanced its formula programming platform with dynamic array formulas, spill ranges, and first-class functions including LET and LAMBDA. This allows one to build sophisticated models without resorting to programming.

Have you explored recursive functions in general? In Excel? How does the Name Manager approach compare with the self-contained one? Do share your opinion or expertise in the subject.

My previous article: MS Excel: Functions are first-class objects