Python 3 - Lernen und professionell anwenden

Kapitel 6

Funktionen

174

In Zeile #1 werden durch Aufruf der Methode upper() die Zeichen des Strings text in lau-

ter Großbuchstaben umgewandelt. Die Methode

count() liefert eine Zahl, die angibt, wie

häufig das Zeichen

buchstabe im String text vorkommt (#2). Mithilfe der Länge von Text

wird daraus die relative Häufigkeit berechnet und zurückgegeben.

In der

if-Anweisung der Funktion deutsch() in Zeile #3 wird geprüft ob die relativen Häu-

figkeiten der Zeichen

a, e und y in gewissen Grenzen liegen. Wenn das der Fall ist, wird

True zurückgegeben, sonst False.

Beispiel für einen Programmlauf:

6.8 Rekursive Funktionen

»Recursion is an order of magnitude more complicated than repetition.«

Dijkstra

# deutsch.py

def deutsch (s):

def h(text, buchstabe):

text.upper() #1

anzahl = text.count(buchstabe) #2

relativeHaeufigkeit = float(anzahl)*100/len(text)

return relativeHaeufigkeit

# Ende def h

if (4<h(s,"a")<9) and (14<h(s,"e")<20) and (h(s,"y")<1): #3

return True

else:

return False

# Ende def deutsch

text = input("Text: ")

if deutsch(text):

print("vermutlich deutsch")

else:

print("vermutlich nicht deutsch")

Text: Damit ein Text einigermassen sicher als deutsch oder nicht deutsch

erkannt wird, muss er bei diesem einfachen Programm ziemlich lang sein.

Man kann sich leicht ausrechnen, dass der Text auf Grund der Streuung

der Vorkommenshaeufigkeiten ueber mehrere Seiten gehen muss. Einzelne

Zeilen reichen nicht aus.

vermutlich deutsch

175

6.8

Rekursive Funktionen

Eine rekursive Funktion ist eine Funktion, die sich selbst aufruft. Der Begriff Rekursion lei-

tet sich vom lateinischen Wort recurrere ab, was unter anderem wiederkehren bedeutet. Die

Idee der Rekursion kann man sich an folgender Alltagssituation klar machen.

Sie befinden sich in einer fremden Stadt und fragen Leute auf der Straße nach dem Weg

zum Bahnhof. Je nach Ihrem Standort können Sie z.B. folgenden Antworten bekommen:

쐽 Antwort 1: »Drehen Sie sich doch mal um! Sie stehen bereits davor!«

쐽 Antwort 2: »Gehen Sie diese Straße entlang, an der nächsten Ampel rechts und dann fra-

gen Sie noch mal jemanden.«

Durch Antwort 1 wurde Ihr Problem »Wie komme ich zum Bahnhof?« direkt gelöst. Ant-

wort 2 ist noch keine Lösung, aber es bringt Sie der Lösung etwas näher. Wenn Sie den

beschriebenen Weg gelaufen sind, müssen Sie noch einmal Ihren Problemlösungsalgorith-

mus anwenden – nämlich jemanden fragen –, aber jetzt ist das Problem kleiner. Denn Sie

sind näher am Bahnhof, der Weg dorthin ist nicht mehr so kompliziert und der Befragte

muss vermutlich nicht mehr so lange nachdenken, um Ihnen weiterhelfen zu können. Nach

mehreren Anfragen wird dann irgendwann die Situation eintreten, dass man Ihnen den

Bahnhof direkt zeigen kann (Antwort vom Typ 1). Die Rekursion endet.

Zu einer rekursiven Problemlösung gehören also zwei Teile:

쐽 Falls das Problem einfach genug ist, löse es direkt (Elementarfall).

쐽 Anderenfalls tue so, als hättest du bereits einen Lösungsalgorithmus für eine einfachere

Version des Problems. Konstruiere damit eine Lösung für das komplexere Problem.

Wenn der Elementarfall fehlt, haben wir es mit einer Endlosrekursion zu tun. Der Prozess

der Problemlösung endet niemals und läuft bis in alle Ewigkeit. Auch hierfür gibt es im All-

tagsdenken Beispiele:

쐽 Denken Sie einen Moment über folgenden Satz nach:

»Meine Vorfahren sind meine Eltern und die Vorfahren meiner Eltern.«

Offensichtlich hat man durch diesen kurzen Satz eine unendlich große Perso-

nengruppe beschrieben. Die Definition ist rekursiv, weil der Begriff »Vorfahre«

verwendet wurde, um sich selbst zu definieren.

쐽 Wenn Sie sich zwischen zwei parallele, einander gegenüberstehende Spiegel stellen,

erleben Sie eine Endlosrekursion: Sie sehen das Spiegelbild des Spiegelbildes des Spie-

gelbildes ...

쐽 Zu einer Endlosrekursion kann es auch im Bereich zwischenmenschlicher Interaktion

kommen. Zwei Personen stehen sich einander gegenüber und fragen sich: Was denkt

der andere wohl, was ich denke, dass er denkt, was ich denke ...

Rekursion ermöglicht kurze und elegante Formulierungen für Problemlösungen. Hier zeigt

sich eine Stärke der Programmiersprache Python. Mit Python können Sie eine rekursive

Funktion so formulieren, dass die algorithmische Idee besonders deutlich wird. Sie werden

im weiteren Verlauf des Buches immer wieder auf rekursive Funktionen stoßen. Allerdings

ist die Arbeitsweise einer rekursiven Funktion anfangs nur schwer zu verstehen. Wenn Sie

mit der rekursiven Denkweise nicht vertraut sind, sollten Sie mit der Turtle-Grafik experi-

mentieren. Mehr dazu im folgenden Abschnitt.