Recursieve functies in PHP

Recursie is en blijft een onderwerp dat veel mensen moeilijk te begrijpen vinden. Velen hebben nog nooit van recursie gehoord, anderen zijn er wel eens mee in aanraking gekomen maar begrijpen het niet echt en weer anderen snappen het principe van recursie en passen het regelmatig toe. Van deze drie groepen zal de laatste groep verreweg de kleinste zijn.

Omdat recursie toch een mooi principe is en in bepaalde gevallen echt een uitkomst kan zijn, zal ik in deze tutorial proberen om een uitleg te geven van wat recursie is en hoe je dit principe toe kunt passen in je PHP scripts.

Benodigde voorkennis
- Basis PHP
- Functies in PHP

Een gangbare definitie van recursie is de volgende:

Recursie is het proces dat een procedure ondergaat als een onderdeel van deze procedure het opnieuw uitvoeren van de gehele zelfde procedure betreft.

Met andere woorden, recursie betreft alles dat op een bepaald moment naar zichzelf refereert.

Recursie vs. Iteratie
Om een beter beeld te krijgen van wat recursie nou precies inhoud, zal ik beginnen met iets dat iedereen al gebruikt in zijn PHP scripts: iteratie.

Iteratie is letterlijk herhaling en de bekendste voorbeelden uit PHP zijn dan ook wel de for en while loops. Iedereen kent ze en iedereen past ze toe.

Voorbeeld 1: Iteratie in een PHP script
<?php
for($i = 0; $i <= 9; $i++)
{
echo $i;
}
?>
Voorbeeld 2: Iteratie in een PHP script (2)
<?php
$i = 0;
while($i <= 9)
{
echo $i;
$i++;
}
?>
Natuurlijk geven beide scriptjes het volgende terug:

0123456789

Beide voorbeelden geven de cijfers van 0 tot 9 op een iteratieve manier.

Eenvoudig gezegd is iteratie dus iets uitvoeren in een loop. Als je nog nooit gehoord hebt van recursie, heb je er waarschijnlijk nog nooit bij stil gestaan dat er ook een alternatieve manier is. Dit komt dan waarschijnlijk omdat het relatief eenvoudig is om dit soort problemen met een loop op te lossen. Recursie daarentegen vereist van PHP programmeurs een andere manier van denken. Je zult er dan ook even een knop voor om moeten zetten en jezelf in het diepe moeten gooien.

Hoewel PHP voornamelijk iteratieve oplossingen gebruikt voor problemen, is het niet alleen mogelijk om recursie te gebruiken maar soms ook gewenst. Verderop in deze tutorial zal ik daar een voorbeeld van geven.

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.

6! = 6 * 5 * 4 * 3 * 2 * 1

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
<?php
function faculteit($getal)
{
$uitkomst = 1;
while($getal > 0)
{
$uitkomst *= $getal;
$getal--;
}
return $uitkomst;
}

echo faculteit(6); // Output: 720
?>
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
<?php
function faculteit($getal)
{
$uitkomst = 1;
while($getal > 0)
{
echo '$uitkomst = '.$uitkomst.', $getal = '.$getal.'<br>';
$uitkomst *= $getal;
$getal--;
}
return $uitkomst;
}
?>
Het resultaat is dan als volgt:

$uitkomst = 1, $getal = 6
$uitkomst = 6, $getal = 5
$uitkomst = 30, $getal = 4
$uitkomst = 120, $getal = 3
$uitkomst = 360, $getal = 2
$uitkomst = 720, $getal = 1
720

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
<?php
function faculteit($getal)
{
if($getal < 2)
{
return 1;
}
else
{
return ($getal * faculteit($getal-1));
}
}

echo faculteit(6); // Output: 720
?>
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
<?php
function faculteit($getal)
{
if($getal < 2)
{
return 1;
}
else
{
echo 'faculteit('.$getal.') = '.$getal.' * faculteit('. ($getal - 1) .') <br>';
return ($getal * faculteit($getal-1));
}
}
?>
De uitkomst is dan als volgt:

faculteit(6) = 6 * faculteit(5)
faculteit(5) = 6 * faculteit(4)
faculteit(4) = 6 * faculteit(3)
faculteit(3) = 6 * faculteit(2)
faculteit(2) = 6 * faculteit(1)
720

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:

6! = 6 * (5 * 4 * 3 * 2 * 1)
5! = 5 * 4 * 3 * 2 * 1

## Dus:
6! = 6 * 5!

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:

return 6 * 5 * 4 * 3 * 2 * 1;

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

return 720;

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
<?php
function faculteit($getal)
{
// Return NULL bij negatieve waarden en niet-integers
if($getal < 0 || !is_int($getal))
{
return NULL;
}

// Berekenen van de faculteit van $getal
if($getal < 2)
{
return 1;
}
else
{
echo 'faculteit('.$getal.') = '.$getal.' * faculteit('. ($getal - 1) .') <br>';
return ($getal * faculteit($getal-1));
}
}
?>

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.

Nu we de basis van recursie behandeld hebben, kunnen we kijken naar een mooier voorbeeld van recursie. Hoewel er sinds PHP 5 enkele functies zijn die het uitlezen van een directory in een keer voor je kunnen doen, zal ik hier een recursieve functie laten zien die dat ook doet.

Het uitlezen van een bepaalde map op zich zal geen probleem zijn. Een combinatie van opendir() en readdir() levert het gewenste resultaat.

Voor de voorbeelden gebruik ik de volgende bestandsstructuur:

gebruikers/
gebruikers/a/
gebruikers/a/arend.txt
gebruikers/a/arjan.txt
gebruikers/gebruikers.txt
gebruikers/p/
gebruikers/p/eigenschappen/
gebruikers/p/eigenschappen/file.txt
gebruikers/p/piet.txt

Voorbeeld 8: Uitlezen van een map
<?php
function leesUit($path)
{
if($dir = @opendir($path))
{
while(($file = readdir($dir)) !== FALSE)
{
if($file != '.' && $file != '..')
{
$output[] = $file;
}
}
closedir($dir);
}
return isset($output) ? $output : FALSE;
}

$map = 'gebruikers';
echo '<pre>';
print_r(leesUit($map));
echo '</pre>';
?>
De functie kijkt allereerst of het opgegeven pad te openen is als directory. Zoja, dan wordt de readdir() functie gebruikt om de map uit te lezen en de bestanden in de $output array te zetten. Vervolgens wordt de directory weer gesloten en wordt bepaald wat er geretourneerd moet worden. Als de functie succesvol verlopen is zal $output geretourneerd worden en in het andere geval FALSE.

Het resultaat van dit script is als volgt:

Array
(
    [0] => a
    [1] => gebruikers.txt
    [2] => p
)

We zien dat de map 'gebruikers' netjes uitgelezen worden en alle aanwezige mappen en bestanden gegeven worden. Alleen zien we in de bestandsstructuur dat de mappen 'a' en 'p' ook nog bestanden en mappen bevatten.

Voor het weergeven van deze bestanden en mappen kunnen we een recursief onderdeel in de functie aanbrengen. Op een bepaalde moment binnen leesUit() functie zullen we diezelfde leesUit() functie aanroepen.

Voorbeeld 9: Volledige directory uitlezen met behulp van recursie
<?php
function leesUit($path)
{
if($dir = @opendir($path))
{
while(($file = readdir($dir)) !== FALSE)
{
if(is_dir($path.'/'.$file) && $file != '.' && $file != '..')
{
$output[$file] = leesUit($path.'/'.$file);
}
elseif($file != '.' && $file != '..')
{
$output[] = $file;
}
}
closedir($dir);
}
return isset($output) ? $output : FALSE;
}

$map = 'gebruikers';
echo '<pre>';
print_r(leesUit($map));
echo '</pre>';
?>
Dit is dan het resultaat:

Array
(
    [a] => Array
        (
            [0] => arend.txt
            [1] => arjan.txt
        )

    [0] => gebruikers.txt
    [p] => Array
        (
            [eigenschappen] => Array
                (
                    [0] => file.txt
                )

            [0] => piet.txt
        )

)

We zien dat dit inderdaad de juiste weergave is van de bestandsstructuur. Alleen hoe zijn we hier nu aan gekomen?

In plaats van alle tegengekomen resultaten direct in de $output array te plaatsen, controleren we nu eerst of het resultaat een nieuwe directory betreft. Als dat zo is maken we in de $output array een nieuwe key aan met de naam van die map. Vervolgens roepen we de leesUit() functie aan om de waarde voor die key te verzorgen.

Op deze manier is het dus mogelijk om directories tot op oneindige dieptes uit te lezen. Het recursieve gedeelte van de functie zal immers elke keer opnieuw aangeroepen worden. Het grote voordeel van het toepassen van recursie in dit voorbeeld moge duidelijk zijn. Je hoeft namelijk niet van tevoren te weten hoe je bestandstructuur eruit ziet en hoeveel bestanden zich bijvoorbeeld in een bepaalde map bevinden.

Het uitlezen van een directory op een iteratieve manier is natuurlijk mogelijk, maar is vele malen lastiger. Je zult namelijk per directory moeten bepalen hoeveel items die directory bevat, welke items bestanden of mappen zijn en vervolgens van eventuele mappen ditzelfde proces herhalen. Als je een complete directory wilt uitlezen is het dus van tevoren vereist om te weten hoe diep de directory is. En daar heb je in de recursieve functie helemaal geen boodschap aan.

Tot zover deze tutorial over het gebruik van recursie in PHP scripts. Het zal voor velen nog wel even wennen zijn om met deze andere manier van denken te werken, maar zodra dat lukt zul je de kracht ervan ontdekken. Een makkelijke manier om hieraan te wennen is je bestaande iteratieve functies op een recursieve manier proberen te schrijven.

Hoewel elke iteratieve functie recursief geschreven zou kunnen worden en omgekeerd, wil dat nog niet zeggen dat dit altijd wenselijk en even makkelijk is. We hebben in deze tutorial wel gezien dat sommige recursieve oplossingen eleganter en soms zelfs veel eenvoudiger zijn dan de iteratieve variant, zijn zoals aangegeven niet altijd even praktisch. Let dus op waar je die functies gebruikt.

Ik zou vooral lekker doorgaan met het programmeren op een iteratieve manier, maar houdt het idee van recursie in je achterhoofd. Mocht je er op een gegeven moment niet uitkomen, bekijk dan eens of je het probleem recursief zou kunnen oplossen.

Deze tutorial is ook hier te vinden.

Disclaimer
Ik heb deze tutorial niet geheel zelf geschreven. Het grootste deel is een vertaling van Recursion in PHP: Tapping Unharnessed Power geschreven door Robert Peake. Ik heb de tekst op sommige punten gewijzigd en enkele andere voorbeelden gebruikt.