Station - Rekursion
Beispiel: Wie dreht man Wörter um?
Das Umdrehen von Wörtern soll jetzt mit einem Programm erledigt werden.
Iterativ zur Lösung
Die Grundidee einer iterativen Lösung besteht darin, ein neues Wort aufzubauen, indem Schritt für Schritt ein Zeichen im alten Wort entfernt und an die richtige Stelle im neuen Wort eingebaut wird. Das folgende Ablaufprotokoll verdeutlicht diesen Vorgang am Beispiel des Worts 'LEBEN'.
{neuesWort -> ''; altesWort -> 'LEBEN'} neuesWort = altesWort[0] + neuesWort altesWort = altesWort[1:] {neuesWort -> 'L'; altesWort -> 'EBEN'} neuesWort = altesWort[0] + neuesWort altesWort = altesWort[1:] {neuesWort -> 'EL'; altesWort -> 'BEN'} neuesWort = altesWort[0] + neuesWort altesWort = altesWort[1:] {neuesWort -> 'BEL'; altesWort -> 'EN'} neuesWort = altesWort[0] + neuesWort altesWort = altesWort[1:] {neuesWort -> 'EBEL'; altesWort -> 'N'} neuesWort = altesWort[0] + neuesWort altesWort = altesWort[1:] {neuesWort -> 'NEBEL'; altesWort -> ''}
Zur Verwaltung des neuen wie auch des alten Worts werden hier neue Variablen eingeführt. Mit Hilfe von Zuweisungen werden die Werte der Variablen schrittweise verändert. Der gesamte Ablauf lässt mit der Kontrollstruktur "Wiederholung" wie folgt modellieren:
Eingabe: wort altesWort = wort neuesWort = '' SOLANGE altesWort noch Zeichen enthält: füge das erste Zeichen von altesWort vorne in neuesWort ein entferne das erste Zeichen von altesWort Ausgabe: neuesWort
Dieses Ablaufmodell lässt sich mit einer imperativ definierten Funktion implementieren.
# Eingabe wort = input('Wort: ') # Verarbeitung altesWort = wort neuesWort = '' while len(altesWort) > 0: neuesWort = altesWort[0] + neuesWort altesWort = altesWort[1:] # Ausgabe print(neuesWort)
Rekursiver Ansatz
Wenn man auf Zuweisungen an Variablen verzichten will, benötigt man eine neue Idee zur Problemlösung. Diese besteht hier darin, das Problem schrittweise in ein strukturgleiches Problem zu reduzieren. Die folgende Reduktionskette verdeutlicht diesen Vorgang am Beispiel des Worts 'LEBEN'.
umdrehen('LEBEN') -> (umdrehen('EBEN') + 'L') -> ((umdrehen('BEN') + 'E') + 'L') -> (((umdrehen('EN') + 'B') + 'E') + 'L') -> ((((umdrehen('N') + 'E') + 'B') + 'E') + 'L') -> (((((umdrehen('') + 'N') + 'E') + 'B') + 'E') + 'L') -> ((((('' + 'N') + 'E') + 'B') + 'E') + 'L') -> (((('N' + 'E') + 'B') + 'E') + 'L') -> ((('NE' + 'B') + 'E') + 'L') -> (('NEB' + 'E') + 'L') -> ('NEBE' + 'L') -> 'NEBEL'
Beachte, dass hier keine Variablen eingeführt werden.
Es werden zwei Sorten von Problemreduktionsschritte ausgeführt. Zum einen werden Schritte ausgeführt, die das Problem auf eines in verkleinerter Form reduzieren. Beachte, dass der Wert des Terms sich bei einer solchen Problemreduktion nicht verändert.
Zum anderen wird ein Schritt ausgeführt, der schließlich das (kleinstmögliche) Problem direkt löst.
Die Problemreduktionsschritte lassen sich verallgemeinernd durch Reduktionsregeln beschreiben:
Fall 1: wort == '' umdrehen(wort) -> wort Fall 2: wort != '' umdrehen(wort) -> umdrehen(wort[1:]) + wort[0]
Dieses Reduktionsregelmodell lässt sich mit einer rekursiv definierten Funktion implementieren.
def umdrehen(wort): if len(wort) == 0: return wort else: return umdrehen(wort[1:]) + wort[0]
Mit einem Funktionsaufruf erhält man die Lösung zu einem vorgegebenen konkreten Problem.
>>> umdrehen('LEBEN') 'NEBEL'
Was ist eigentlich eine rekursive Problemreduktion?
Rekursive Problemreduktion ist eine Problemlösestrategie, bei der ein Problem
auf ein strukturgleiches Problem (in verkleinerter
Form) zurückgeführt wird.
Hier ein Beispiel:
Das Problem "Umdrehen der Zeichenkette 'LEBEN'
" können wir auf das
entsprechende Problem "Umdrehen der Zeichenkette 'EBEN'
" zurückführen.
Rekursive Funktionsdefinitionen
Eine rekursive Funktionsdefinition ist eine Funktionsdefinition, bei der die Funktion selbst im Funktionsterm benutzt wird.
Beispiel einer rekursiven Funktionsdefinition:
def umdrehen(wort): if len(wort) == 0: return wort else: return umdrehen(wort[1:]) + wort[0]
Bei der Auswertung von Funktionsaufrufen kommt es bei rekursiven Funktionsdefinitionen zur wiederholten Ausführung strukturgleicher Reduktionsschritte. Rekursion kann somit als Ersatz für die Kontrollstruktur "Wiederholung" benutzt werden.
Damit dieses Wiederholungskonzept terminiert, muss nach endlichen vielen Reduktionsschritten eine Situation (der sog. Rekursionsanfang) erreicht werden, bei der die Lösung zum Problem direkt angegeben werden kann.
Man versucht daher, Reduktionsschritte so zu konzipieren, dass sie das Problem in einer Weise "verkleinern", die nur endlich viele Verkleinerungsschritte zulässt. Im oben gezeigte Beispiel besteht die Verkleinerung darin, die Länge der Zeichenkette um 1 zu reduzieren. Nach endlich vielen Reduktionsschritten kommt man so sicher zur leeren Zeichenkette.
Rekursion ist eine mächtige und gerne genutzte Strategie beim Problemlösen. Wenn der Problemkontext es zulässt, dann kann man das Problemlöseverfahren sehr einfach und kompakt über eine Problemreduktion beschreiben. Die wiederholte Ausführung der Reduktionsschritte - und damit die Erzeugung der eigentlichen Lösung - überlässt man dem Ausführsystem.
Aufgabe 1
Führe die folgende Funktion mit geeigneten Funktionsaufrufen aus und erkläre die produzierten Ausgaben.
def umdrehen(wort): print('Uebergabe:', wort) if len(wort) == 0: ergebnis = wort else: ergebnis = umdrehen(wort[1:]) + wort[0] print('Rueckgabe:', ergebnis) return ergebnis
Aufgabe 2
Noch eine rekursive Funktionsdefinition! Kannst du vorhersagen, welche Ausgaben bei der Auswertung
des Funktionsaufrufs verarbeiten('TOR')
hier gemacht werden? Überprüfe deine Vermutung.
def verarbeiten(wort): print('Uebergabe:', wort) if len(wort) == 0: ergebnis = wort else: ergebnis = wort[0] + wort[0] + verarbeiten(wort[1:]) print('Rueckgabe:', ergebnis) return ergebnis