MS Excel: How to develop a recursive function

Introduction

A recursive function returns a value that depends on the value that the function returns for another set of inputs. For example, the factorial function is

fact(0) = 1
fact(n) = n * fact(n-1) for n >= 1 and n in the set of integers        

There are other functions of this nature - see Recursive definition - Wikipedia.

There are also non-mathematical uses for recursion. Reversing a text string is an example. One can also leverage recursion for breadth-first and depth-first search algorithms - working with trees (as Computer Science defines them). In SQL, for example, a recursive solution using a Common Table Expression (or CTE) makes it almost trivial to navigate an organizational hierarchy.

Some of these functions do have an easy-to-follow non-recursive alternative. For some others, the non-recursive alternative may be difficult to understand. I find that a recursive solution can be easy to write, debug, understand, maintain, and extend. In such cases, I consider a non-recursive solution only if we have to meet some other requirement, such as performance.

There are three sections to this article

• Recursion in Excel with the Name Manager
• Recursion in Excel with a local formula
• Recursion in other programming languages

Recursion in Excel with the Name Manager

[An alternative to the Name Manager is the Advanced Formula Environment: microsoft/advanced-formula-environment: Create, edit, and reuse formulas in Excel (github.com)]

If we create a function using the Name Manager, we can implement recursion in a very straightforward manner - in fact, simply follow the definition of the function. So, we can create the following:

_factorial	=LAMBDA(n,n*IF(n>1,_factorial(n-1),1))        

and then use it as

=_factorial(10)        

While this is very easy to do, the downside is that every such function is "global." For some, this might not be an issue. But, creating multiple global variables is a recipe for problems with maintenance and extendibility.

Recursion in Excel with a local formula

In Excel, we can build a recursive function within a single formula. To start, we have to combine the LET and LAMBDA to name a function. Unfortunately, it's not as straightforward as above. For example, if we were to try to duplicate the above, we would see

The IDE is offering no assistance with _fac - clearly, it does not recognize _fact at this point. The way Microsoft implemented LET and LAMBDA, Excel will only know about _fact after we complete the LAMBDA function - but we need to call _fact from inside the function! In fact, if we finish the formula, we will get the #NAME! error.

=LET(_fact,LAMBDA(n,n*IF(n>1,_fact(n-1),1)),
??? _fact(10))
#NAME?        

There is a way around this - use a placeholder function as a parameter to the LAMBDA. Then, we provide the actual function when we call the function. Below, we've added fx as the placeholder function. So, the function now has two parameters (fx and n), not just one (n). Then, inside the LAMBDA, we call fx, remembering that we have to provide it with two arguments, the placeholder function and a new value for n - that's the fx(fx, n-1) part.

=LET(_fact,LAMBDA(fx,n,n*IF(n>1,fx(fx,n-1),1)),        

Also, when we call _fact, we have to provide the actual function for the placeholder and the actual value for n. So, we get

=LET(_fact,LAMBDA(fx,n,n*IF(n>1,fx(fx,n-1),1)),
??? _fact(_fact, 10))        

The advantage of this approach is that if we want to use a function just once, we can keep it local to the cell - and not expose it as a global entity. The downside is that it is harder to understand.

For more on the how and the why see

• MS Excel: Functions are first-class objects and
• MS Excel: Recursive functions

Recursion in other programming languages

A language such as Python, Javascript, VBA, Java, SQL, or whatever, allows one to write a recursive function along the same lines as Excel using the Name Manager. At the same time, if the language supports nested functions, we can make the function local to another function - essentially getting the benefits of both approaches.

def fact(n):
? ? '''compute the factorial of n '''
? ? return(n*(fact(n-1) if n >1 else 1))        

or, with fact nested inside another function:

def myFunction(n):
? ? def fact(n):
? ? ? ? '''compute the factorial of n '''
? ? ? ? return(n*(fact(n-1) if n >1 else 1))
? ? # do other stuff
? ? return(fact(n))
print(myFunction(10))        

My previous article: (1) Phone Number Region Lookup | LinkedIn