Twee jaar geleden heb ik in dit artikel (Recursieve Custom Functions maken) een methode getoond waarmee je stapsgewijs een CF zou kunnen maken. Het voorbeeld in dat artikel was zogenaamde “kop-recursie” of in het engels “head-recursion”.
In dat artikel heb ik de opmerking gemaakt dat over het verschil tussen kop- en staart-recursie een apart artikel zou kunnen worden geschreven. Hieronder probeer duidelijk te maken wat de verschillen zijn en stel een paar functies beschikbaar die je zelf als basis voor je eigen CF’s zou kunnen gebruiken.
Kop-recursie
Het kenmerk van “kop-recursie” is dat je met zo’n functie je data bewerkt en vervolgens binnen deze functie, deze zichzelf weer laat aanroepen, totdat er aan een bepaalde voorwaarde wordt voldaan. De functie geeft dan in een keer zijn resultaat.
Inverteer
Gebruik je een kop-recursieve-functie (inverteer) om bijvoorbeeld tekst ( “ABCD” ) om te keren dan werkt dit in de uitvoering ongeveer zo:
Inverteer ( “ABCD” ) + Inverteer ( “ABC” ) + Inverteer ( “AB” ) + Inverteer ( “A” ) en daarna krijg je het resultaat terug als “DCBA”
Na iedere iteratie van de functie worden het resultaat en de volgende iteratie op dezelfde plek in het geheugen verwerkt. De allereerste iteratie is meteen het eerste resultaat van de functie en met de rest wordt op dezelfde plek de functie weer aangeroepen. Aan het einde wanneer en geen data meer is om te verwerken wordt het resultaat in één keer teruggegeven.
De inverteerfunctie met kop-recursie zie er als volgt uit:
Let ( [
l = Length ( Data ) ;
c = Right ( Data ; 1 ) ;
Data = Left ( Data ; l – 1 )
] ;
Case ( l > 0 ; c & Reverse_Head ( Data ) )
)
(bij kopiëren vanuit je browser zullen mintekens (-) en quotes ( “” ) verkeerd worden geplakt, vervang die tekens na het plakken voor de juiste)
Staart-recursie
Dit artikel wil ik graag de verschillen tussen kop- en staart-recursie laten zien, dus bekijken we ook hoe een staart-recursieve-functie (inverteer) met dezelfde tekst (“ ABCD” ) zou omgaan en dat gebeurt ongeveer zo:
Inverteer ( “ABCD” ; “” ) , Inverteer ( “ABC” , “D” ) , Inverteer ( “AB” , “DC” ) , Inverteer ( “A” , “DCB” )
Na iedere iteratie wordt het resultaat opgeteld met het oude resultaat op een gereserveerde plek in het geheugen gezet en de functie wordt opnieuw aangeroepen met slechts 2 waarden. Aan het einde wordt er door de eerste variabele niet meer voldaan aan de voorwaarden en kan het resultaat worden opgepikt uit de gereserveerde plaats in het geheugen.
De inverteerfunctie met staart-recursie zie er als volgt uit:
Let ( [
l = Length ( Data ) ;
c = Right ( Data ; 1 ) ;
Data = Left ( Data ; l – 1 )
] ;
Case ( l > 1 ; Reverse_Tail ( Data ; Result & c ) ; Result & c )
)
(bij kopiëren vanuit je browser zullen mintekens (-) en quotes ( “” ) verkeerd worden geplakt, vervang die tekens na het plakken voor de juiste)
Verschillen
Om het verschil in kop- en staart-recursie te verduidelijken heb ik nog een iets eenvoudiger functie gemaakt en ook deze in twee versies gebouwd. Deze functie maakt een lijst (array) van getallen totdat de ingestelde waarde is bereikt.
De eerste is weer met kop-recursie:
Let ( [
result = Data – 1
] ;
Case ( Data > 0 ; List ( Array_Head ( result ) ; Data ) )
)
Nummer twee is met staart-recursie:
Let ( [
theList = List ( Data ; Result ) ;
Data = Data – 1
] ;
Case ( Data > 0 ; Array_Tail ( Data ; theList ) ; TheList )
)
(bij kopiëren vanuit je browser zullen mintekens (-) en quotes ( “” ) verkeerd worden geplakt, vervang die tekens na het plakken voor de juiste)
Opmerkingen
De werking van deze functies mag je zelf onderzoeken in het voorbeeld dat je hieronder kan downloaden. Er zijn wel een paar opmerkingen die ik wil maken over de formules. Het inverteren van tekst kost beduidend meer tijd dan een lijst met getallen genereren, ca 2,5 maal zoveel.
Bij staart-recursie heb je dus altijd één extra iteratie t.o.v. kop-recursie, dus dat kost wat extra processortijd. Bij iedere doorgang moet het resultaat van de vorige doorgang uit het geheugen worden opgehaald en ook dat kost een beetje processortijd.
Altijd kop-recursie?
Dus zouden we dan altijd kop-recursie moeten gebruiken? Nee beslist niet, want schijn bedriegt hier. Je zou verwachten dat kop-recursie het snelste werkt, maar uit de voorbeelden in het voorbeeld-bestand zal blijken dat dit niet waar is.
Ik heb de voorbeelden in dat bestand getest met FMPA 15.0.3.305 op MacOS 10.12.5 (mbp2016, 2.9GHz i7-6920HQ) en op Windows 8.1 (HP8570, 3.0GHz i7-3540M)
Snelheidsmetingen
Hieronder zie je twee grafieken, een met de meetresultaten met de investering van een tekst en een volgende met de productie van een lijst. Daarnaast zie je in beide grafieken de resultaten gemeten met MacOS respectievelijk Windows. Tenslotte heb ik met 4 major-versies van FileMaker de tests uitgevoerd.
Je kan in deze grafieken mooi zien dat de Mac met zijn 6e generatie i7 maar Een heel klein beetje sneller is dan de PC met zijn 3e generatie i7, geen reden dus om de machine met de allernieuwste processor aan te schaffen.
Wat ook opvalt is dat staart-recursie eigenlijk altijd sneller is dan kop-recursie en dat is eigenlijk tegen mijn verwachting in en ook tegen wat mij ooit op een cursus is verteld. Kop-recursie zou de snelste methode zijn en mij grafieken tonen dat dit niet waar is.
FileMaker Go
Ik heb dit bestand, met zijn functies ook even op een iPad Air uit 2014 getest. Daarop zie je hetzelfde beeld, staart-recursie is sneller dan kop-recursie, alleen heeft de iPad voor de calculatie ongeveer 8 tot 10 mal zoveel tijd nodig. De tests op iPad heb ik niet gelogd en ik heb die resultaten daarom niet in de grafieken opgenomen.
Download
Hoe dan ook, ik vind dat ik wel weer genoeg heb zitten zemelen en wat me nu nog rest is jullie de download beschikbaar stellen, zodat jullie zelf kunnen gaan testen en vanaf nu het verschil tussen kop- en straat-recursie kennen.
Recursion