A Variable Way of Writing Recursion

Introduction

Recursion can be a complex and often intimidating part of FileMaker development for many. Wrapping your head around what it is and how it works is something even a seasoned developer can struggle with from time to time - just ask anyone who has sat the certification exam!

In this article we start by offering a brief introduction as to what recursion is by way of a simple example, before digging into the main reason for this article which is to present an alternative way to write your custom functions that is much simpler and easier to understand and follow.  If you are already caught up on what recursion is and how it works, then feel free to skip down this introduction and get stuck into the more interesting stuff further down the article. Otherwise enjoy this introduction to recursion :)

So let's go!

Recursion is really just a loop

Yup, that's about it. We use recursion to simulate a looping construct when required in a calculation. FileMaker has no loop function at this point in time and so we rely on recursion to achieve the same effect. Think of it as being the ugly awkward half brother to a FileMaker scripted loop.  A scripted loop can be used to loop and process records, or values stored within variables among other things. Recursive functions typically are used to loop through a list of values while performing actions on that list. They can also be used to transform values, or build lists of values.

Of course they are used for much more but in the world of FileMaker development most recursive functions you will come across tend to involved processing of multiple values, such as a list.

You write recursive functions using a Custom Function

In FileMaker, we use the Custom Function feature to write recursive custom functions. A custom function is purely a function you entirely declare and write yourself. They need not be recursive, but given we have access to write functions, we can easily write them to be recursive if need be.

You will find custom functions in FileMaker under the "File" menu -  File -> Manage -> Custom Functions.

Writing Custom Functions

Note that in FileMaker Pro 16 and earlier, this feature is only available to users of FileMaker Pro Advanced. While a standard copy of FileMaker Pro can execute a custom function, you cannot write them. With the release of FileMaker Pro 17, there is no longer a separate version of Advanced, and so you can write these functions using FileMaker Pro. You just have to make sure you enable the "Use Advanced Tools" option which is set in the FileMaker Pro preferences.

Okay, so recursion is like a loop... but how? 

Techterms.com has a nice and simple definition of recursion:

Recursion is a process in which a function calls itself as a subroutine. This allows the function to be repeated several times, since it calls itself during its execution. Functions that incorporate recursion are called recursive functions.

The key here is that the function calls itself. Each time a function calls itself again, you can think of it as progressing to the next item - or drawing an analogy to a scripted loop it would be akin to moving on to the next record to process.  If we wanted to loop over a list of 10 items doing something to each, then the function would call itself 9 times (the first time the user calls it, and the other 9 times the function calls itself.).

Another way to look at it is to think of it a bit like the Droste effect. I'm sure you have all seen pictures similar to that below, it is a good way to think about recursion. You can read more about the Droste Effect here.

 A simple example of recursion

 Here we have a simple function _factorial (_integer ).

 When this function is passed a number it will return the product of the integer and all integers below it, ending at the number 1.  For example _factorial (4) will return the result of 24. This is done by multiplying 4 * 3 * 2 * 1.

The function first takes the parameter and makes it an absolute number - purely done to ensure we don't end up with a negative number parameter. 

Recursive functions have an exit condition. This is a check to determine whether recursion is going to end or continue. It's exactly like the "Exit loop If" script step.

Each time the function is called, it will be being passed the next lowest number. The exit condition is when we are passed the number 1.

If we have not yet been passed the value "1", the function will multiply the integer passed by the result of the function called again (with 1 less as its parameter).

If you are still not following, have a look at this graphic:

Here we are showing each row as a subsequent recursive call to the function.  The first time the function is called it is passed the value 4.   The exit condition is checked "is 4 equal to 1?". Because the answer is false, we multiply 4 by the result of a recursive call.  Now imagine repeating this but for the function with the parameter of 3. This is illustrated on row 2. We repeat the exit condition which is still false, and so the result of this call is 3 multiplied by the function call again with the parameter of 2.

Once more we repeat this until row 4 where the exit condition is true - 1 is equal to 1. The result of this is simply to return the number 1.

So the result of 1 is passed back up to row 3 and used as the result. Row 3 is equal to 2 * 3.  This is passed up to row 2.

Row 2's result is 3 * 2 * 1, and this is passed right back up to the first row.  

You can see this in the result column, results of each function call are passed back up the recursive chain to the original function call, and it is here that we can fully evaluate the result.

Clear as mud? Good!  However if you are still struggling, at this point we recommend you download the accompanying example file for this article. You'll find a link at the bottom of the page. The example file includes a step by step guide to following the recursive function along with illustrations. You can also look at the function yourself in the unlocked file, to get a feel for how it works.

Let's take this further using variables

As we have seen, one of the most common ways in which recursion is done, is to process a value at each iteration, and then pass a modified version of the parameter to the subsequent recursive call. This is normally done by removing elements from a list, or maintaining a counter parameter which is incremented with each subsequent call so that each recursive step knows what position in a list it is processing.

Modification of lists such as chopping off values, or obtaining left/right values, can be quite an expensive and time consuming operation when done hundreds of times. Ideally we want to keep any parameter we use in an unmodified state and reference positions within it using a counter, it's a much more efficient way to process.

But what if we don't want to pass counters as parameters, can we do this? Can we use a local variable as a counter? Furthermore how far can we take the usage of local variables to improve readability and simplicity of the function? Turns out we can take it quite far.

The key - variables persist from one recursive call to the next

That's right. You can define a local variable in one recursive call, and the value of that will be accessible to all subsequent recursive calls. This makes them very handy for transferring of information from one call to the next without using function parameters.  Think of them as storage lots that you can place information in to refer to throughout the function.

Now we are going to utilise this fact to show an alternative way to write a more complex function.

It is important to also note however that sometimes the method we'll show is not the best method. Often if recursion is simple enough, then just go with the simplest way to write it. Using variables is a good technique to improve readability for other developers, and can improve performance through minimal list manipulation functions, but go with what works best for you.

Example: _RemoveValues function

(Note you can find all examples from this article in the example file, linked to at the bottom).

Time to take things up a notch. This function is defined as:

_RemoveValues ( _listA ; _listB )

It will take 2 return delimited lists as its parameters. The function is to return all values in _listA which do not exist in _listB.

The way in which the function is written above is a pretty typical style that you might find in a lot of recursive functions.  It begins with the exit condition which is when the first list is empty.

If there are values in _listA to process, it checks if the first value in that list is present in _listB. If so, it keeps it, otherwise it discards it. It does this by either getting the 1st left value from _listA, or the 0th value of _listA (in other words nothing).

To that value, it appends the result of the recursive call, however the parameter to this call is _listA without the left-most value present (as we just processed that one).

You'll note we are using 2 rather costly functions here - LeftValues and RightValues. These are inefficient function calls when dealing with larger lists.   Consider a _listA with a thousand items. We will be doing a thousand recursive calls, however each time we do that recursion we are running the RightValues function to strip out the left-most value, that's a lot of calls !

Now let's look at it rewritten with variables

Here is our alternative approach to writing the same function but this time using local variables and a standardised approach to the functional structure: 

There's quite a lot going on here to talk about. First thing to note is yes there are more lines of code here even without comments included. While there are more lines of code, it actually makes for a more readable function overall, as well as helping to better lay out a  more simplified approach to thinking about recursion. This approach is more like a scripted loop, where you do not need to think as much about the complex nature of recursive calls.

Structurally the function follows this standard layout:

1. A counter is defined, as well as an exit counter value.
2. Use however many variables (both local or within a Let statement) you require to be clear and readable.
3. Use a local variable to maintain your final result value.
4. Define your exit condition. When evaluated to true, clear all used local variables, and return your result value.
5. If exit condition is not met, simply call the function again with the exact same parameters.

One of the key differences here between this and a standard method of recursion is that we don't bother updating passed parameters to the recursive call. They can remain exactly the same -  no modification to them is required. We also do not require a counter parameter - this is maintained through a local variable.

A note about the exit condition and variables

Upon reaching your exit condition, it is highly recommended that you clear all your local variables. This is because if you do not do so, their values will persist in the data viewer after the function finishes. This state is known as the 0 script state, and is a state where local variables can exist if defined outside the scope of a script - such as here in the function. In the interests of tidiness clear them when you're done. One of the reasons why we prefix all of our variables with an underscore when defined in a function is so that we know they were defined from a function. Normal script variables if defined should not be defined with the underscore. This is another way to ensure there is no conflict between variables defined in a function that may not be cleared, and those that get defined in a script.

Defining a counter and exit value

The first step in our function is to establish a counter, and an exit value.  The counter will be incremented each time the function is called in order to track our position in the recursion. The exit counter value tells us when to stop processing. Usually we know when this will be before we begin because it usually corresponds with the size of a list we are processing.

You'll note the first check is whether we have a counter value at all - this will ensure that the very first time the function is called we set an initial counter value of 1.  After that, each subsequent recursive call will see a value in our counter, and so increment it instead of initialising it.

The same goes for our exit variable. On first call it will be empty so we set it to the size of our listA. Subsequent calls we do not modify it. This only needs to be set once.

Defining processing variables

Processing variables help us store values that will be carried from one recursive call to the next. For these we use local variables. If we require variables that need not be transferred from one call to the next, we instead use Let statement variables, whose scope is only that of the current function call.

In our example each successive function call will work with a specific value in our list. We use our counter to tell what value that is, and we use GetValue to obtain it. GetValue is a far more efficient function call than Left/RightValues.

We do our check to see whether our value is in ListB or not, in the same way we did in our earlier function definition.

Finally, we have a result variable - $_return - which we will store what our end result will be. This value persists from one function call to the next.

The exit condition

Here is our exit condition:

The exit condition is almost always the same - it's when our counter reaches our exit value. At this point in time we need to do a couple of things:

1. Clear the local values we defined
2. Store our return value in a Let variable
3. Clear our return variable
4. Return the result

Steps 2 and 3 are a bit of a quirk. Our result is stored in a local variable, but we cannot clear this variable before we return it as a result. To work around this, we store it in a Let variable and return that instead. the Let variable is automatically cleared when the function ends.  Using the Let function allows us to clear all used variables used in a nice concise manner.

And finally, the recursive call

In our recursive function definition, the actual act of recursion is reduced to somewhat of an afterthought. We don't need to think about it, or worry about what we pass it. We just call it.

Pros and Cons of this method

As mentioned earlier, this is an alternative approach to writing a recursive custom function but not to be considered the correct way. There is nothing wrong with writing it however you wish. There are pros and cons with using this method. Some pros are:

• Improved readability - useful if other developers must interpret your code
• Simplicity through closely resembling a scripted loop
• No need to modify parameters passed through each subsequent call
• No need for state-tracking parameters such as counters (done in variables)
• Easy to follow.

Some cons however are:

• You need to clear variables when done
• There is a risk variables could interfere with other processes if not cleared
• No guarantee this is a supported FileMaker feature, no guarantee it won't be deprecated in future.
• Perhaps performance hit through act of using local variables as opposed to purely Let statement? Unsure.
• May not play nice if your recursive function calls itself multiple times within each call (e.g. some sorting functions).

The choice is yours. If this works for you then by all means embrace it and use it. We certainly have. But not all functions are the same and some other approaches to writing them may work better for you. Our aim here is that this method is clear to read and follow and might help developers feel less anxious about writing complex recursive custom functions.

Example file!

As with all of our articles we produce we like to provide a detailed example file to go along with it. It’s not enough to just read how something is done, you should be able to see it in action and explore how it works yourself. Please find attached the example file below.

Click to download example file!