Rekursive Programmierung

0 | 17006 Aufrufe
Sie können diese Wikiseite nach der Anmeldung auf Webmasterpro bearbeiten. Helfen Sie mit und verbessern Sie "Rekursive Programmierung" mit Ihrem Wissen!

Anzeige Hier werben

Was ist Rekursion?

Eine Funktion ist rekursiv ("zurücklaufend"), wenn sie durch sich selbst definiert ist. Das heißt: Sie ruft sich selbst auf um ein Problem zu lösen, bis eine bestimmte Abbruchbedingung erfüllt wird.

Fakultät

Die Fakultät einer natürlichen Zahl, ist sie selbst mit allen kleineren natürlichen Zahlen - außer 0 - multipliziert. Daraus ergibt sich für z.B. 3! = 3*2*1 oder 5! = 5*4*3*2*1. Allgemein ist n! = n*(n-1)*(n-2)*..*1. In der Mathematik ist definiert, dass die Fakultät von 0 immer 1 ist (unsere Abbruchbedingung).

Fakultät und Rekursion

Was hat Fakultät mit Rekursion zutun? Man kann eine Funktion zur Lösung der Fakultät rekursiv lösen. Dieses Beispiel wird sehr oft verwendet, weil es anschaulich und einfach ist. Man könnte nämlich statt 4! = 4*3*2*1 auch 4! = 4*3! schreiben, da 3!=3*2*1 und stattdessen könnte man 3*2! schreiben usw. Die Funktion fak(n) sähe in Pseudocode etwa so aus:

 
Text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
fak(n):
 falls n > 0
  return n * fak(n-1);
 andernfalls
  return 1;

Bsp.:
fak(3) = 3 * fak(2); // ruft fak(2) auf
fak(2) = 2 * fak(1); // ruft fak(1) auf
fak(1) = 1 * fak(0); // ruft fak(0) auf
fak(0) = 1; // Abbruchbedingung fak(0)=1

Mit der Abbruchbedingung beginnt die Rekursion, denn
fak (0) liefert 1 an fak(1), somit kann fak(1) 1*1 an fak(2) liefern und fak(2) dann 2*1*1 an fak(3) ..

In PHP-Code könnte das so aussehen:

Fakultät rekursiv  
PHP
1
2
3
4
5
6
7
8
<?php
  function fak(n) {
    if(n > 0)
      return n * fak(n-1);
    else
      return 1;
  }
?>

Andere Anwendungen für Rekursion

Oft wird die Rekursion für das Abbilden von Dateistrukturen (Filelist) oder zum Erstellen von anderen Verzweigungsbäumen verwendet.

Verzeichnis rekursiv löschen

Die Funktion rmdir() löscht Verzeichnisse nur, wenn sie leer sind. Die folgende Funktion durchläuft alle Unterverzeichnisse des gegebenen Verzeichnisses rekursiv und löscht jeweils alle Dateien in den Verzeichnissen, damit im Anschluss rmdir() ausgeführt werden kann.

Verzeichnis rekursiv löschen  
PHP
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function rmdir_recursive($dir) {
  if(is_dir($dir)) {
    if($dh = opendir($dir)) {
      if($dir[strlen($dir)-1] != '/') $dir = $dir.'/';
      while(($file = readdir($dh)) !== false) {
        if($file != '.' && $file != '..') {
          if(is_dir($dir.$file) && !is_link($dir.$file)) {
            rmdir_recursive($dir.$file);
          } elseif(is_file($dir.$file)) {
            unlink($dir.$file);
          }
        }
      }
      closedir($dh);
    }
    rmdir($dir);
  }
}

Hier ist sicherlich noch viel Platz für Verbesserungen und Erweiterungen. Es ist Mitarbeit von jedem erwünscht!


Wikiseite bearbeiten

Diese Seite kann von jedem registrierten Benutzer bearbeitet werden. Bisher haben 4 Personen an der Seite "Rekursive Programmierung" mitgewirkt.

Sie haben einen Fehler entdeckt oder möchten etwas ergänzen? Dann können Sie nach der Anmeldung "Rekursive Programmierung" hier bearbeiten.

Mitarbeiter
  • hat keine Beschreibung angegeben. Eine Beschreibung kann man unter dem Punkt "Profil bearbeiten" im Kontrollzentrum eintragen.
  • Kfz Gutachter München
  • hat keine Beschreibung angegeben. Eine Beschreibung kann man unter dem Punkt "Profil bearbeiten" im Kontrollzentrum eintragen.
  • hat keine Beschreibung angegeben. Eine Beschreibung kann man unter dem Punkt "Profil bearbeiten" im Kontrollzentrum eintragen.