Zum Inhalt springen

Websiteentwicklung: PHP: Rekursion

Aus Wikibooks

Was ist Rekursion?

[Bearbeiten]

Rekursive Funktionen sind vereinfacht gesagt Funktionen, die in ihrer Ausführung sich selbst noch ein mal aufrufen mit einem veränderten Argument.

Ein Beispiel

[Bearbeiten]

Hier ein kleines Beispiel zur Rekursion mit einer rekursiven PHP Funktion f() zur Berechnung der Fakultät einer ganzen Zahl:

function f($i) 
{
  if (!is_integer($i) or $i < 1) 
  {
    return "Fehler";
  }

  if ($i == 1) 
  {
    return $i;
  }
  else 
  {
    /*
      return $i * f(--$i);  
      kann nicht verwendet werden, da --$i zuerst dekrementiert!!!
    */
    $temp = $i;
    return $temp * f(--$i);
  }
}

In Zeile 3 prüft die Funktion, ob der Aufrufparameter gültig ist und beendet sich, falls der Parameter keine ganze Zahl (is_integer) oder kleiner 1 ist. Die Zeile 8 enthält die Abbruchbedingung für die Rekursion: Sobald der Parameter 1 ist, liefert die Funktion 1 zurück (und ruft sich nicht mehr selbst rekursiv auf). Wird die Abbruchbedingung nicht erfüllt, erfolgt in Zeile 14 die eigentliche Rekursion durch Aufruf von f(--$i). Hier wird der Parameter $i zuerst dekrementiert, bevor er der Funktion übergeben wird. Das führt dazu, dass die Variable $i in der Zeile VOR Auswertung dekrementiert wird (an BEIDEN Stellen) - deshalb ist eine Zwischenvariable nötig. So wird - hoffentlich - sichergestellt, dass die Funktion einmal abbricht, wenn der Parameter < 2 wird.

Aufruf erfolgt dann z.B.:

$f = f(5);

Dieses einfache Beispiel kann auch als while-Konstrukt ohne Rekursion realisiert werden:

function f($i) 
{
  if (!is_integer($i) or $i < 1) 
  {
    return "Fehler";
  }

  $ret = $i;
  while ($i-- > 1)
  {
    $ret *= $i;
  }

  return $ret;
}