Rekursiva funktioner i PHP
Vad är en rekursiv funktion?
Funktioner är grundläggande inom all programmering. Rekursiva funktioner är kortfattat funktioner som anropar sig själva. Två kriterier ställs alltid på en rekursiv funktion:
- Den måste innehålla ett avslutande villkor. Med det innebär att det måste finnas ett tillstånd då funktionen slutar anropa sig själv. Gör den inte det kommer funktionen anropa sig själv i oändlig tid (en. infinite loop), eller till du på annat sätt avbryter processen.
- Ett rekursivt funktionsanrop ska alltid skilja sig från det tidigare anropet. Undvik redundans, det vill säga att behandla samma information flera gånger.
Exempel: En enkel rekursiv funktion i PHP
En enkel rekursiv funktion skulle t.ex. kunna vara att räkna alla tal mellan (och inklusive) två angivna heltal. I PHP hade det sett ut så här:
function recursive_count($start, $end)
{
if ($start <= $end)
{
echo $start.' ';
$start++;
recursive_count($start, $end);
}
}
recursive_count(1,10);
echo "<br />";
recursive_count(22, 30);
Koden uppfyller båda kraven för en rekursiv funktion. Dels har den ett avslutande villkor (start-variabeln måste vara av lägre värde eller lika med end-variabeln, annars slutar funktionen) och då variabeln start ökar för varje iteration kommer heller aldrig samma funktionsanrop att göras. Koden ovan genererar förstås följande resultat:
1 2 3 4 5 6 7 8 9 10 22 23 24 25 26 27 28 29 30
Varför använda rekursiva funktioner?
Inga konstigheter så långt, eller hur? Men är det inte enklare att använda en vanlig loop? Jo, förmodligen! Och i de allra flesta fall (som i det ovan) är det svårt att motivera en rekursiv funktion framför användandet av en loop. Resultatet är detsamma, men för de allra flesta är det lättare att läsa och begripa vanliga loopar, kanske just för att de är mer vanligt förekommande.
I några fall är användandet av rekursiva funktioner mer naturliga än användandet av en loop. Ett exempel är t.ex. vid beräkning av matematisk fakultet. Ett annat exempel där rekursiva funktioner brukar användas är då man vill söka igenom katalogstrukturer eller andra trädstrukturer.
Exempel: En rekursiv sökning i en katalogstruktur
En lite mer komplex rekursiv funktion i PHP. Här börjar vi i en katalog och söker igenom varje underkatalog, deras underkataloger, osv, till hela katalogträdet är genomsökt.
function traverse_dir($dir)
{
if (is_dir($dir))
{
$subdirs = get_subdirs($dir);
foreach($subdirs as $subdir)
{
$cwd = $dir . '/' . $subdir;
traverse_dir($cwd);
echo $cwd."\n";
}
}
else echo 'No such directory: ' . $dir;
}
function get_subdirs($dir)
{
$dirs = array();
$files = @scandir($dir); // ignore permission denied warnings
if($files) // if directory and permission not denied
{
foreach ($files as $file)
{ // ignore . and ..
if ((is_dir($dir.'/'.$file)) && ($file != '.') && ($file != '..'))
{
$dirs[] = $file;
}
}
}
return $dirs;
}
traverse_dir('/var/www');
Funktionen traverse_dir tar här en katalog (‘/var/www’) som enda parameter och söker sedan igenom den efter underkataloger. Funktionen gör sedan ett anrop på sig självt och upprepar proceduren i varje underkatalog. Villkoren för funktionen är att fortsätta så länge det finns tillgängliga underkataloger, och då varje funktionsanrop innehåller underkatalogens namn kommer ej heller samma funktionsanrop att upprepas. Funktionen get_subdirs är ej en nödvändighet utan hade kunnat skrivas in i funktionen traverse_dir. Att tydligt separera rekursiva element och icke-rekursiva gör dock koden lättare att överblicka, förstå och felsöka.
Slutligen
Rekursiva funktioner används främst inom funktionell programmering, och sällan i språk som PHP. I många av de fall där rekursiva funktioner faktiskt hade varit användbara (som i fallet ovan) finns oftast färdiga funktioner att nyttja som utför samma sak men med betydligt färre rader kod (se exempelvis funktionen glob i PHP). Att ha koll på vad en rekursiv funktion är och hur den tillämpas kan ändå vara av värde, dels för att förstå hur de ”färdiga” funktionerna arbetar, men också för att det är ytterligare ett verktyg som kan komma till nytta i andra programmeringssituationer. Även om exemplen ovan är skrivna i PHP är principen förstås densamma oavsett programmeringsspråk.
