25. Rekursion

Wir brauchen jetzt eine Funktion, die deriveLeft so aufruft, dass am Schluss alle möglichen Ableitungen erzeugt wurden. Sie soll ein Wort bekommen und für alle Wörter, die sich daraus ableiten lassen, eine neue Ableitung starten.

Überlegen wir uns zunächst wieder Pseudocode dafür:

Funktion generiereSprache

Eingabe: Ein Wort w, eine Regelmenge R

Wenn w nur aus Terminalen besteht

gib w aus
sonst
für alle möglichen direkten Linksableitungen w‘ von w
rufe generiereSprache mit w‘ und R auf

Eine direkte Linksableitung ist dabei das, was wir in deriveLeft erzeugt haben: Ein Wort, das durch Ersetzung des am weitesten links stehenden Nichtterminals im Quellwort entsteht.

Die Ableitungsfunktion ruft sich hier selbst für jede neu erzeugte Ableitung auf: Rekursion. Bei jeder Rekursion ist es wichtig, eine Abbruchbedingung zu haben, damit sich die Funktion nicht endlos selbst aufruft. In unserem Pseudocode ist die Abbruchbedingung, dass das Wort nur aus Terminalsymbolen besteht – es werden dann keine weiteren rekursiven Aufrufe gemacht. Es ist bei jedem rekursiven Algorithmus entscheidend, nachweisen zu können, dass die Abbruchbedingung früher oder später wahr wird, denn endlose Rekursion führt in jedem Fall zu einem zu einem Programmfehler. Häufig ist das kein großes Problem, denn normalerweise besteht ein Rekursionsschritt aus einer Zurückführung einer komplizierteren Aufgabe auf eine einfachere (” Lösung für n+ 1 auf Lösung für n„).

In unserem Fall ist das leider nicht so, und in der Tat wird unsere Abbruchbedingung für die viele Sprachen (nämlich die, die beliebig viele Wörter generieren können), nicht wahr. Um dennoch zu einem Abbruch zu kommen, fügen wir in den Code eine weitere Abfrage auf die Länge der Ableitung ein:

def isTerminal(word):
  return not getLeftmostNonTerm(word)

def generate(curWord, rules, maxLen):
  if len(curWord)>maxLen:
    return
  if isTerminal(curWord):
    print curWord
    return
  for deriv in deriveLeft(curWord, rules):
    generate(deriv, rules, maxLen)

Die Definition von isTerminal mag albern erscheinen. Wir werden aber später die Definition von Terminalsymbolen ändern. Wenn so eine Änderung passiert – und das ist in Softwareprojekten die Regel –, müssen wir nicht jeden Aufruf von isupper durchsehen, ob er zufällig eigentlich prüft, ob wir ein nur aus Terminalen bestehendes Wort haben, sondern müssen nur die Definition von isTerminal ändern.

Die Funktion generate ist eigentlich einfach: Zunächst wird die Abbruchbedingung überprüft, dann wird, wenn wir bereits ein Wort nur aus Terminalen haben, es ausgegeben und die Rekursion ebenfalls abgebrochen. Ansonsten gehen wir einfach die von deriveLeft gelieferten Ableitungen durch und leiten weiter ab.

Test:

>>> from gener1 import *
>>> generate("S", rules, 6)
b
aba
aabaa

Rekursion wirkt anfangs manchmal ein wenig magisch. Sehen wir uns an, wie die Rekursion hier abgelaufen ist:

Der Klassiker beim Einführen der Rekursion ist die Fakultät,

n! = 1 ⋅ 2 ⋅ 3 ⋅⋅⋅n.

Die rekursive Definition ist:

{
n! =   1           n = 0
       n(n -  1)!  sonst

Sie ist unter anderem deshalb ein Klassiker, weil es hier einfacher ist, die Rekursion zu durchschauen. Jeder Funktionsaufruf (mit Ausnahme des letzten) erzeugt nämlich wieder genau einen Funktionsaufruf.

In Python:

def fak(n):
  if n==0:
    return 1
  else:
    return n*fak(n-1)

Übungen zu diesem Abschnitt

Ihr solltet euch wenigstens an den rötlich unterlegten Aufgaben versuchen

(1)

Schreibt eine iterative Fassung der Fakultätsfunktion, d.h. eine, die die Fakultät in einer Schleife durch fortgesetzte Veränderung einer Variable berechnet. Macht euch vorher klar, warum dabei die Konvention, dass range(n) die Zahlen von 0 bis n- 1 zurückgibt, euer Leben auf doppelte Art schwer macht. Hinweis: Man kann range auch mit zwei Argumenten aufrufen. Das erste ist dann der Startwert der resultierenden Sequenz, das zweite der Endwert plus eins.

(2)

Nehmt die rekursive Implementation der Fakultät oben und spickt sie so lange mit print-Statements, bis ihr versteht, was vor sich geht.

(3)

Nehmt die Abfrage auf die Länge der Ableitung aus generate heraus und lasst sie mit unserer Standardgrammatik laufen. Was passiert? Ändert sich das, wenn ihr die einfache Ausdrucksgrammatik nehmt?


Markus Demleitner

Copyright Notice