Recursie toegepast

Hoe je recursie in een PHP script kunt toepassen zal ik uitleggen aan de hand van een wiskundig principe. De wiskunde kent namelijk het verschijnsel faculteit dat zich uitermate goed leent om recursie uit te leggen.

De faculteit van een getal, aangegeven door een ! achter het getal (vb. 6!), is het resultaat van de vermenigvuldiging van dit getal met al zijn voorgangers.

De uitkomst van 6! is dus gelijk aan 720. De enige uitzondering op deze regel is 0!, dit is namelijk gelijk gesteld aan 1.

Het uitrekenen van de faculteit van een getal kunnen we zowel op een iteratieve als recursieve manier doen. Laten we beginnen met de iteratieve functie.

Voorbeeld 3: Berekenen van de faculteit op een iteratieve manier

In dit voorbeeld hebben we gebruik gemaakt van een while loop om door de reeks getallen heen te lopen en de waarden overeenkomstig te vermenigvuldigen.

Laten we eens kijken wat deze functie precies doet door een echo van de twee variabelen toe te voegen.

Voorbeeld 4: De iteratieve functie met echo van variabelen

Het resultaat is dan als volgt:


Een alternatieve manier is het gebruik van een recursieve functie. Herinner je nog even: recursie betreft alles dat op een bepaald moment naar zichzelf refereert. In een PHP script ziet dat er als volgt uit:

Voorbeeld 5: Berekenen van de faculteit op een recursieve manier

Deze functie ziet er al een stuk eleganter uit, maar wat doen we hier nu precies? In plaats van de variabele $uitkomst gebruiken we nu enkel de variabele $getal. En in plaats van het bijhouden van een teller, zoals $i in voorbeeld 1 en 2, houden we bij simpele recursie alleen de bewerking op een enkele variabele in de gaten.

Het if-statement in dit script dient twee doelen. Het eerste is natuurlijk het retourneren van de waarde 1 als je faculteit(0) of faculteit(1) ergens in je code aanroept.

Het tweede doel van dit statement is echter veel belangrijker. Het betreft de zogenaamde end condition van de recursie. In de iteratieve while loop is de end condition het moment waarop $getal niet langer groter is dan 0, hier is dat als $getal kleiner wordt dan 2.

Om ook hier een duidelijk beeld te krijgen van wat deze recursieve functie nu eigenlijk doet, voegen we een echo toe aan de functie:

Voorbeeld 6: De recursieve functie met echo

De uitkomst is dan als volgt:

We zien dat het oplopende resultaat uit het iteratieve script hier helemaal ontbreekt. Hoe is het dan toch mogelijk dat het script de goede uitkomst geeft?

In plaats van het resultaat telkens te vermenigvuldigen met een bepaalde waarde, vermenigvuldigen we nu het getal met de faculteit van het getal-1. Het bewijs dat dat klopt:

Het is dus de vermenigvuldiging die de resultaten van onze code verzamelt (engels: to aggregate), daarom wordt de vermenigvuldigings operator (*) ook wel de aggregator genoemd.

De laatste regel van de recursieve functie is nu dus eigenlijk als volgt:

Dit in tegenstelling tot de laatste regel van de iteratieve functie:


Je merkt dat het gebruik van recursie een andere manier van denken verlangt. Zodra je hier aan gewend bent, zul je de voordelen die recursie soms met zich meebrengt inzien.

De functie die we nu gebruikt hebben is eigenlijk nog niet helemaal af. De functie zal namelijk de fout in gaan zodra er een negatieve waarde of een niet-integer als parameter meegegeven wordt. Om dat te voorkomen voegen we nog een paar regels code toe.

Voorbeeld 7: De complete recursieve functie met foutafhandeling


Performanceverschillen
Het verschil in performance tussen deze twee functies op deze pagina is ook iets om aandacht aan te besteden. Over het algemeen zullen recursieve functies altijd langzamer zijn dan iteratieve functies. Dit komt omdat bij een recursieve functie elke keer weer een nieuwe functie aangeroepen wordt, dit kost relatief veel tijd.

Vooral bij lichte functies zoals in dit voorbeeld kan het snelheidsverschil wel oplopen tot 50%. In de praktijk merk je hier echter niets van aangezien de tijd die het kost om de functie uit te voeren heel kort is, namelijk rond de 0.00001 seconden. Naarmate de functies groter worden, zal het verschil in performance alleen maar afnemen. De overhead die ontstaat bij het aanroepen van een functie zal dan een kleinere invloed hebben op de totale performance van de recursieve functie.

In het geval van het berekenen van de faculteit is het waarschijnlijk verstandiger om de iteratieve functie te gebruiken. Het bepalen van de faculteit van een groot getal met een recursieve functie levert namelijk een veel grotere belasting. Voor het berekenen van bijvoorbeeld 100! zouden 101 instanties van de recursieve functie aangemaakt moeten worden om tot een resultaat komen. Een iteratieve functie zou in dit geval dus geschikter zijn aangezien deze maar een keer aangeroepen wordt en het resultaat met een loop berekend.

« Lees de omschrijving en reacties