Sometimes writing a short, simple function, can hide in-depth processing that resolves quickly – by calling… itself * What is a recursive function, how does it work, what to be aware of and how it is implemented in Excel VBA – read on…

What is a Recursive Function?

Technically speaking, a recursive function calls itself as part of its program flow.

Yes, you read it correct. This is the general idea:

Function CalcSomething(…) as Long

     …

     X = CalcSomething(…)

     …

End Function

What is a recursive function good for?

Recursive function may be an elegant and quick way to resolve a challenge that can be converged into a simple test by repeating the same calculation while gradually reducing the calculated object.

OK, I know, this sounds complicated. Let’s try again.

The visual display that comes to my mind is the 1940 Walt Disney short cartoon: Fantasia.

In Fantasia, the apprentice magician is chartered with a tedious task of carrying water with two buckets to fill the well. Tempted to try out his magical skills, he tames a broomstick to carry the buckets, back and forth, while he arrogantly falls asleep into dreaming about how mighty a magician he is.

Soon enough, the hard-working broomstick floods the place, while our poor apprentice don’t know how to cancel the spell.

At his despair, the apprentice grabs an axe and shreds the broomstick into pieces.

Soon enough, each of the broken piece grows its own hands and legs and recurses what it was trained to do: carry buckets of water. As more of those broomsticks are broken – the broomstick army grows endlessly until…

Until the master arrives and cancels the spell.

The key takeaway from Fantasia that will help us understand recursive functions, is:

1. A single task that is repeated by smaller and smaller vehicles – the broomstick
2. A stop event that ends the process – the master magician’s cancel of the spell

I watched this cartoon as a child maybe 40 years ago, yet the vision of multiplication of broomsticks into smaller broomsticks that increase the task pace and output – was engraved in my mind and helped me grasp recursive functions decades later. Maybe it will be of help to you as well.

Conceptualizing a recursive algorithm

Let’s consider the following simple task: find a given country name within a list of countries of the world.

We assume that we have the list of countries sorted alphabetically.

We need to write an efficient VBA function to return True if the given country name is found in the list.

The list will be conveniently copied from an Excel Worksheet table into an array. You may recall that processing arrays is way faster that running over a range of cells.

The first approach that may come to mind, is running a loop over the array, matching each array member to our candidate country until a match, or until the loop ends.

I will now suggest a little different approach:

If we split the list of countries right in the middle, we can quickly judge whether our target country is expected to be found in the first half, or in the second half of the list (remember, our list is sorted!).

Having determined the target half, we have exactly the same task at hand: find our country in a list of countries, only our list is now HALF its original length. We have broken our broomstick!

Not only that, but since we are tasking our function to do exactly that: finding a country within a list of countries, we can call it again – to process a shorter list of countries this time!

We can now plot our function algorithm to be:

1. Split the received list of countries in half
2. If our candidate country matches the mid-list country – we found a match – exit the function
3. If the list length is 1 – our country is not here – exit the function
4. Identify the half expected to host our candidate country: left half or right half of the split
5. Go to step 1 with the selected half of the list

The power of our approach is derived by the exponential pace in which we reduce the size of our countries list, as we cut its size in half on each iteration. How many function calls are needed to cover a list of 200 countries?

First call – 200 countries

Second call – 100 countries

Third call – 50 countries

Fourth call – 25 countries

Fifth call – 13 countries

Sixth call – 7 countries

Sevenths call – 4 countries

Eights call – 2 countries

Ninths call – 1 country

Less than 10 function calls (and processing) are needed to crunch a list of 200 countries!

12 runs will cover more than 4,000 items (4,096, to be precise). It’s about the power of two (2^12 = 4,096).

This same approach is used in a bubble-sorting algorithm, which is a common assignment given to students to practice recursive functions: Split the list of items and sort two items only: the “left” against the “right”.

I trust you can clearly identify the two takeaways from the Fantasia cartoon:

1. The broomstick is our list of countries
2. The cancellation spell is a match of country event or a list of length=1

It is crucial to always have a stop event in a recursive function, or else our function will be called over and over until our machine runs out of memory resources – an endless loop.

Implementing a recursive function in Excel VBA

To implement our country finding function in Excel VBA, let’s first prepare a test function to ask the user for a country to find, call our recursive function and deliver a proper message to the user:

Sub GetCountry()

    Dim strCountry As String

    Dim arrCountries() As Variant

    Dim strMessage As String

    arrCountries = ThisWorkbook.Sheets("Countries").Range("CountriesTable[#Data]").Value

    strCountry = InputBox("What is your country?", "Country Selection")

    If (strCountry <> vbNullString) Then

        If (DoesCountryExists(arrCountries, strCountry)) Then

            strMessage = "You are from a real country!"

        Else

            strMessage = "You are from another planet I don't know"

        End If

    Else

        strMessage = "Don't know what to do with an empty country..."

    End If

    MsgBox strMessage, vbOKOnly + vbInformation, "Country Search Results"

End Sub

Now we are ready to implement our recursive function, reflecting the algorithm we outlined above.

The act of cutting the list (array) in half is achieved by way of bounding half of the array within a starting index and an ending index.

For example, in a list of 100 countries, if our next iteration half is the first (“left”) half, we pass the index of 1 (“from”) and the index of 50 (“to”) to our function.

Two zeroes (“0”) indexes (the default values for the bounding indices if omitted in the call) indicates the first call to the function. In this case, the initial bounds are set to the natural bounds of the full array.

Function DoesCountryExists(ByRef arrCountries() As Variant, strCountry As String, _

            Optional iFrom As Long = 0, Optional iTo As Long = 0) As Boolean

'Returns True if strCountry is found in arrCountries.

    Dim iMid As Long

    If (iFrom + iTo) = 0 Then

        iFrom = LBound(arrCountries, 1)

        iTo = UBound(arrCountries, 1)

    End If

    If (iFrom > iTo) Then Exit Function

    iMid = Int((iTo - iFrom) / 2 + iFrom)

    If (arrCountries(iMid, 1) = strCountry) Then

        DoesCountryExists = True

        Exit Function

    End If

    If (arrCountries(iMid, 1) > strCountry) Then

        DoesCountryExists = _

            DoesCountryExists(arrCountries, strCountry, iFrom, iMid - 1)

    Else

        DoesCountryExists = _

            DoesCountryExists(arrCountries, strCountry, iMid + 1, iTo)

    End If

End Function

As you can see, I take care to secure an ending condition for all possible scenarios. The ultimate ending condition is when the broomstick becomes as small as can possibly be – our two ever-getting-closer indexes make contact (the gap between them is eliminated). We have also another condition – the essence of our function – when our country is found.

How does a recursive function work and what to be aware of?

Every call to a function allocates memory space for its variables and for a little “housekeeping”. We say that the memory block allocated to a called function is pushed into the memory stack.

Recursive calls, therefore, adds to the stack upon every iteration call.

Unlike non-recursive calls for functions in which memory is released quickly as function calls terminate, recursive “chain” of calls consume accumulated memory blocks in the stack that are not released until the stop event “back-fires” the call-chain and releases the stack in reverse order.

As the terminating function call hits the stop event, its calling function resumes as usual with the statement following the recursive call. When that function call ends, its parent calling function resumes execution in a similar way – all the way back until the complete “chain” is released.

When opting for a recursive function, consider the “broomstick” effect – the task at hand that begs a recursive approach, against possible memory toll for its execution.

Speaking of recursive functions, you are now asked to share this Blog post recursively with other friends and colleagues – let the stop event be an outreach of all Excel enthusiasts out there!