Python Tutorial, Teil 7

Rekursionen und reguläre Ausdrücke

| Autor / Redakteur: Thomas Drilling / Stephan Augsten

Rekursionen lassen sich in nahezu jeder Programmiersprache abbilden, wir sehen uns die Möglichkeiten von Python an.
Rekursionen lassen sich in nahezu jeder Programmiersprache abbilden, wir sehen uns die Möglichkeiten von Python an. (Bild: Drilling / Python.org)

Komplexere Datenstrukturen, Operationen und Programmiertechniken bilden den nächsten Schritt in der Python-Programmierung. Rekursive Funktionen und reguläre Ausdrücke bilden in diesem Teil unseres Python-Tutorials den Schwerpunkt.

In den vergangenen Teilen haben wir den grundlegenden Aufbau von Python-Programmen, die wichtigsten Tools, elementare Datenstrukturen, essentielle Operationen, Modulen Bibliotheken und wiederverwendbarem Code sowie die Grundzüge funktionaler Programmierung in Python kennengelernt. Im Folgenden widmen wir uns rekursiven Funktionen und regulären Ausdrücken, Teil 8 behandelt dann Mengen und den Lambda-Operator.

Rekursive Funktionen in Python

Rekursionen gibt es in nahezu jeder Programmiersprache. Hierbei handelt es sich um eine Programmiertechnik, in der eine Funktion sich selbst ein oder mehrmals im eigenen Funktionskörper (body) aufruft.

Um eine rekursive Funktion überhaupt in einem Programm verwenden zu können, muss sie terminieren. Das tut sie dann, wenn das Problem mit jedem Rekursionsschritt reduziert wird, bzw. sich in Richtung auf eine Abbruchbedingung zu „bewegt“. Diese ist dann erreicht, wenn die Funktion sich nicht mehr selbst aufruft.

Ein beliebtes Beispiel aus der Mathematik ist die Fakultätsfunktion. Bestimmt man z. B. den Wert von 5! rekursiv, wäre

5!=5x4!, 4!=4*3!, 3!=3*2!, 2!=2*1! und 1!=1 (da 1! per Definition 1 ist) = 5*4*3*2*1 = 120.

Hierbei liefert die Fakultätsfunktion für das Argument 1 den Wert 1 zurück, ohne dass zur Berechnung ein weiterer rekursiver Aufruf erforderlich ist. Eine rekursive Funktion kann in eine Endlosschleife führen, wenn das Abbruchkriterium nicht erreicht wird. Wie schaut das Ganze jetzt in Python aus? Dazu erinnern wir uns unseres Beispiels aus Teil 3 mit der rein funktionalen Umsetzung unsere Fibonacci-Folge. Diese kann man iterativ und rekursiv programmieren:

Iterativ: Wir starten mit zwei Einsern. Die weiteren Elemente ergeben sich, indem man jeweils die Summe der beiden letzten anfügt.

Rekursiv: Jedes Element ist laut Formel die Summe der beiden vorherigen Elemente. Wir verschieben also die Aufgabe der Berechnung von F(n) auf die Berechnung von F(n-1) und F(n-2), von zwei gleichartigen aber einfacheren Aufgaben, ab. F(2) und F(1) sind bekannt, weil vorgegeben.

def fibo1(n):   # Gibt Fibonacci-Reihe bis n aus.
   x, y = 0, 1
      while y < n:
      print (y, end=" ")
      x, y = y, x+y

fibo1(100)

Rekursiv implementiert sähe das Ganze so aus

def fibo2(n):
   if n == 0:
      return 0
   elif n <= 2:
      return 1
   else:
      return fibo2(n-1) + fibo2(n-2)

Der Vorteil der rekursiven Implementierung besteht vorrangig in der exakten Übertragbarkeit der mathematischen Definition. Allerdings sind die Unterschiede im Laufzeitverhalten beider Implementierungen beträchtlich. Während die „normale“, iterativ implementierte Variante 1 nahezu sofort das Ergebnis liefert, braucht die rekursive Variante mit einem Parameterwert von 20 je nach unterliegender Plattform schon Minuten.

Rekursive Funktionen sind also prinzipiell langsamer. Um das zu verstehen, muss man sich nur anschauen, wie „oft“ die Funktionen im Beispiel fibo2(100) aufgerufen wird. Zum Berechnen von fibo2(20) ruft diese fibo2(19) und fibo2(18) auf. Da diese Werte unbekannt sind, müssen fibo2(18) und fibo2 (17) für fibo2(19) und fibo2(17) sowie fibo2(16) für fibto2(18) berechnet werden usw.

Möchte man mit diesem Algorithmus fibo2(20) berechnen, wird fibo2(3) 2584 Mal neu berechnet, d. h. der Zeitbedarf für den Algorithmus wächst mit wachsendem n exponentiell. Abhilfe schafft es, die berechnete Werte in einer dynamischen Liste (dictionary) zwischenzuspeichern, quasi eine Erinnerungsfunktion. Das könnte etwa so aussehen:

memory = {0:0, 1:1}
def fibm(n):
   if not n in memory:
      memory[n] = fibm(n-1) + fibm(n-2)
   return memory[n]

Reguläre Ausdrücke

In Programmiersprachen kommen reguläre Ausdrücke in der Regel zum Filtern von Texten oder Strings zum Einsatz und helfen z. B. bei der Prüfung, ob ein Text oder ein String zu einem regulären Ausdruck passt ("matched"). Auch bei Textersetzungen kommen reguläre Ausdrücke zum Einsatz. Die entsprechende Syntax ist in allen Programmiersprachen und Skriptsprachen identisch, egal ob es sich um Python, Perl, Java, SED, AWK oder C# handelt. Auch viele Texteditoren wie vi kommen mit regulären Ausdrücken zurecht.

Wir kennen aus dem zweiten Teil dieses Tutorials im Zusammenhang mit sequenziellen Datentypen bereits den „in“-Operator, mit dem man herausfindet, ob ein String in einer anderen Zeichenkette enthalten ist.

>>> x = "Python Tutorial Teil 7"
>>> "Tutorial" in x
True
>>>

Reguläre Ausdrücke ermöglichen noch wesentlich weiterführende String-Vergleiche. Möchte man in Python reguläre Ausdrücke verwenden, muss zunächst das Modul „re“ importiert werden. Hierbei handelt es sich um eine weitere Standardbibliothek, welche eine Reihe von Funktionen und Methoden zum Verwenden regulärer Ausdrücke bereitstellt. Wichtig ist zu wissen, dass zahlreiche Zeichen „innerhalb“ von regulären Ausdrücken Sonderbedeutungen haben, etwa der Backslash.

Ganz allgemein werden reguläre Ausdrücke in Python als Strings dargestellt, wobei allerdings Backslashes in Form von Escape-Zeichen eingesetzt werden müssen. Will man verhindern, dass Blackslashes aus regulären Ausdruck entfernt werden bzw. mit dem jeweils folgenden Zeichen eine Sonderbedeutung erhalten, muss man jeden Backslash eines regulären Ausdrucks als doppelten Backslash "\\" schreiben. Da dies die Ausdrücke immer komplexer macht, kann man auch Raw-Strings verwenden, indem man dem String mit einem vorgestellten markiert: So passt etwa folgende regulärer Ausdruck …

r"^P.*\.py$"

… z. B. auf alle Dateinamen (die ja Zeichenketten/Strings sind), die mit einem großen "P" beginnen und mit ".py" enden. Die einfachste vorstellbare Forme eines regulären Ausdrucks ist diejenige, die überhaupt keine Metazeichen (Funktionszeichen) mit Sonderbedeutungen enthält. So matched z. B. r"Pyt" die Zeichenkette: "Dies ist Teil 7 unseres Python Tutorials“. Weiter kann man durch eckige Klammern "[", "]" eine Zeichenauswahl definieren, wobei der Ausdruck „in“ den eckigen Klammern dann für genau ein Zeichen aus dieser Auswahl steht. So matched z. B. der Ausdruck ...

r"M[ae][iy]er

... vier verschiedene Schreibweisen des Familiennamens Meier (Meyer, Maier, Mayer). Allerdings spielt es hierbei keine Rolle ob sich der Name am Anfang, im Inneren oder am Ende eines Strings befindet.

Reguläre Ausdrücke ermöglichen äußerst detaillierte und bedarfsgerechte String-Vergleiche.
Reguläre Ausdrücke ermöglichen äußerst detaillierte und bedarfsgerechte String-Vergleiche. (Bild: Drilling)

Was aber, wenn nur am Anfang des Strings gesucht werden sollen? Dazu stellt das re-Modul von Python z. B. die beiden Funktion search() und match() zur Verfügung, wobei Letztere nur prüft, ob eine Übereinstimmung am Anfang des String vorliegt.

>>> import re
>>>
>>> x1 = "Mayer verfasst einen Python Workshop"
>>>
>>> x2 = "Dr. August Mayer ist nämlich Journalist und Programmierer."
>>>
>>>
>>> print(re.search(r"M[ae][iy]er", x1))
<re.Match object; span=(0, 5), match='Mayer'>
>>>
>>> print(re.match(r"M[ae][iy]er", x1))
<re.Match object; span=(0, 5), match='Mayer'>
>>>
>>> print(re.search(r"M[ae][iy]er", x2))
<re.Match object; span=(11, 16), match='Mayer'>
>>>
>>> print(re.match(r"M[ae][iy]er", x2))
None
>>>

Laut Duden gibt es für die Schreibweisen des Namens Maier noch deutlich mehr Varianten, als die vier bisher Beschriebenen. Allerdings müssten man für einen erfolgreichen Match auch optionale Zeichen erfassen oder auslassen können, um etwa auch „Mayr“ zu erfassen. Um die Aufgabenstellung zu lösen, ist es erforderlich, mit Hilfe des Fragezeichens in der Syntax der regulären Ausdrücke eine Sonderbedeutung auszudrücken. So erreicht man mit "e?", dass der Buchstabe „e“ vorkommen kann aber nicht muss.

r"M[ae][iy]e?r"

Steht ein Fragezeichen hingegen hinter einer runden Klammer, kann der komplette Unterausdruck innerhalb der Klammern vorkommen, muss es aber nicht zwingend, etwa in …

r"Sep(ember)? 2018"

Anstelle einzelner Buchstaben, wie z. B. einer zwischen "i" oder "y" (in RE-Notation [iy]), braucht man häufig eine Auswahl zwischen kompletten Zeichenklassen, etwa eine Ziffer zwischen "0" und "9" oder einen Buchstaben zwischen "a" und "z". Daher gibt es für reguläre Ausdrücke mit dem Bindestrich ein reserviertes Sonderzeichen innerhalb der Zeichenauswahl. So ist [a-z] ist eine abgekürzte Schreibweise für [abcdefghijklmnopqrstuvwxyz] und [0-9] steht für [0123456789].

So ist es unübersehbar deutlich effizienter, [a-z] statt [abcdefghijklmnopqrstuvwxyz] schreiben zu können. Möchte man etwa im Rahmen eines Password-Parsing eine Zeichenauswahl beliebiger Klein- oder Großbuchstaben" erzwingen, klappt das sehr einfach mit [A-Za-z].

Vordefinierte Zeichenklassen

Es kann aber auch mit dem Bindestrich noch mühselig sein, Zeichenklassen für den gewünschten Einsatzzweck zu bilden. Daher gibt es in Python für häufig vorkommende Zeichenklassen vordefinierte Kürzel, wie:

\d – Eine Ziffer, entspricht [0-9].

\D – das Gegenteil von \d, d. h. sämtliche Zeichen mit Ausnahme der Ziffern [^0-9].

\s – Ein Whitespace, wie z. B. Leerzeichen, Tabs, Newlines [ \t\n\r\f\v].

\S – Gegenteil von \s, also alles außer Whitespace [^ \t\n\r\f\v].

\w – Alphanumerisches Zeichen plus Unterstrich, also [a-zA-Z0-9_]. Ist LOCALE gesetzt, matched die Klasse auch noch die speziellen Zeichen der LOCALE wie etwa Umlaute.

\W – Das Gegenteil von \w.

\b – Matched auf den leeren String, allerdings nur dann, wenn dieser am Anfang oder Ende eines Strings ist.

\B – Passt wie \b auf den leeren String, aber nur, wenn dieser nicht am Anfang oder Ende eines Strings ist.

Kommentare werden geladen....

Kommentar zu diesem Artikel

Anonym mitdiskutieren oder einloggen Anmelden

Avatar
  1. Avatar
    Avatar
    Bearbeitet von am
    Bearbeitet von am
    1. Avatar
      Avatar
      Bearbeitet von am
      Bearbeitet von am

Kommentare werden geladen....

Kommentar melden

Melden Sie diesen Kommentar, wenn dieser nicht den Richtlinien entspricht.

Kommentar Freigeben

Der untenstehende Text wird an den Kommentator gesendet, falls dieser eine Email-hinterlegt hat.

Freigabe entfernen

Der untenstehende Text wird an den Kommentator gesendet, falls dieser eine Email-hinterlegt hat.

copyright

Dieser Beitrag ist urheberrechtlich geschützt. Sie wollen ihn für Ihre Zwecke verwenden? Infos finden Sie unter www.mycontentfactory.de (ID: 45305300 / Frameworks & Sprachen)