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,

Die rekursive Definition ist:

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)