NickLightbody

Understanding a tail recursive FileMaker Custom Function.

Discussion created by NickLightbody on Sep 9, 2015
Latest reply on Oct 20, 2016 by destroid

This is just for any non-mathematicians out there for whom recursion is not second nature. Filemaker has offered recursion since 2007 and this is the first time I felt I understood tail recursion, so this may be helpful for a few other former Arts students like me.

 

Sometimes, when doing encryption it is useful to shuffle sets of characters, for example when creating substitution keys.

In the past I have just written simple scripts in Filemaker to do this because, although I have used and adapted recursive custom functions several times, I have never really understood the difference between a normal recursive function and a tail recursive function.

 

This is important because the normal form is limited to 10,000 cycles in FileMaker but the tail form can run to 50,000 cycles.

 

The other day I had to create a shuffle routine within a database definition hence, as I couldn't script it, I had to work out how to create a suitable recursive function.

 

A quick search found an erudite explanation by RayCologon from 2006 which explained the difference...

 

http://www.filemakertoday.com/com/archive/index.php?t-9986.html

 

As ever, thank you to Ray for his clear explanation - how does he know all these things!

 

Here is the key quote: "Tail recursion has nothing to do with whether you 'loop' backwards from the end or forward from the beginning. What matters is how values accumulate and are passed down through successive function calls (and in particular, whether the function must feed values via a temporary memory 'stack' in the course of its operation). In the simplest terms, recursive functions that are constructed so that they don't depend on the stack are tail recursive."

 

In other words, it is tail recursive if you pass all the results of the expression on to the next iteration as parameters without creating local variables.

 

With that understood it was fairly simple to construct my shuffle function so that it output the shuffled string and a control value, so the control value reduced by 1 on each call and the result of the expression no longer called itself when the control had reduced to zero.

 

Here it is.

 

/*

xShuffle

 

FileMaker Custom Function - Tail Recursive

By Nick Lightbody September 7th, 2015

Purpose: To shuffle a string

Syntax: xShuffle ( string; control )

Input: string - to be shuffled

Input: control - number of times xShuffle should call itself i.e. to control the extent of the shuffle

*/

 

 

Let([

s=string;

c=Case(control<1;1;control);

L=Length(s);

r=Int(L * Middle(GetAsText(Random);3;2)/100);

x=Middle(s;r;1);

y=Substitute (s;x;"") & x;

c=c-1

];

Case( c>0 ; xShuffle( y ; c ) ; y )

)

 

Do please suggest how this can be improved - note that the control parameter is required since otherwise it can't be passed on to the next call - I had of course tried this as fully automatic based on the length of the string - which doesn't work.

 

Cheers

Nick Lightbody

September 9th 2015

Outcomes