Übungen
Übung 1
Du hast jetzt einige Probleme der Informatik und Mathematik kennengelernt, die man rekursiv lösen kann. Tatsächlich stößt man auch im Alltag ab und zu auf Rekursion und kann einige Alltagssituationen "rekursiv" lösen.
- Nenne Alltagssituationen, in denen du Rekursion schonmal begegnet bist. Denk dabei zum Beispiel an deinen Schulalltag oder deinen Alltag zuhause.
- Nenne Probleme aus dem Alltag, die man mit einer rekursiven Strategie lösen kann.
Übung 2
In Python können wir nicht nur Zahlen miteinander addieren, sondern auch Strings. Dabei ist die Summe zweier Strings die Aneinanderreihung oder Verkettung der beiden Strings. Dazu sagen wir auch Konkatenation.
Erneut schauen wir uns die Funktion zum Aufsummieren aller Elemente einer Liste an. Diesmal wollen wir allerdings keine Liste von Zahlen aufsummieren, sondern Strings. Die folgende Implementierung hat allerdings einen Fehler und muss angepasst werden. Finde heraus wo der Fehler liegt und korrigiere ihn. Warum ist die ursprüngliche Implementierung falsch?
def sum_list (l):
if (len(l) == 0):
return 0
else:
return l[0] + sum_list(l[1:])
print(sum_list(["a", "b", "c"]))
print(sum_list(["h", "a", "l", "l", "o"]))
print(sum_list(["w", "e", "l", "t"]))
#print(sum_list(_dein_Beispiel_hier_))
Übung 3
Am Anfang der Lernstrecke hast du die Funktion
quersumme Funktion kennengelernt. Nun wollen wir die Funktion einmal programmieren.
Beispiele:
-
quersumme(1)= 1 -
quersumme(12)= 3 -
quersumme(123)= 6 -
quersumme(1234)= 10
Überlege dir zunächst die Antworten auf die folgenden zwei Fragen. Hinweis: Eventuell sind die dabei die Operationen Modulo (%) und Division (//) hilfreich.
- Wie kommst du an die einzelnen Ziffern der Zahl?
- Wie verkürzt du die Zahl um eine Ziffer?
Schreibe nun mit diesen Überlegungen die Funktion.
def quersumme (n):
# Dein Code hier
print(quersumme(1))
print(quersumme(12))
print(quersumme(123))
print(quersumme(1234))
#print(quersumme(_dein_Beispiel_hier_))
Übung 4
Das Collatz-Problem, auch bekannt als (3n + 1)-Vermutung, ist ein faszinierendes ungelöstes Problem in der Mathematik. Die Idee ist, eine Folge von Zahlen zu generieren, beginnend mit einer beliebigen positiven ganzen Zahl n:
-
Wenn
ngerade ist, ist die nächste Zahln / 2. -
Wenn
nungerade ist, ist die nächste Zahl3n + 1.
Die Vermutung besagt, dass diese Folge für jede positive Startzahl n irgendwann die Zahl 1 erreicht.
Schreibe die rekursive Funktion
collatz_steps(n), die für die gegebene Startzahl n die Anzahl an Schritten (engl. steps) berechnet, bis die Sequenz bei 1 angelangt ist. Ersetze dafür die Fragezeichen mit Python Code. Wir legen fest, dass die Funktion nie mit 0 aufgerufen wird, diesen Fall musst du also nicht beachten.
Beispiele:
-
collatz_steps(1)= 0 -
collatz_steps(2)= 1, Sequenz: 2 $\to$ 1 -
collatz_steps(3)= 7, Sequenz: 3 $\to$ 10 $\to$ 5 $\to$ 16 $\to$ 8 $\to$ 4 $\to$ 2 $\to$ 1 -
collatz_steps(4)= 2, Sequenz: 4 $\to$ 2 $\to$ 1 -
collatz_steps(5)= 5, Sequenz: 5 $\to$ 16 $\to$ 8 $\to$ 4 $\to$ 2 $\to$ 1
def collatz_steps (n):
if (?????):
return 0
elif (?????):
return ????? collatz_steps(n // 2)
else:
return ????? collatz_steps(3 * n + 1)
print(collatz_steps(1))
print(collatz_steps(2))
print(collatz_steps(3))
print(collatz_steps(4))
print(collatz_steps(5))
#print(collatz_steps(_dein_Beispiel_hier_))
Hinweis: Obwohl die Collatz-Vermutung für alle bisher getesteten Zahlen zutrifft, ist sie mathematisch noch nicht bewiesen. Das bedeutet, es gibt theoretisch die Möglichkeit (wenn auch sehr unwahrscheinlich), dass für eine bestimmte sehr große Zahl die Folge nicht bei 1 endet. In einem solchen Fall würde die rekursive Funktion theoretisch unendlich weiterlaufen und schließlich zu einem Fehler führen, da Python eine maximale Rekursionstiefe hat. Für die üblichen Testzahlen ist das aber kein Problem.
Übung 5
Schreibe nun die rekursive Funktion
collatz_sequence(n), die für die gegebene Zahl n die Sequenz (engl. sequence) aus Zahlen in Form einer Liste berechnet und zurückgibt. Wir legen wieder fest, dass die Funktion nie mit 0 aufgerufen wird, diesen Fall musst du also nicht beachten.
Beispiele:
-
collatz_sequence(1)= [1] -
collatz_sequence(2)= [2, 1] -
collatz_sequence(3)= [3, 10, 5, 16, 8, 4, 2, 1] -
collatz_sequence(4)= [4, 2, 1] -
collatz_sequence(5)= [5, 16, 8, 4, 2, 1]
def collatz_sequence (n):
# Dein Code hier
print(collatz_sequence(1))
print(collatz_sequence(2))
print(collatz_sequence(3))
print(collatz_sequence(4))
print(collatz_sequence(5))
#print(collatz_sequence(_dein_Beispiel_hier_))
Übung 6
Schreibe eine rekursive Funktion
is_Exp_2(n), die für eine gegebene natürliche Zahl n überprüft, ob es eine natürliche Zahl x gibt, sodass $2^x = n$. Anders gesagt soll überprüft werden, ob n eine Zweierpotenz ist.
Beispiele:
-
is_Exp_2(1)=True -
is_Exp_2(2)=True -
is_Exp_2(3)=False -
is_Exp_2(4)=True -
is_Exp_2(5)=False -
is_Exp_2(8)=True
Tipp
Eventuell benötigst du zwei Basisfälle.
def is_Exp_2 (n):
# Dein Code hier
print(is_Exp_2(1))
print(is_Exp_2(2))
print(is_Exp_2(3))
print(is_Exp_2(4))
print(is_Exp_2(5))
print(is_Exp_2(8))
#print(is_Exp_2(_dein_Beispiel_hier_))
