Benut de kracht van recursie
Door Joris Bakker en Wijnand Gritter
Recursie is een zeer krachtige techniek, die complexe problemen eenvoudig kan oplossen en kan het bovendien omgaan met elke grootte van een probleem. Binnen DataWeave heb je bijvoorbeeld veel te maken met data in allerlei vormen en maten. Doormiddel van recursieve functies is het mogelijk om ongeacht hoe de data eruit ziet bepaalde acties erop uit te voeren. Stel je wilt een privacy filter functie maken, waar je een object in kan stoppen en dat vooraf bepaalde velden anoniem gemaakt worden. Dan wil je niet voor elk verschillend object een andere functie maken, maar een functie die met alle objecten overweg kan. Hiervoor kan recursie gebruikt worden om recursief door een object te lopen en zo alle velden die anoniem moeten worden gemaakt aan te passen. Zo is het dus mogelijk om een functie te maken die met elk object kan omgaan en hier alle velden die worden meegegeven anoniem maakt of versleutelt de data.
Data:
{
"message": "Hello world!",
"personalInformation": {
"name": "Max",
"bsm": "123456789",
"address": {
"street": "edisonbaan",
"number": "15"
}
}
}DataWeave:
%dw 2.0
output application/jsonvar fields = [
"name",
"bsm",
"street"
]
fun privacyFilter(obj: Object, privateFields: Array): Object = do {
var keys = keysOf(obj)
---
{(keys map((key) ->
if(obj[key] is Object)
// Further explores the underlying object of the current key.
(key): privacyFilter({(obj.*'$(key)')}, privateFields)
else
// Returns a key: value pair.
if(privateFields contains key as String)
(key): "Anoniem of encrypted data"
else
(key): obj[key]
))}
}
---
privacyFilter(payload, fields)
Resultaat:
{
"message": "Hello world!",
"personalInformation": {
"name": "Anoniem of encrypted data",
"bsm": "Anoniem of encrypted data",
"address": {
"street": "Anoniem of encrypted data",
"number": "15"
}
}
}Nu we een voorbeeld hebben gezien van een probleem en hoe deze met recursiviteit kan worden opgelost zullen we dieper ingaan op hoe het werkt en hoe je het kan gebruiken. Bij recursie los je een probleem op door eerst kleinere onderdelen van het probleem op te lossen, wat uiteindelijk leidt tot het oplossen van het initiële vraag stuk. Dit is een methode die veel gebruikt wordt binnen programmeren en het stelt je in staat complexe problemen op te lossen door deze op te breken in kleinere “sub” problemen die eenvoudiger zijn om op te lossen.
Neem bijvoorbeeld de drie situaties met dominostenen hierboven; Het doel is dat de nde domino steen om valt. De eerste domino steen wordt altijd omgegooid, hier begint het, de base case.
1. Als n een is weten we dus dan de nste domino steen wordt omgegooid.
2. Als n twee is weten we dat deze omvalt als n — 1 omvalt, ofwel als de eerste domino omvalt en aangezien dit de base case is weten dat deze omvalt, dus de nste domino steen zal omvallen.
3. Als n elf is weten we dat deze omvalt als n — 1 omvalt, maar om te weten of n — 1 omvalt moet je weten of n — 2 omvalt, enz. tot je bij n — 10 bent, waarvan je weet dat hij omvalt. Vervolgens kan je weer terug werken, aangezien n — 10 omvalt, valt ook n — 9, n — 8, …, n — 2, n — 1 waaruit vervolgens resulteert dat de nste domino ook omvalt.
Strategie voor het recursief oplossen van een probleem
- Definieer een “base case”, de kleinste/ eenvoudigste versie van het probleem en noteer hiervan de oplossing.
- Definieer een methode hoe je de oplossing van een kleiner probleem kan gebruiken om een huidig probleem op te lossen
- Combineer vervolgens deze twee stappen om tot een volledig recursieve functie te komen.
Als je met recursie werkt is het belangrijk om met de volgende dingen rekening te houden
- Je moet altijd een stop conditie hebben en bij het herhaaldelijk maken van recursieve call moet deze convergeren naar de stop conditie
- Als je een correcte structuur hebt, dus als je:
1. een probleem kan oplossen met de oplossing van een kleinere versie van het probleem
2. een correcte base case hebt
dan doet recursie de rest, dit wordt ook wel de “recursive leap of faith” genoemd. Je hoeft je dus niet druk te maken over de tussenliggende stappen die worden uitgevoerd.
Faculteit
Om een simpel voorbeeld te geven van recursie, gaan we n faculteit berekenen op een recursieve methode. n faculteit, ook wel n! is een wiskundig concept, waarbij n een positief heel getal is en van 1 t/m n met elkaar wordt vermenigvuldigd, bijvoorbeeld 5! = 1 x 2 x 3 x 4 x 5 dus 5! = 120. Dit zou je ook kunnen opschrijven als 5 x 4!, ofwel n! = n x (n — 1)!, als je dit herhaald krijg je het volgende:
Om recursie te laten werken zijn er drie condities waar aan voldaan moet worden.
1. De oplossing van de “base case” moet bekend zijn, dit is de oplossing van het kleinste probleem.
2. Ga er vanuit dat het geval (n — 1) werkt.
3. Laat zien dat het voor n werkt als je (n — 1) gebruikt.
In dit geval is de base case dus als n gelijk is aan 1 en om het probleem kleiner te maken weten we dat n! = n x (n — 1)!. Als we ervan uit gaan dat (n — 1) werkt krijgen we de volgende oplossing:
%dw 2.0
output application/json
fun factorial(n) =
if(n > 1)
// n! = n x (n – 1)!
n * factorial(n - 1)
else
// Base case
1
---
factorial(5) // resultaat 120De torens van Hanoi
Een ander probleem wat op een recursieve manier kan worden opgelost is de torens van Hanoi. Hier heb je drie torens, waar schijven met verschillende diameters op liggen. Er zijn twee regels voor dit probleem:
1. Er mag slechts 1 schijf tegelijk worden verplaatst.
2. Een grotere schijf mag nooit op een kleinere geplaatst worden.
Het doel is om de complete toren van schijven te verplaatsen naar een andere toren.
Om dit recursief op te lossen moeten we dus weer de nodige stappen voor recursie nagaan. Laten we beginnen wij het definiëren van een base case. De simpelste versie van het probleem is als er een schijf is, deze kan je dan simpelweg van een toren naar de andere toren verplaatsen.
Dan de volgende stap, kunnen we een grotere versie van het probleem opknippen naar een kleinere versie van het probleem? Ja, dit kan door het volgende te zeggen: De drie torens noemen we even A, B en C. Bij het verplaatsen van n schijven van A naar C, doen n — 1 schijven verplaatsen van A naar B, dan verplaatsen we de nste schijf van A naar C en verplaatsen we de n — 1 schijven van B naar C. Na deze stappen zullen alle schijven van A naar C verplaatst zijn.
De laatste stap is de “recursive leap of faith”, hier gaan we ervan uit dat om n — 1 schijven van A naar B te verplaatsen we simpelweg n — 2 schijven van A naar C kunnen verplaatsen, dan de n — 1ste schijf van A naar B en dan de n — 2 schijven van C naar B. Dit proces wordt dan herhaalt tot de base case, waar de oplossing van bekend is. Vertaald in DataWeave ziet dat er als volgt uit:
%dw 2.0
output text
fun hanoi(n, start, end) =
if(n == 0)
""
else do{
var other = 6 - (start + end)
---
hanoi(n - 1, start, other) ++ "move: $(start) -> $(end)\n" ++ hanoi(n - 1, other, end)
}---
hanoi(3, 1, 2)
Resultaat:
move: 1 -> 2
move: 1 -> 3
move: 2 -> 3
move: 1 -> 2
move: 3 -> 1
move: 3 -> 2
move: 1 -> 2Recursie op de achtergrond
Op de achtergrond wordt een stack gebruikt, dit is een abstracte data structuur die gebaseerd is op Last In First Out (LIFO). Dit houdt in dat het laatste element wat op de stack wordt gezet, de eerste zal zijn die eraf gaat. Hiermee wordt de volgorde van de recursieve calls te volgen. Als een functie wordt aangeroepen wordt deze namelijk op de stack gezet en als deze een resultaat terug geeft wordt deze van de stack af gehaald (zoals te zien is bij het aanroepen van de factorial functie).
Bij het gebruik van recursieve functie zal je vroeg of laat een error tegenkomen genaamd: stack overflow. Dit betekent dat de stack letterlijk vol is en er niks meer bij kan. De oorzaak hiervan is meestal een incorrecte basecase, de recursie gaat tot in de oneindigheid door, of als de recursie te diep gaat (zichzelf te vaak aanroept waardoor de stack het niet meer kan volgen).
Praktische DataWeave recursie toepassing
Om nog een voorbeeld van een praktische DataWeave functie te geven kijken we naar de merge object functie. Deze functie kan twee objecten volledig samenvoegen, dit houdt in dat de twee objecten tot en met n diep met elkaar worden samengevoegd, waar het “mainObject” leidend is bij duplicaten. Dit verschilt met de standaard functie binnen DataWeave voor het samenvoegen van objecten, namelijk de functie mergeWith. Deze functie voegt een object enkel op de oppervlakte samen. Stel we hebben twee objecten:
Object 1:
{
"location": {
"preferredDays": [
{
"day": "MONDAY",
"partOfDay": "MORNING"}
],
"address": {
"country": "Netherlands",
"city": "Utrecht"
}
}
}
object 2:
{
"location": {
"preferredDays": [
{
"day": "MONDAY",
"partOfDay": "AFTERNOON"
},
{
"day": "TUESDAY",
"partOfDay": "MORNING"}
],
"address": {
"houseNumber": "15",
"postalCode": "3439 MN",
"street": "Edisonbaan"
}
}
}
Bij het gebruik van de mergeWith functie krijg je het onderstaande resultaat. Dit voegt dus onderliggende objecten niet met elkaar samen, zoals address.
%dw 2.0
output application/json
import mergeWith from dw::core::Objects
---
mergeWith(object1, object2)Resultaat:
{
"location": {
"preferredDays": [
{
"day": "MONDAY",
"partOfDay": "AFTERNOON"
},
{
"day": "TUESDAY",
"partOfDay": "MORNING"
}
],
"address": {
"houseNumber": "15",
"postalCode": "3439 MN",
"street": "Edisonbaan"
}
}
}Bij het gebruik van de mergeObject functie wordt tot en met n diep objecten samengevoegd, zoals te zien is in het onderstaande voorbeeld.
%dw 2.0
output application/json
/* Recursively goes through an entire object. Merges duplicate keys together.
* Input params:
* - mainObject: Contains the truth (in case of duplicate fields the main object is leading.)
* - subObject: Object to be merged into the main object.
* Output: Single object where duplicate keys are merged into one.
*/
fun mergeObject(mainObject: Object, subObject: Object = {}): Object = do {
// Initial call combines objects, further calls just take the mainObject.
var combinedObject = if(isEmpty(subObject)) mainObject else mainObject ++ subObject
var keys = keysOf(combinedObject)
---
{(keys map((key) ->
if(combinedObject[key] is Object)
// Further merges the underlying object of the current key.
(key): mergeObject({(combinedObject.*'$(key)')})
else if(combinedObject[key] is Array)
// Returns all the unique entries in an array of both objects.
(key): flatten(combinedObject.*'$(key)') distinctBy(value) -> value
else
// Returns a key: value pair.
(key): combinedObject[key]
// Leaves each object with unique keys
))} distinctBy(value, key) -> key
}
---
mergeObject(object1, object2)Resultaat:
{
"location": {
"preferredDays": [
{
"day": "MONDAY",
"partOfDay": "MORNING"
},
{
"day": "MONDAY",
"partOfDay": "AFTERNOON"
},
{
"day": "TUESDAY",
"partOfDay": "MORNING"
}
],
"address": {
"country": "Netherlands",
"city": "Utrecht",
"houseNumber": "15",
"postalCode": "3439 MN",
"street": "Edisonbaan"
}
}
}Gevaren en beperkingen van recursie
Alhoewel je veel problemen kan oplossen, is dit niet altijd mogelijk of even makkelijk. Aangezien je een base case moet kunnen definiëren en ook een probleem moet kunnen verkleinen in sub problemen, zodat het altijd convergeert naar de base case. Naarmate een probleem complexer wordt, kan een recursieve functie ook zeer lastig te debuggen zijn.
Verder heb je te maken met beperkingen zoals een maximum aan recursieve iteraties, bij DataWeave is dit 256 keer. Of dat de data niet meer op de stack past, waardoor je een stack overflow krijgt.
Ook is het goed om rekening te houden met het feit dat recursie voor veel een complex onderwerp is en dus altijd goed gedocumenteerd moet worden om situaties te voorkomen dat processen of functies onbegrijpelijk zijn voor mensen die er nog niet bekend mee zijn.
