The A-Z of FileMaker: R is for Recursion

The trite definition of recursion is “see recursion”. And further, that to understand recursion, one must first understand recursion!

According to the online Dictionary of Technical Terms, 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.”

FileMaker custom functions

In FileMaker programming, recursion is possible when creating custom functions. The definition of a recursive custom function will include the function itself. So the function is said to “call” itself when it evaluates an expression.

Care must be taken when designing recursive custom functions – they will need an exit point. If there is no valid exit point, the function will keep calling itself infinitely or until all memory is consumed. FileMaker custom functions will only allow a specified number of recursions until they exit and return ?.

Why do I need recursion?

Good question. There are some problems that require the same process to be repeated an indeterminate number of times.

A simple mathematical concept is the factorial – denoted by n! – the product of all positive integers less than or equal to n:

5! = 5 x 4 x 3 x 2 x 1 = 120

This could also be considered as

5 x (5 - 1) x (5 - 2) x (5 - 3) x (5 - 4)
n . (n - 1) . (n - 2) ... 2 . 1

The generalised process is:

n! = n . (n - 1)!

The factorial process takes the first number and multiplies it by the factorial of itself minus 1 until the last multiplier is 1. Clearly, the reason this needs recursion is that there will be the same number of multiplications as the value of the initial number.

How do we write a custom function in FileMaker Pro?

Well, first you need FileMaker Pro Advanced. This will provide access to File > Manage > Custom Functions…. When you create a new custom function, you will use the dialog box:

edit custom function

You give your custom function a name, create as many parameters as you need and define the function.

(As it happens, FileMaker Pro already provides a function called Factorial so you cannot use that name here.)

So here is my factorial custom function, Factorial_c:

factorial custom function

There is one parameter – number. Looking at the function definition:

Case ( number < 0; "?"; 
     number = 0; 1;  
     number > 1; number * Factorial_c ( number - 1); 
     1 )

It uses a Case function to test for multiple outcomes. The first test returns an error (?) if the number provided is negative.

The second test provides the special case where 0! = 1.

The third test is where the recursion occurs – for any number greater than 1, it multiplies that number by the factorial of the number one less than itself. Highlighted in bold is where the function calls itself.

The function has three exit points – when the number is less than zero, zero, or one. Otherwise, it will call itself.

Note: for simplicity, this function does not explicitly account for non-integer numbers.

So if the number passed was 4, the process goes:

Expression:   Factorial_c ( 4 )
First pass:   4 * Factorial_c ( 4 - 1)
Second pass:  4 * 3 * Factorial_c ( 3 - 1)
Third pass:   4 * 3 * 2 * Factorial_c ( 2 - 1)
Fourth pass:  4 * 3 * 2 * 1
Exit Result:  24

Is there a more practical example?

If you are not mathematical, well done for hanging in there! For your reward, here is a more practical example of recursion.

There may be cases where you need to create an acronym of a phrase. For example, Australian Computer Society would return ACS.

So we create a custom function called Acronym ( text ) with one parameter, text, and defined as:

Upper ( Left ( text; 1) ) &
If ( WordCount (text) > 1;
   Acronym ( RightWords (text; WordCount(text)-1) )

The recursion (highlighted in bold) simply takes the current string less the first word (by getting the all the words from the right except the first one).

The custom function calls itself whenever the word count is more than one. The exit point is when the text has one word (or less).

So if the text passed was “new south wales”, the process goes:

Expression:   Acronym ( "new south wales" )
First pass:   "N" & Acronym ( "south wales" )
Second pass:  "NS" & Acronym ( "wales" )
Exit Result:  "NSW"

To reiterate, this recursive custom function will work for a string of any* number of words. That is the beauty of recursion in the efficiency of the code.

Bonus points

For bonus points, it would be useful if the acronym ignored certain words like and, of, &, etc. For example, the Australian Bureau of Statistics should be ABS rather than ABOS.

How could you modify the function to ignore defined words? Perhaps using the Substitute function?

* Recursive limits in FileMaker

As mentioned above, the FileMaker calculation engine will allow a certain number of recursions before exiting with an error (?). For standard recursion, this limit is 10,000. For the special case of tail recursion, the limit is 50,000.

So what is standard recursion? It is when the calculation engine needs to preserve a previous result (in a stack) for each recursion. Both examples above do this. For the acronym function, the calculation engine needs to remember all the previous letters while it runs the next acronym recursion on the shorter text string. When the exit point is reached, the result is returned from the stack.

Then what is tail recursion? This is when a stack is not used because the entire result is passed to the next recursion. Each recursion is complete in its own right.

Here is an example of tail recursion for the Acronym function. The structure of the function is Acronym_t ( text ; result ). When using the function, the result always starts with a null value (“”). The result passed onto the next recursion is the progressive accumulation of the final result.

If ( WordCount (text) > 1;
   Acronym_t ( RightWords(text;WordCount(text)-1); 
               result & Upper(Left(text;1)) ); 
   result & Upper ( Left ( text; 1) ) 

The process goes:

Expression:   Acronym_t ( "New South Wales"; "" )
First pass:   Acronym_t ( "South Wales"; "N" )
Second pass:  Acronym_t ( "Wales"; "NS" )
Result:       "NSW"

Creating tail recursive custom functions requires a little more thought and effort. However, it is sometimes important to be able to exceed the standard 10,000 pass limit.

But I still don’t understand recursion!

Well then you need to read this article – The A-Z of FileMaker: R is for Recursion. See what I did there? :p

One Response

Leave a Reply

Your email address will not be published. Required fields are marked *