Websiteentwicklung: PHP: Rekursion

Websiteentwicklung PHP Rekursion

Was ist Rekursion?

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

Ein Beispiel

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;
}

Zurück zu Reguläre Ausdrücke | Hoch zu PHP | Vor zu PHP-Referenz