SELFPHP

Rekursive/Iterative Funktionen



Informationsseite

nach unten Autor

nach unten Allgemeine Informationen

nach unten Beispiel: Fakultät rekursiv
nach unten Beschreibung: Fakultät rekursiv

nach unten Beispiel: Fakultät iterativ
nach unten Beschreibung: Fakultät iterativ

nach unten Beispiel: Rekursive Dateiauflistung
nach unten Beschreibung: Rekursive Dateiauflistung

nach unten Beispiel: Iterative Dateiauflistung
nach unten Beschreibung: Iterative Dateiauflistung

nach unten Fazit

nach unten Download

nach unten 

Autor

Name: Daniel Kressler
Email: E-Mail d.kressler@selfphp.info
Website: http://www.selfphp.info

 

nach obennach unten 

Allgemeine Informationen

Zuerst einmal - Eine Funktion/ ein Algorithmus ist rekursiv, wenn sie/er teilweise oder gänzlich sich selbst aufrufen. Eine Funktion/ ein Algorithmus ist iterativ, wenn die Funktionalität auf einer Schleife basiert oder auf eine hinaus läuft. Rekursive Fälle brauche immer eine Abbruchbedingung, ähnlich wie Schleifen eine Ausstiegsbedinung brauchen. Alles was sich iterativ lösen lässt, lässt sich auch immer relativ einfach rekursiv lösen. Nur, wenn man versucht eine Rekursion in eine Iteration zum zu stricken, wird das manchmal nur mit akrobatischen Gedankengängen zu bewältigen sein. Rekursive Funktionen/Algorithmen, sind im Allgemeinen langsamer als eine vergleichbare iterative Lösung, dafür aber meistens wesendlich übersichtlicher. Es muss also immer wohl überlegt sein, was sinnvoller ist. Sind Sie sich jedoch Mal nicht sicher, was jetzt die Bessere Variante wäre, dann wählen Sie die rekursive Lösung, weil alle Vor- und Nachteile mit einander verglichen zur Einsicht führen: Am Ende setzt sich die Überschaubarkeit durch, somit sind rekursive Funktionen im Zweifelsfall vorzuziehen.

Ein jeder Programmierer wird früher oder später auf Probleme stoßen, die sich nur durch Rekursion/Iteration lösen lassen. Denn alleine ein mehrdimensionales Array darzustellen, ist ohne Rekursion/Iteration gar nicht möglich, natürlich nur, wenn nicht gewiss ist wie viele Dimensionen diese Array haben könnte. Gibt es jedoch einen Fixwert, was die Anzahl der Dimensionen betrifft, so kann man Rekursion/Iteration, mit teils viel Code, einfach umgehen. Doch dies wird in der Regel nicht der Fall sein. Ein mehrdimensionales Array könnte man mit einer Laufwerks- oder Verzeichnisstruktur vergleichen, sehen Sie sich dazu, das Beispiel "Dateiauflistung" an. Das wird Ihnen diesen Gedanken näher bringen.

 

nach obennach unten 

Beispiel: Fakultät rekursiv


<?php
function faculty($int_n){

    
// 0! und 1! immer gleich 1
    
if($int_n < 2){

        
// Rueckgabewert 1
        
return 1;

    
// $int_n nicht 0 oder 1
    
}else{

        
// $int_n Mal Rueckgabewert von "faculty"
        
return $int_n * faculty($int_n - 1);
    }
}

echo
faculty(0) . '<br>' . "\n", // Ausgabe: 1
     
faculty(1) . '<br>' . "\n", // Ausgabe: 1
     
faculty(2) . '<br>' . "\n", // Ausgabe: 2
     
faculty(4) . '<br>' . "\n", // Ausgabe: 24
     
faculty(6) . '<br>' . "\n", // Ausgabe: 720
     
faculty(8) . '<br>' . "\n", // Ausgabe: 40320
     
faculty(10);                // Ausgabe: 3628800
?>

 

nach obennach unten 

Beschreibung: Fakultät rekursiv

Bei der rekursiven Funktion "faculty" wird immer zuerst geprüft, ob der übermittelte "Wert" ($int_n) kleiner als "2" ist, Also entweder "0" oder "1". Ist das der Fall, dann wird immer "1" als Rückgabe getätigt. Ist es nicht der Fall, so tritt die ELSE-Bedingung in Kraft, was zu Folge hat, dass die Funktion "faculty" rekursiv Aufgerufen wird. Dabei wird der angegebene Wert von "$int_n" mit dem Rückgabewert der Funktion "faculty", Mal genommen und das solange bis der übermittelte Parameter kleiner als "2" ist.

Ein visuelles Beispiel:

Rufen Sie die Funktion "fakulty" mit dem Argument "4" auf (faculty(4)), dann läuft die Berechnung folgendermaßen ab:

4 * (4 - 1) * (3 - 1) * (2 - 1)

Oder einfach:

4 * 3 * 2 * 1

Das Ergebnis wäre dann "24".

 

nach obennach unten 

Beispiel: Fakultät iterativ


<?php
function faculty($int_n){

    
// Deklariere $int_result mit Definiton 1
    
$int_result = 1;

    
// Ist $int_n kleiner als 2
    
if($int_n < 2){

        
// ...dann $int_result immer 1
        
$int_result = 1;

    
// $int_n groeßer als 2
    
}else{

        
// FOREACH-Schleife starten und bis $int_n
        // ausfuehren. $int_times akt. Wert
        
foreach(range(1, $int_n) as $int_times){

            
// $int_result Mal $int_times
            
$int_result *= $int_times;
        }
    }

    
// $int_n! Ergebnis zurueckgeben
    
return $int_result;
}

echo
faculty(0) . '<br>' . "\n", // Ausgabe: 1
     
faculty(1) . '<br>' . "\n", // Ausgabe: 1
     
faculty(2) . '<br>' . "\n", // Ausgabe: 2
     
faculty(4) . '<br>' . "\n", // Ausgabe: 24
     
faculty(6) . '<br>' . "\n", // Ausgabe: 720
     
faculty(8) . '<br>' . "\n", // Ausgabe: 40320
     
faculty(10);                // Ausgabe: 3628800
?>

 

nach obennach unten 

Beschreibung: Fakultät iterativ

Die iterative Version der Funktion "faculty" geht so vor, dass zuerst die Variable "$int_result" deklariert und mit dem Wert 1 definiert wird. Anschließend wird auch hier erstmal geprüft, ob das übergebene Argument kleiner als "2" ist. Ist das Argument "0" oder "1", also kleiner als "2", dann ist der Rückgabewert "1", weil "0 Fakultät" oder "1 Fakultät" immer "1" ist. Ist das Argument hingegen größer als "1", mindestens 2 also, dann kommt die ELSE-Bedingung zum Zuge. In der ELSE-Bedingung wird eine FOREACH-Schleife gestartet, welche den Zahlen bereich von 1 bis $int_n durchläuft und jedes Mal das Ergebnis des letzten Durchlaufs, mit der aktuellen Zahl des Zahlenbereichs, Mal nimmt und gleichzeitig der Variablen "$int_result" den neuen Wert zuweist. Das erledigt der arithmetische Operator "*=". Vor dem Ersten Durchlauf, gibt es auch bereits ein Ergebnis und zwar "1" - die Definition der Variablen "$int_result". Ist der Zahlenbereich abgearbeitet, so wird zum Schluss nur noch das finale Ergebnis zurückgegeben.

 

nach obennach unten 

Beispiel: Rekursive Dateiauflistung

<?php
/*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*/
/****     Konfiguration der Funktion      ****/
/*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*/

// Die Variable $str_hyphen beinhaltet das Trennzeichen, welches die Ordner und
// Dateien trenn. Auf Windowssystemen ist es der Slash "/" und auf Unixsystemen
// ist es der Backslash "\". Hier wird jetzt aber immer der Backslash genutzt,
// weil Windows auch mit dem Backslash korrekt arbeitet.
//
// Beachten Sie bitte, dass der Backslash escaped werden muss, da es sonst zum
// "Parse error" kommt.
$str_hyphen = '\\';

// Die nun folgende Kontrollabfrage prüft, welches System Ihr Server nutzt.
// Dementsprechend wird der Wert fuer den Zeilenumbruch in der Variablen $str_nl
// gespeichert.
if(eregi('win', PHP_OS)){
    
$str_nl = "<br>\r\n";
}elseif(
eregi('mac', PHP_OS)){
    
$str_nl = "<br>\r";
}else{
    
$str_nl = "<br>\n";
}



/*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*/
/****  Rekursive Funktion "filelisting"   ****/
/*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*/

function filelisting(){

    
// Argumente laden
    
$arr_args = func_get_args();

    
// pruefen ob das einzigste Argument leer ist
    
if(empty($arr_args[0])){

        
// Uebergabe des Strings ".\" an $str_path
        
$str_path = '.' . stripslashes($GLOBALS['str_hyphen']);

    }else{

        
// Uebergabe des altuellen Pfads an $str_path
        
$str_path = $arr_args[0];

    }

    
// Verzeichnis-Handle anlegen
    
$res_dir = dir($str_path);

    
// Abarbeitung der Dateien und Ordner, im aktuellen Verzeichnis-Handle
    
while($str_file = $res_dir->read()){

        
// "." und ".." ignorieren
        
if(($str_file !== '.') && ($str_file !== '..')){

            
// Pruefen ob gueltiges Verzeichnis
            
if(is_dir($str_path . $GLOBALS['str_hyphen'] . $str_file)){

                
// Rekusiv Funktion "filelisting" aufrufen
                
filelisting($str_path . $GLOBALS['str_hyphen'] . $str_file);
            }else{

                
// Dateien ausgeben
                
echo $str_path . $GLOBALS['str_hyphen'] . $str_file . $GLOBALS['str_nl'];
            }
        }
    }

    
// Verzeichnis schließen
    
$res_dir->close();
}

// Aufruf der Funktion
filelisting();
?>

 

nach obennach unten 

Beschreibung: Rekursive Dateiauflistung

Zu Anfang werden die der Funktion "filelisting" übergebenen Argumente, mit der Funktion "func_get_args", geladen. Der Rückgabe Wert der Funktion "func_get_args" ist vom Type "Array" - genauer es ist ein indiziertes Array - dadurch ist darauf zu achten, dass man auch "Array typisch" auf die Werte zurückgreift. Der Funktion "filelisting" wird immer nur ein Argument übergeben, also hat das von "func_get_args" zurückgegeben Array immer nur ein Element. Dieses Element hat den Index "0" (indizierte Arrays beginnen mit "0", nicht mit "1"). Mit der Funktion empty wird geprüft, ob dieses Array-Element leer oder nicht deklariert ist. Jetzt tritt an dieser Stelle ein Sonderfall auf. Rufen Sie die Funktion "normal" auf, dann sind das Array und somit auch das Array-Element, direkt nach dem Aufruf, noch leer, weil kein Argument angegeben wurde. Sie könnten aber eines angeben, damit die Funktion mit der Dateiauflistung in einem von Ihnen gewählten Verzeichnis anfängt. Nur Aus diesem Grund wird an dieser Stelle eine IF-Anweisung ausgeführt. Der IF-Teil deklariert die Variable "$str_path" und übergibt ihr den String ".\". Dieser String ist das Verzeichnis mit dem die Dateiauflistung beginnen soll und selbiger setzt sich aus zwei Teile zusammen: Erster Teil "." (Punkt), zweiter Teil "\" (Backslash). Auf den Backslash muss die Funktion "stripslashes" angewandt werden, da die Funktion sonst mit dem noch escapeden Backslash "\\" arbeitet. In der Konfiguration der Funktion, musste dieser ja escaped werden, damit es nicht zu einem "Parse error" kommt. Der definierte String ".\" sagt der Funktion, dass sie in dem Verzeichnis mit der Dateiauflistung anfangen soll, in dem sich das ausführende Script selbst auch befindet. Im weiteren Verlauf wird lediglich der ELSE-Teil ausgeführt werden, weil der Funktion filelisting fortan ein Argument übergeben werden wird. Der ELSE-Teil ist einzig und allein die Übergabe des Array-Elements mit dem Index "0" an die Variable "$str_path". Das ist darum nötig, damit in der Funktion mit nur einer Variablen für die Pfadangabe gearbeitet werden muss. Als nächstes beginnen, dann die eigentlichen Verzeichnisoperationen. Zunächst wird ein Verzeichnis-Handle an Hand der Pfadübergabe von "$str_path" angelegt und in "$res_dir" gespeichert. Im Weiteren durchläuft eine WHILE-Schleife ein Verzeichnis, das mit Referenz des Verzeichnis-Handle gelesen wurde. Die anschließende IF-Anweisung filtert die Einträge "." und ".." raus, würde man dies nicht machen, so würde das Script "gehimmelt". Anschließend beginnt die Musterung von Ordnern und Dateien. Sprich, ist ein Verzeichniseintrag ein Ordner, dann wird die Funktion "filelisting" rekursiv aufgerufen. Dabei wird als Argument, der Pfad zum Ordner und der Ordner selbst angegeben. Ferner, wenn es ein Ordner ist, beginnt an dieser Stelle das ganze Spiel von vorne: Ordner öffnen, auslesen und darin befindliche Ordner / Dateien aussortieren. Andernfalls, wenn der aktuell gewählte Verzeichniseintrag eine Datei ist, werden der Pfad zur Datei und der Dateiname ausgegeben.

 

nach obennach unten 

Beispiel: Iterative Dateiauflistung

<?php
/*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*/
/****     Konfiguration der Funktion      ****/
/*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*/

// Die Variable $str_hyphen beinhaltet das Trennzeichen, welches die Ordner und
// Dateien trenn. Auf Windowssystemen ist es der Slash "/" und auf Unixsystemen
// ist es der Backslash "\". Hier wird jetzt aber immer der Backslash genutzt,
// weil Windows auch mit dem Backslash korrekt arbeitet.
//
// Beachten Sie bitte, dass der Backslash escaped werden muss, da es sonst zum
// "Parse error" kommt.
$str_hyphen = '\\';

// Die nun folgende Kontrollabfrage prüft, welches System Ihr Server nutzt.
// Dementsprechend wird der Wert fuer den Zeilenumbruch in der Variablen $str_nl
// gespeichert.
if(eregi('win', PHP_OS)){
    
$str_nl = "<br>\r\n";
}elseif(
eregi('mac', PHP_OS)){
    
$str_nl = "<br>\r";
}else{
    
$str_nl = "<br>\n";
}



/*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*/
/****  Iterative Funktion "filelisting"   ****/
/*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*/

function filelisting(){

    
// Temporaeren Speicher initialisieren und mit dem Ersten
    // Array-Element fuellen.
    
$arr_buffer = array('.' . stripslashes($GLOBALS['str_hyphen']));

    
// Durchlaufen des Temporaeren Speichers
    
while($arr_buffer){

        
// Erstes Array-Element in $str_path speichern und
        // aus Array loeschen
        
$str_path = array_shift($arr_buffer);

        
// Verzeichnis-Handle erstellen
        
$res_dir = dir($str_path);

        
// Durchlaufen der einzelnen Verzeichniseintraege
        
while(false !== ($str_file = $res_dir->read())){

            
// Ausmusterung von "." und ".." aus den
            // Verzeichniseintraegen
            
if(($str_file !== '.') && ($str_file !== '..')){

                
// Wenn Eintrag ein Ordner
                
if(is_dir($str_path . $GLOBALS['str_hyphen'] . $str_file)){

                    
// ...dann dem Temporaeren Speicher hinzufügen
                    
$arr_buffer[] = $str_path . $GLOBALS['str_hyphen'] . $str_file;
                    
                
// Eintrag kein Ordner
                
}else{
                
                    
// ...dann Pfad und Dateinamen ausgeben
                    
print $str_path . $GLOBALS['str_hyphen'] . $str_file . $GLOBALS['str_nl'];
                }
            }
        }
        
        
// Verzeichnis schließen
        
$res_dir->close();
    }
}

// Funktion aufrufen
filelisting();
?>

 

nach obennach unten 

Beschreibung: Iterative Dateiauflistung

Bei der iterativen Funktionsversion von "filelisting" wird zuerst ein Array deklariert. Dieses Array wird als Buffer/Zwischenspeicher gebraucht, damit die Möglichkeit gegeben ist, weitere Pfade zu Ordnern zuspeichern, welche erst im Verlauf der Funktion gefunden werden. Die anschließende WHILE-Schleife durchläuft diesen Buffer. Innerhalb der Schleife wir mit Hilfe der Funktion "array_shift" immer das Erste Buffer-Element - $arr_buffer ist ja ein indiziertes Array - extrahiert, sprich es wird ausgelesen und aus dem Buffer gelöscht, damit es nicht erneut selektiert werden kann. Das extrahierte Element wird in der Variablen "$str_path" gespeichert und diese Variable wird Funktion "dir" als Argument übergeben. Die Funktion "dir" erzeugt dann einen Verzeichnis-Handle daraus, der in der zweiten WHILE-Schleife mit der Funktion (bzw. Methode) "read" ein Verzeichnis ausliest und das Ergebnis in "$str_file" speichert. Die folgenden IF-Anweisung filtert auch hier wieder "." und ".." aus den Verzeichniseinträgen heraus damit PHP nicht "abstürzt". Die nächste IF-Anweisung prüft, ob der aktuelle Verzeichniseintrag ein Ordner ist und wenn, dann wird der Ordner samt Pfad in den Buffer geschrieben. Ist der Eintrag kein Order so wird eine Ausgabe, des Aktuelle Verzeichniseintrags und dem dazugehörigen Pfad, getätigt. Dieser Vorgang wiederholt sich so oft, bis dass das Aktuell offene Verzeichnis komplett durchlaufen ist. Danach springt die erste WHILE-Schleife wieder an, all das geht immer so weiter, bis der Buffer leer ist. Das bedeutet auch, dass die letzte mögliche Verzeichnisebene erreicht wurde. In der Verzeichnisstruktur gibt es ab diesem Punkt, keine Unterverzeichnisse mehr.

 

nach obennach unten 

Fazit

Rekursion/Iteration ist ein komplexes Thema, jedoch kann man es in manchen Fällen eben nicht ohne lösen. Zur Rekursion lässt sich noch sagen: "Ein Schritt zurück bedeutet, Zwei Schritte nach Vorne..."

 

nach obennach unten 

Download

Der Download beeinhaltet folgende Dateien:
  • allgemeine_infos.txt
  • fakultaet_rekursiv_beispiel.php
  • fakultaet_rekursiv_erklaerung.txt
  • fakultaet_iterativ_beispiel.php
  • fakultaet_iterativ_erklaerung.txt
  • rekursive_dateiauflistung_beispiel.php
  • rekursive_dateiauflistung_erklaerung.txt
  • iterative_dateiauflistung_beispiel.php
  • iterative_dateiauflistung_erklaerung.txt
  • README.TXT
Download starten

 

nach oben
weiter:weiter Seite
zurück:zurück Seite Programmiertechniken
 

© 2001, 2002, 2003, 2004, 2005 E-Mail Damir Enseleit, mail@selfphp.de