Schleifen binden - Theorie Lektion 8

Erstellt von Frithjof Fri, 25 Jul 2008 20:58:00 GMT

Der letzte Artikel versprach vollmundig, dass es weitergeht. Und das wird es auch! Was sind schon 50 Tage? Es lebt sich auch gut ohne Ruby.

Zur Einstimmung nach dieser langen Pause gibt es nicht die bereits erwartete Abschlußlektion 20, sondern eine kleine Theorielektion zum Thema Rekursion.

Was ist Rekursion?

Rekursion leitet sich vom lateinischen Verb recurrere ab. Es bedeutet etwa zurückkehren, zurücklaufen, wobei im Zusammenhang mit Programmiersprachen wohl zurückkehren die treffendste scheint.

Mit Rekursion kann man wiederkehrende Programmabläufe gestalten ohne eine richtige Schleife zu verwenden. Mit Ruby hattest du bisher folgende Möglichkeiten kennengelernt, eine Schleife zu nutzen:

  • while
  • for each
  • Iteratoren

Jede Programmiersprache hat für Schleifen gewöhnlich spezielle Schlüsselwörter, die am Beginn oder Ende eines Programmabschnittes stehen, der solange wiederholt werden soll, bis eine gewisse Bedingung erfüllt ist, die dann zum Abbruch der Schleifendurchläufe führt.

Man kann aber alles, was man mit diesen speziellen Schlüsselwörtern als Schleifen programmieren kann auch ohne sie bewerkstelligen. Ja es gibt sogar (Programmier-) Sprachen, die für Schleifen überhaupt keine Schlüsselwörter bereitstellen. XSLT zum Beispiel bietet zwar ein Schlüsselwort for-each an, um über einer Eingabemenge eine Schleife zu bilden, allerdings ist man dabei direkt an die Länge der Eingabemenge gebunden. Und wenn keine Eingabemenge vorliegt, nützt dieses Schlüsselwort nicht viel. In XSLT kommt man somit um Rekursion überhaupt nicht herum, wenn man Schleifen braucht.

Grundprinzip der Rekursion

Ein erstes Merkmal der Rekursion ist, dass sich ein Programmabschnitt selbst erneut aufruft. Der erste Aufruf muss jedoch von außen erfolgen.

Irgendwann sollte das sich selber aufrufen aber zu Ende sein. Ein zweites Merkmal ist somit eine exakt definierte Abbruchbedinung. Ist diese Bedingung erfüllt, soll der Sich-Selber-Aufruf nicht mehr vorgenommen werden.

Ein einfaches Beispiel soll das verdeutlichen. Wir schreiben ein Rubyprogramm, dass sich selber aufruft. Dazu verwendet es die Methode system aus dem Rubykern. Mit system kann man Befehle der Kommandozeile aus einem Rubyprogramm heraus ausführen. Den Namen der Datei des aktuell laufenden Rubyprogramms erhältst du mit der globalen Variable __FILE__.


# theorie_08.rb
puts "Ein Hallo aus der Rekursion!" 

system("ruby " + __FILE__)

Starte das Programm an der Konsole mit


ruby theorie_08.rb

und es wird dir ewig den selben Gruß senden


[25.07.2008, 22:07]:> ruby theorie_08.rb
Ein Hallo aus der Rekursion!
Ein Hallo aus der Rekursion!
Ein Hallo aus der Rekursion!
Ein Hallo aus der Rekursion!
Ein Hallo aus der Rekursion!
...

solange bis du es endlich mit der Abbruchbedinung Strg-C abbrichst. Das ist eine ziemlich harte Abbruchbedingung.

Du bemerkst hier das Dilemma: das Programm selber kann nicht entscheiden, das wievielte mal es bereits aufgerufen wird. Es hat also nichts, woran es die Notwendigkeit eines Abbruchs erkennen könnte.

Das Programm muss beim Aufruf von sich selbst sich selbst einen Parameter mitgeben, mit dem irgendwie dann ein Abbruchkriterium formuliert werden kann.

Einem Rubyprogramm kann man einen Parameten mitgeben, indem man ihn einfach nach dem Programmnamen mit auf der Kommandozeile hinschreibt. Alle so nach dem Programmnamen angegebenen Parameter werden in einem globalen Array mit dem festen Namen ARGV festgehalten und stehen so innerhalb des Programms zur Verfügung. Merke dir die ARGV als ARGumentVektor (Vektor meint dasselbe wie Array oder Liste).


# sag_hallo.rb
if not ARGV[0].nil?
  puts "Hallo " + ARGV[0] + "!" 
else
  puts "Hallo! Wie ist dein Name?" 
end

[25.07.2008, 22:16]:> ruby sag_hallo.rb
Hallo! Wie ist dein Name?

[25.07.2008, 22:17]:> ruby sag_hallo.rb Livia
Hallo Livia!

Für das rekursive Programm kannst du nun prima die Parameterliste ARGV verwenden, um dem Programm ab dem ersten Aufruf über alle weiteren Selbstaufrufe hinweg Informationen zukommen zu lassen, die es dann für ein sinnvolles Abbruchkriterium verwenden kann.

Versuche es!


# theorie_08.rb

# Zuerst das Abbruchkriterium checken
parameter = ARGV[0]
if parameter.nil?
  # Ohne Parameter mach ich gar nix
  puts "Parameter fehlt!" 
  exit
else
  parameter = parameter.to_i - 1
end

# Abbrechen, wenn parameter den Wert 0 unterschreitet
if parameter < 0
  exit
end

# Ansonsten dann die eigentliche Arbeit verrichten
puts "Das #{parameter}. Hallo aus der Rekursion!" 

# Und schließlich sich selbst aufrufen
system("ruby " + __FILE__ + " " + parameter.to_s)

Mit exit wird das laufende Rubyprogramm sofort verlassen.

Wie du siehst, musst du hier etwas aufpassen wegen des Datentyps. Alle Parameter, die auf der Kommandozeile einem Programm übergeben werden, landen als Strings in der ARGV Liste. Zum herunterzählen musst du den Wert zunächst mit to_i in eine ganze Zahl (Integer) verwandeln und zum Anhängen an den Selbstaufruf erneut in einen String mit to_s konvertieren.

Startest du jetzt das Programm an der Konsole, zunächst ohne, dann mit Parameter,


[25.07.2008, 22:31]:> ruby theorie_08.rb
Parameter fehlt!

[25.07.2008, 22:31]:> ruby theorie_08.rb 10
Das 9. Hallo aus der Rekursion!
Das 8. Hallo aus der Rekursion!
Das 7. Hallo aus der Rekursion!
Das 6. Hallo aus der Rekursion!
Das 5. Hallo aus der Rekursion!
Das 4. Hallo aus der Rekursion!
Das 3. Hallo aus der Rekursion!
Das 2. Hallo aus der Rekursion!
Das 1. Hallo aus der Rekursion!
Das 0. Hallo aus der Rekursion!

dann bricht die Selbstaufrufserie wie gewünscht ab, sobald der übergebene Parameter auf weniger als 0 heruntergezählt wurde.

Rekursion innerhalb eines Programms

Wie du an dem hin und herkonvertieren gesehen hast, ist die Verwendung der Rekursion auf das gesamte Programm recht fehleranfällig. Diese Art wird dir sicher auch recht selten begegnen. Viel natürlicher ist es, innerhalb eines Programms eine Rekursion aufzubauen. Welche Möglichkeiten hast du denn, um in einem Programm etwas aufzurufen?

Na klar, Methoden kann man aufrufen. Wir schreiben das bisherige Programm so um, dass wir den Teil, der sich wiederholen soll in einer eigenen Methode steht.

Zuerst musst du diese Methode einmal aufrufen (ähnlich dem ersten Programmaufruf an der Kommandozeile) und alles weitere besorgt die Methode selbst. Sie prüft das Abbruchkriterium und je nach dem arbeitet sie was und ruft sich selber nochmal auf, oder sie bricht ab.


# theorie_08_b.rb

def sag_was(counter)
  if counter.nil?
    # Ohne Parameter mach ich gar nix
    puts "Parameter fehlt!" 
    return
  else
    counter = counter - 1
  end

  # Abbrechen, wenn counter den Wert 0 unterschreitet
  if counter < 0
    return
  end

  # Ansonsten dann die eigentliche Arbeit verrichten
  puts "Das #{counter}. Hallo aus der Rekursion!" 

  # Und schließlich sich selbst aufrufen
  sag_was(counter)
end

# Erster Aufruf immer von außen
sag_was(10)

[25.07.2008, 22:31]:> ruby theorie_08_b.rb
Das 9. Hallo aus der Rekursion!
Das 8. Hallo aus der Rekursion!
Das 7. Hallo aus der Rekursion!
Das 6. Hallo aus der Rekursion!
Das 5. Hallo aus der Rekursion!
Das 4. Hallo aus der Rekursion!
Das 3. Hallo aus der Rekursion!
Das 2. Hallo aus der Rekursion!
Das 1. Hallo aus der Rekursion!
Das 0. Hallo aus der Rekursion!

Du bemerkst sofort, dass das umgeschriebene Programm viel schneller läuft. Das liegt daran, dass hier nur einmal der Rubyinterpreter gestartet werden musss. Alle rekursiven Aufrufe laufen in einer Instanz des Interpreters ab.

Voher wurde ja rekursiv immer eine neue Instanz des Rubyinterpreters gestartet— das dauerte etwas länger und verschwendete Systemressourcen.

Zu guter Letzt noch ein paar Schönheitskorrekturen: die Zählung in richtiger Reihenfolge ausgeben und ARGV nutzen, um beim Aufruf des Programms einen Startwert festlegen zu können:


# theorie_08_b.rb

def sag_was(counter, start = nil)
  if start.nil? then start = counter end
  if counter.nil?
    # Ohne Parameter mach ich gar nix
    puts "Parameter fehlt!" 
    return
  else
    counter = counter - 1
  end

  # Abbrechen, wenn counter den Wert 0 unterschreitet
  if counter < 0
    return
  end

  # Ansonsten dann die eigentliche Arbeit verrichten
  puts "Das #{start - (counter % start)}. Hallo aus der Rekursion!" 

  # Und schließlich sich selbst aufrufen
  sag_was(counter, start)
end

# Erster Aufruf immer von außen
sag_was(ARGV[0].to_i)

[25.07.2008, 22:42]:> ruby theorie_08_b.rb 5
Das 1. Hallo aus der Rekursion!
Das 2. Hallo aus der Rekursion!
Das 3. Hallo aus der Rekursion!
Das 4. Hallo aus der Rekursion!
Das 5. Hallo aus der Rekursion!

Wann Rekursion und wann lieber nicht?

Vermeide Rekursion, wo es nur möglich ist. Auch wenn Rekursion recht elegant daher kommt, büßt das Programm etwas an Lesbarkeit ein. Außerdem ist es schwieriger, einen Fehler in einem rekursiven Programm zu finden, als in gewöhnlichen Schleifen.

Nicht selten ist aber ein rekursiver Ansatz vorzuziehen. Insbesondere, wenn du einen Algorithmus implementieren musst, der bereits rekursiv entworfen ist, oder wenn sich die Rekursivität geradezu aufdrängt. Dann kann es sogar manchmal viel schwieriger sein, eine rekursionsfreie Implementierung zu finden.

Um Rekursion kommst du sowieso nicht herum, wenn die (Programmier-) Sprache keine Befehle für Schleifen anbietet (siehe XSLT). Spätestens dann musst du dich mit Rekursion vertraut machen.

- Änderungen
28.07.2008, Bei Rekursion mit Methode reicht return anstatt exit.