seminar05.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Seminar Problemorientierte Programmierung\n",
    "\n",
    "## 5 Verzweigungen und Rekursion\n",
    "\n",
    "Das erste Thema dieses Kapitels ist die `if`-Anweisung, die unterschiedlichen Code ausführt, je nach Zustand des Programms. Im zweiten Teil lernen Sie die `Rekursion` kennen.\n",
    "\n",
    "(Buch: http://greenteapress.com/thinkpython2/html/thinkpython2006.html)\n",
    "## Exkurs: Was mir an Python gefällt\n",
    "\n",
    "In dieser Rubrik, die immer am Anfang eines Kapitels steht, möchte ich Ihnen zeigen, wofür ich Python nutze und warum ich es mag. Sie werden vielleicht noch nicht verstehen, was ich genau mache, aber Sie sehen damit schon einmal die Möglichkeiten von Python und können später darauf zurückgreifen. Da dies auch ein Exkurs ist, können Sie diese Rubrik gerne auch erst einmal überspringen.\n",
    "\n",
    "Mit den Operatoren aus diesem Kapitel können wir ganz leicht das Verfahren zur Umwandlung einer Dezimalzahl in ihre Binärdarstellung implementieren:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Umwandlung einer positiven, ganzen Dezimalzahl in Binärdarstellung (als Zeichenkette)\n",
    "def dez_zu_bin(n):\n",
    "    ergebnis = \"\"\n",
    "    while n > 0:\n",
    "        ergebnis = str(n % 2) + ergebnis\n",
    "        n = n // 2\n",
    "    return ergebnis\n",
    "\n",
    "print(dez_zu_bin(42))\n",
    "\n",
    "# Und weil wir heute beim Thema Rekursion sind ...\n",
    "def dez_zu_bin_rekursiv(n):\n",
    "    if n == 0:\n",
    "        return \"\"\n",
    "    return dez_zu_bin_rekursiv(n // 2) + str(n % 2)\n",
    "\n",
    "print(dez_zu_bin_rekursiv(42))\n",
    "\n",
    "# Warum eigentlich auf ein Zahlensystem festlegen?\n",
    "def dez_zu_allem(n, s):\n",
    "    if n == 0:\n",
    "        return \"\"\n",
    "    return dez_zu_allem(n // len(s), s) + s[n % len(s)]\n",
    "\n",
    "print(dez_zu_allem(42, \"01\"))\n",
    "print(dez_zu_allem(42, \"0123456789\"))\n",
    "print(dez_zu_allem(42, \"01234567\"))\n",
    "print(dez_zu_allem(42, \"0123456789ABCDEF\"))\n",
    "print(dez_zu_allem(42, \"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.1 Ganzzahldivision und Restberechnung\n",
    "\n",
    "Der Operator `//` für die **Ganzzahldivision** teilt zwei ganze Zahlen und rundet das Ergebnis zu einer ganzen Zahl ab. \n",
    "\n",
    "Angenommen, wir wollen wissen, wie lang ein Film über 105 Minuten in Stunden dauert. Bei der üblichen Division erhalten wir eine Gleitkommazahl: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "minuten = 105\n",
    "minuten/60"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Aber normalerweise schreiben wir Stundenangaben nicht mit Dezimalpunkt. Mit der Ganzzahldivision können wir die Stunden als ganze Zahl berechnen, wobei abgerundet wird:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "minuten = 105\n",
    "stunden = minuten // 60\n",
    "print(stunden)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Um den Rest der Division zu berechnen, könnten wir eine Stunde in Minuten abziehen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rest = minuten - stunden * 60\n",
    "print(rest)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alternativ können wir auch den Operator `%` zur **Restberechnung** verwenden. Dieser teilt zwei ganze Zahlen und gibt uns den Rest zurück:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rest = minuten % 60\n",
    "print(rest)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dieser Operator ist nützlicher, als es auf den ersten Blick erscheinen mag. Beispielsweise können wir damit leicht prüfen, ob eine Zahl durch eine andere Zahl teilbar ist - wenn `x % y` gleich Null ist, dann ist `x` durch `y` teilbar.\n",
    "\n",
    "Außerdem können wir damit die am weitesten rechts liegende Ziffer einer Zahl extrahieren. Beispielsweise ergibt `x % 10` die am weitesten rechts liegende Ziffer von `x`, also die Einerstelle (in der Basis 10). Analog liefert uns `x % 100` die letzten beiden Ziffern:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "4711 % 100"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Berechnen Sie, wie viele Stunden und Minuten 1270 Minuten ergeben:  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "zeit = 1270\n",
    "\n",
    "# Fügen Sie hier den Code ein, um die Anzahl Stunden und Minuten zu berechnen\n",
    "\n",
    "print(zeit, \"Minuten entsprechen\", stunden, \"Stunden und\", minuten, \"Minuten\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```1270 Minuten entsprechen 21 Stunden und 10 Minuten``` ist die richtige Ausgabe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.2 Boolesche Ausdrücke\n",
    "\n",
    "Ein **Boolescher Ausdruck** ist ein Ausdruck, der entweder wahr oder falsch ist. Die folgenden Beispiele nutzen den `==`-Operator, der zwei Operanden vergleicht und `True` zurückliefert, falls Sie gleich sind, und ansonsten `False`: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "5 == 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "5 == 6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`True` und `False` sind zwei besondere Werte, die zum Datentyp `bool` gehören; sie sind keine Zeichenketten!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "type(True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "type(False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der `==`-Operator ist einer der sogenannten **relationalen Operatoren**; die anderen sind:\n",
    "\n",
    "```python\n",
    "x != y               # x ist ungleich y\n",
    "x > y                # x ist größer als y\n",
    "x < y                # x ist kleiner als y\n",
    "x >= y               # x ist größer oder gleich y\n",
    "x <= y               # x ist kleiner oder gleich y\n",
    "```\n",
    "\n",
    "Auch wenn Ihnen diese Symbole wahrscheinlich bekannt vorkommen, so sind sie doch anders als ihre mathematischen Äquivalente. **Ein üblicher Fehler ist, das einfache Gleichheitszeichen (`=`) statt des doppelten Gleichheitszeichens (`==`) zu verwenden.** Wir merken uns: `=` ist der Zuweisungsoperator und `==` ist ein relationaler Operator. Die Operatoren `=<` und `=>` gibt es nicht.\n",
    "\n",
    "![Note that this implies you should NOT honk solely because I stopped for a pedestrian and you&#39;re behind me.](https://imgs.xkcd.com/comics/formal_logic.png)\n",
    "\n",
    "([Formal Logic](https://xkcd.com/1033/), Randall Munroe)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.3 Logische Operatoren\n",
    "\n",
    "Es gibt drei **logische Operatoren**: `and`, `or` und `not`. Die Semantik (Bedeutung) dieser drei Operatoren ist ähnlich der Bedeutung der englischen Wörter. Beispielsweise ist `x > 0 and x < 10` genau dann wahr, wenn `x` größer als 0 *und* kleiner als 10 ist.\n",
    "\n",
    "`n%2 == 0 or n%3 == 0` ist wahr, wenn *eine oder beide* der Bedingungen wahr ist, das heißt wenn die Zahl `n` durch 2 *oder* drei teilbar ist.\n",
    "\n",
    "Genaugenommen sollten die Operanden der logischen Operatoren Boolesche Ausdrücke sein, aber Python erlaubt uns da mehr Freiheit. Jede Zahl ungleich Null wird als `True` interpretiert:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "42 and True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Diese Flexibilität kann nützlich sein, aber es gibt ein paar Feinheiten, die verwirrend sein könnten. Daher sollten Sie diese Variante eher vermeiden (außer, Sie wissen, was Sie tun)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.4 Verzweigungen\n",
    "\n",
    "Um nützliche Programme zu schreiben, benötigen wir fast immer die Möglichkeit, Bedingungen zu prüfen und das Verhalten des Programms entsprechend anzupassen. **Verzweigungen** ermöglichen uns dies. Die einfachste Form ist die `if`-Anweisung:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if x > 0:\n",
    "    print(x, 'ist eine positive Zahl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der Boolesche Ausdruck hinter `if` heißt **Bedingung**. Wenn die Bedingung wahr ist, wird die eingerückte Anweisung ausgeführt. Falls nicht, passiert nichts.\n",
    "\n",
    "Fügen Sie im folgenden Beispiel eine Anweisung vor der Verzweigung ein, so dass die Bedingung erfüllt ist: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if x % 2 == 0:\n",
    "    print(\"x ist eine gerade Zahl\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`if`-Anweisungen haben die gleiche Struktur wie Funktionsdefinitionen: ein (Verzweigungs-)Kopf, gefolgt von einem eingerückten (Verzweigungs-)Rumpf. Anweisungen dieser Art werden **Verbundanweisungen** genannt. \n",
    "\n",
    "Die Anzahl an Anweisungen, die im Rumpf stehen können, ist nicht begrenzt, aber es muss mindestens eine Anweisung sein. Manchmal ist es nützlich, einen Rumpf ohne Anweisungen zu haben (üblicherweise als Platzhalter für Code, den wir noch schreiben wollen). In diesem Fall können wir die **`pass`**-Anweisung verwenden, die nichts tut:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if x < 0:\n",
    "    pass     # TODO: Behandlung negativer Werte implementieren!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.5 Alternative Verzweigung\n",
    "\n",
    "Eine zweite Form der `if`-Anweisung ist die \"alternative Verzweigung\", bei der es zwei Möglichkeiten gibt und die Bedingung festlegt, welche davon ausgeführt wird. Die Syntax sieht folgendermaßen aus:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if x % 2 == 0:\n",
    "    print(\"x ist gerade\")\n",
    "else:\n",
    "    print(\"x ist ungerade\")   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wenn der Rest bei der Division von `x` durch 2 gleich Null ist, dann wissen wir, dass `x` eine gerade Zahl ist und das Programm gibt eine entsprechende Meldung aus. Wenn die Bedingung falsch ist, wird die zweite Anweisung ausgeführt. Da die Bedingung entweder wahr oder falsch sein muss, wird genau eine der Alternativen ausgeführt. Diese Alternativen werden **Zweige** genannt, denn sie erzeugen eine Verzweigung im Kontrollfluss. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.6 Verkettete Verzweigungen\n",
    "\n",
    "Manchmal gibt es mehr als zwei Möglichkeiten und wir benötigen mehr als zwei Zweige. Eine Möglichkeit eine Berechnung dieser Art auszudrücken, sind sogenannte **verkettete Verzweigungen**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if x < y:\n",
    "    print(x, 'x ist kleiner als', y)\n",
    "elif x > y:\n",
    "    print(x, 'ist größer als', y)\n",
    "else:\n",
    "    print(x, 'und', y, 'sind gleich')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`elif` ist eine Abkürzung für `else if`. Wieder wird nur genau ein Zweig ausgeführt. Es gibt keine Begrenzung für die Anzahl der `elif`-Anweisungen. Falls es einen `else`-Teil gibt, so muss dieser am Ende stehen, aber es muss keinen geben:\n",
    "\n",
    "```python\n",
    "if choice == 'a':\n",
    "    draw_a()\n",
    "elif choice == 'b':\n",
    "    draw_b()\n",
    "elif choice == 'c':\n",
    "    draw_c()\n",
    "```\n",
    "\n",
    "Jede Bedingung wird in der vorgegebenen Reihenfolge geprüft. Wenn die erste nicht erfüllt (falsch) ist, wird die nächste geprüft, und so weiter. Sobald eine der Bedingungen erfüllt (wahr) ist, wird der entsprechende Zweig ausgeführt und die `if`-Anweisung wird beendet. **Auch wenn mehr als eine Bedingung erfüllt ist, wird nur der erste zutreffende Zweig ausgeführt.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.7 Verschachtelte Verzweigungen\n",
    "\n",
    "Eine Verzweigung kann auch mit einer anderen verschachtelt sein. Wir könnten das Beispiel vom vorherigen Abschnitt auch so schreiben:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if x == y:\n",
    "    print(x, 'und', y, 'sind gleich')\n",
    "else:\n",
    "    if x < y:\n",
    "        print(x, 'ist kleiner als', y)\n",
    "    else:\n",
    "        print(x, 'ist größer als', y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die äußere Verzweigung hat zwei Zweige: \n",
    "- Der erste Zweig enthält eine einfache `print`-Anweisung.\n",
    "- Der zweite Zweig enthält eine weitere `if`-Anweisung, die selbst zwei Zweige hat. Diese beiden Zweige sind beide einfache Anweisungen; sie könnten aber ebenfalls Verzweigungen enthalten.\n",
    "\n",
    "Auch wenn die Einrückung der Anweisungen die Struktur offensichtlich macht, werden **verschachtelte Verzweigungen** schnell schwer lesbar. Daher ist es eine gute Idee, sie möglichst zu vermeiden.\n",
    "\n",
    "Boolesche Operatoren bieten uns oft die Möglichkeit, verschachtelte Verzweigungen zu vereinfachen. Beispielsweise können wir den folgenden Code in eine einfach Verzweigung umschreiben:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if 0 < x:\n",
    "    if x < 10:\n",
    "        print(x, 'ist eine positive einstellige Zahl.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die `print`-Anweisung wird nur ausgeführt, wenn beide Bedingungen erfüllt sind. Daher können wir den gleichen Effekt mit Hilfe des `and`-Operators erzeugen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if 0 < x and x < 10:\n",
    "    print(x, 'ist eine positive einstellige Zahl.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Für diese Art der Bedingung bietet Python sogar eine noch kürzere Schreibweise:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if 0 < x < 10:\n",
    "    print(x, 'ist eine positive einstellige Zahl.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Schreiben Sie die folgende verschachtelte Verzweigung so um, dass nur noch eine Verzweigung verwendet wird:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if x % 2 == 0:\n",
    "    if x % 4 == 0:\n",
    "        print(x, \"ist durch 2 und 4 teilbar\")\n",
    "else:\n",
    "    print(x, \"ist nicht durch 2 oder 4 teilbar\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Fügen Sie hier Ihren Code ein"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.8 Rekursion\n",
    "\n",
    "Um Rekursion zu verstehen, gehen Sie zu [Abschnitt 5.8](#5.8-Rekursion) und lesen Sie diesen.\n",
    "\n",
    "![I may have also tossed one of a pair of teleportation rings into the ocean, with interesting results.](https://imgs.xkcd.com/comics/tabletop_roleplaying.png) \n",
    "\n",
    "([Tabletop Roleplaying](https://xkcd.com/244/), Randall Munroe)\n",
    "\n",
    "Es ist erlaubt, dass eine Funktion eine andere aufruft; es ist auch erlaubt, dass die Funktion sich selbst aufruft. Es ist vielleicht nicht offensichtlich, warum das eine gute Idee ist, aber es ist eines der \"magischsten\" Dinge, die ein Program tun kann. Schauen wir uns beispielsweise die folgende Funktion an:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def countdown(n):\n",
    "    if n <= 0:\n",
    "        print(\"Abheben!\")\n",
    "    else:\n",
    "        print(n)\n",
    "        countdown(n-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wenn `n` Null oder negativ ist, gibt die Funktion \"Abheben!\" aus. Ansonsten wird `n` ausgegeben und eine Funktion `countdown` - die Funktion selbst - aufgerufen mit `n-1` als Argument. \n",
    "\n",
    "Was passiert wenn wir diese Funktion folgendermaßen aufrufen?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "countdown(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Ausführung von `countdown` beginnt mit `n=3`. Da `n` größer als 0 ist, wird der Wert 3 ausgegeben und die Funktion ruft sich selber auf ...\n",
    "- Die Ausführung von `countdown` beginnt mit `n=2`. Da `n`   größer als 0 ist, wird der Wert 2 ausgegeben und die Funktion ruft sich selber auf ...\n",
    "  - Die Ausführung von `countdown` beginnt mit `n=1`. Da `n` größer als 0 ist, wird der Wert 1 ausgegeben und die Funktion ruft sich selber auf ...\n",
    "    - Die Ausführung von `countdown` beginnt mit `n=0`. Da `n` nicht größer als 0 ist, wird \"Abheben!\" ausgegeben und zurückgesprungen.\n",
    "    \n",
    "    Die Funktion `countdown` mit `n=1` springt zurück.\n",
    "    \n",
    "  Die Funktion `countdown` mit `n=2` springt zurück.\n",
    "  \n",
    "Die Funktion `countdown` mit `n=3` springt zurück.\n",
    "\n",
    "Und damit sind wir zurück im `__main__`. Die Ausgabe des Aufrufs sieht damit so aus:\n",
    "\n",
    "```\n",
    "3\n",
    "2\n",
    "1\n",
    "Abheben!\n",
    "```\n",
    "\n",
    "Eine Funktion die sich selbst aufruft wird **rekursiv** genannt; der Vorgang wird **Rekursion** genannt.\n",
    "\n",
    "**Es ist wichtig, dass Sie dieses Beispiel verstanden haben. Falls das nicht der Fall sein sollte, lassen Sie es sich von Ihrem Partner, Kommilitonen oder Übungsleiter erklären.**\n",
    "\n",
    "Eine gute Hilfe ist außerdem diese Webseite: http://www.pythontutor.com.\n",
    "Dort können Sie ihren Python Code hochladen und Schritt für Schritt durchführen. \n",
    "Probieren Sie es mit der Funktion countdown() aus *(Achtung: Sie müssen die Funktion auch dort aufrufen)*.\n",
    "\n",
    "Als weiteres Beispiel schreiben wir eine Funktion, die eine Zeichenkette `n` mal ausgibt:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_n(s, n):\n",
    "    if n <= 0:\n",
    "        return\n",
    "    print(s)\n",
    "    print_n(s, n-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wenn `n <= 0` ist, dann beendet die **return-Anweisung** die Funktion. Der Kontrollfluss kehrt dann sofort zur aufrufenden Stelle zurück und die übrigen Anweisungen in der Funktion werden nicht ausgeführt. \n",
    "\n",
    "Der Rest der Funktion ist ähnlich zu `countdown`: `s` wird ausgegeben und dann ruft die Funktion sich selbst auf, um `s` `n-1` mal auszugeben. Die Anzahl der Zeilen die ausgegeben werden ist also 1 + (n - 1), was gleich `n` ist.\n",
    "\n",
    "Für solche einfachen Beispiele ist es wohl einfacher, eine `for`-Schleife zu verwenden. Aber wir werden später Beispiele sehen, die eher schwierig mit einer `for`-Schleife zu implementieren sind, jedoch sehr einfach mittels Rekursion. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.9 Stapeldiagramme für rekursive Funktionen\n",
    "\n",
    "In [Abschnitt 3.9](seminar03.ipynb#3.9-Stapel-Diagramme) haben wir Stapeldiagramme genutzt, um den Zustand eines Programms während eines Funktionsaufrufs zu repräsentieren. Die gleiche Art Diagramm kann uns helfen, eine rekursive Funktion zu interpretieren.\n",
    "\n",
    "Jedes Mal, wenn eine Funktion aufgerufen wird, erstellt Python einen Block, der die lokalen Variablen und Parameter der Funktion enthält. Für eine rekursive Funktion kann es zur gleichen Zeit mehrere Blöcke auf dem Stapel geben.\n",
    "\n",
    "Die folgende Abbildung zeigt ein Stapeldiagramm für den Aufruf von `countdown(3)`:\n",
    "\n",
    "![Stapel-Diagramm](https://amor.cms.hu-berlin.de/~jaeschkr/teaching/spp/stapeldiagramm_countdown.svg)\n",
    "\n",
    "Wie üblich, ist oben auf dem Stapel der Block für `__main__`. Dieser ist leer, denn wir haben in `main` keine Variablen erstellt oder Argumente übergeben.\n",
    "\n",
    "Die vier Blöcke für `countdown` haben unterschiedliche Werte für den Parameter `n`. Der Block am Boden des Stapels, wo `n=0` ist, wird **Basisfall** genannt. In diesem gibt es keinen rekursiven Aufruf, daher gibt es keine weiteren Blöcke. Dies ist gleichzeitig die **Abbruchbedingung** für die Rekursion.\n",
    "\n",
    "Zeichnen Sie als Übung ein Stapeldiagramm für `print_n`, wenn es mit `s = 'Hallo'` und `n = 2` aufgerufen wird. \n",
    "Schreiben Sie dann eine Funktion `do_n`, die ein Funktionsobjekt und eine ganze Zahl `n` als Parameter erwartet und dann die übergebene Funktion `n`-mal aufruft. *(Funktionsobjekte wurden im [3. Kapitel](seminar03.ipynb) erklärt und dort beispielsweise in [Aufgabe 2](seminar03.ipynb#Aufgabe-2) verwendet.)* \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# implementieren Sie hier die Funktion do_n\n",
    "def do_n(f, n):\n",
    "    if n<=0:\n",
    "        return\n",
    "    f\n",
    "    do_n(f,n-1)\n",
    "# eine Testfunktion\n",
    "def testfunktion():\n",
    "    print(\"Ich wurde aufgerufen!\")\n",
    "do_n(testfunktion(),5)\n",
    "# rufen Sie hier die Funktion do_n auf, indem Sie die Funktion testfunktion sowie den Wert 7 als Argument übergeben "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.10 Unendliche Rekursion\n",
    "\n",
    "Wenn die Rekursion niemals den Basisfall erreicht, werden immer wieder rekursive Aufrufe getätigt und das Programm wird nicht beendet. Dies wird **unendliche Rekursion** genannt und ist im Allgemeinen keine gute Idee. Das hier ist ein minimales Programm mit unendlicher Rekursion:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def recurse():\n",
    "    recurse()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In den meisten Ausführungsumgebungen läuft ein Programm mit unendlicher Rekursion nicht wirklich für immer. Python gibt uns eine Fehlermeldung aus wenn die maximale Rekursionstiefe erreicht ist:\n",
    "\n",
    "```\n",
    "Traceback (most recent call last):\n",
    "  File \"<stdin>\", line 1, in <module>\n",
    "  File \"<stdin>\", line 2, in recurse\n",
    "  File \"<stdin>\", line 2, in recurse\n",
    "                  .\n",
    "                  .\n",
    "                  .\n",
    "  File \"<stdin>\", line 2, in recurse\n",
    "RecursionError: maximum recursion depth exceeded\n",
    "```\n",
    "\n",
    "Dieser Traceback ist etwas größer als der, den wir im vorherigen Kapitel gesehen haben. Wenn der Fehler auftritt, befinden sich 1000 `recurse`-Blöcke auf dem Stapel!\n",
    "\n",
    "Wenn bei ihnen eine ungewollte unendliche Rekursion auftritt, überprüfen Sie Ihre Funktion und stellen Sie sicher, dass es einen Basisfall gibt, der keinen rekursiven Aufruf tätigt. Und wenn es einen Basisfall gibt, überprüfen Sie, ob er garantiert erreicht wird.\n",
    "\n",
    "![Mandelbrot Detail](https://upload.wikimedia.org/wikipedia/commons/thumb/b/b3/Mandel_zoom_07_satellite.jpg/800px-Mandel_zoom_07_satellite.jpg)\n",
    "\n",
    "([Wolfgang Beyer](https://commons.wikimedia.org/wiki/File:Mandel_zoom_07_satellite.jpg))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.11 Tastatur-Eingaben\n",
    "\n",
    "Die meisten Programme, die wir bisher geschrieben haben, akzeptieren keine Eingaben durch die Nutzerin. Sie erledigen jedesmal die gleiche Aufgabe. \n",
    "\n",
    "Python bietet eine eingebaute Funktion namens `input` die das Programm pausiert und darauf wartet, dass der Nutzer etwas eintippt. Wenn der Nutzer *Return* oder *Enter* drückt, fährt das Programm fort und `input` gibt was immer der Nutzer eingetippt hat als Zeichenkette zurück. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "text = input()\n",
    "print(text)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bevor man von der Nutzerin eine Eingabe bekommt, ist es eine gute Idee, einen Hinweis auszugeben, der der Nutzerin sagt, was Sie eintippen soll. Der Funktion `input` können wir einen solchen Hinweis als Argument übergeben: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "name = input(\"Wie lautet Ihr Name?\\n\")\n",
    "print(name)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Folge `\\n` am Ende des Hinweises repräsentiert einen **Zeilenumbruch** - ein spezielles Zeichen, welches einen Zeilenumbruch bewirkt. Aus diesem Grund erscheint die Eingabe des Nutzers unter dem Hinweis.\n",
    "\n",
    "Falls wir erwarten, dass der Nutzer eine ganze Zahl eintippt, können wir versuchen, die Eingabe in eine ganze Zahl umzuwandeln:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "prompt = \"Wie hoch ist die Fluggeschwindigkeit einer unbeladenen Schwalbe?\\n\"\n",
    "speed = input(prompt)\n",
    "int(speed)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wenn der Nutzer etwas anderes als eine Zeichenkette mit Ziffern eintippt, erhalten wir einen Fehler:\n",
    "\n",
    "```\n",
    "ValueError: invalid literal for int() with base 10: 'Eine afrikanische oder eine europäische Schwalbe?'\n",
    "```\n",
    "\n",
    "Wir werden später sehen, wie wir diese Art von Fehler behandeln können."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.display import YouTubeVideo\n",
    "YouTubeVideo('liIlW-ovx0Y')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.12 Debugging\n",
    "\n",
    "Wenn ein Syntax- oder Laufzeitfehler auftritt, enthält die Fehlermeldung oft eine überwältigende Menge an Information. Die hilfreichsten Teile davon sind üblicherweise:\n",
    "- Welcher Art von Fehler aufgetreten ist und\n",
    "- wo der Fehler aufgetreten ist.\n",
    "\n",
    "Syntaxfehler sind üblicherweise leichter zu finden, aber es gibt ein paar knifflige Fälle. Probleme mit Leerzeichen können schwierig zu finden sein, denn Leerzeichen (und auch Tabs) sind unsichtbar und wir ignorieren sie üblicherweise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 5\n",
    " y = 6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In diesem Beispiel ist das Problem, dass die zweite Zeile durch ein Leerzeichen eingerückt ist. Aber die Fehlermeldung zeigt auf `y`, was verwirrend ist. Im allgemeinen gibt eine Fehlermeldung an, wo das Problem entdeckt wurde, aber der tatsächliche Fehler kann sich weiter vorne im Code befinden, manchmal auch in der vorhergehenden Zeile.\n",
    "\n",
    "Das gleiche gilt für Laufzeitfehler. Angenommen, wir versuchen das Signal-Rausch-Verhältnis in Dezibel zu berechnen. Die Formel dafür ist $SNR_{db} = 10\\log_{10}(P_{signal}/P_{noise})$. In Python könnten wir das so aufschreiben:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "signal_power = 9\n",
    "noise_power = 10\n",
    "ratio = signal_power // noise_power\n",
    "decibels = 10 * math.log10(ratio)\n",
    "print(decibels)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wenn wir dieses Programm ausführen, erhalten wir einen Fehler:\n",
    "\n",
    "```\n",
    "Traceback (most recent call last)\n",
    "<ipython-input-53-b5706bfbb8ff> in <module>()\n",
    "      3 noise_power = 10\n",
    "      4 ratio = signal_power // noise_power\n",
    "----> 5 decibels = 10 * math.log10(ratio)\n",
    "      6 print(decibels)\n",
    "\n",
    "ValueError: math domain error\n",
    "```\n",
    "\n",
    "Die Fehlermeldung gibt Zeile 5 an, aber in dieser Zeile befindet sich kein Fehler. Um den tatsächlichen Fehler zu finden könnte es hilfreich sein, den Wert von `ratio` mit Hilfe der `print`-Funktion auszugeben. Tatsächlich ist der Wert 0. Das Problem ist also in Zeile 4, da dort Ganzzahldivision statt Gleitkommadivision genutzt wird.\n",
    "\n",
    "Sie sollten sich die Zeit nehmen und Fehlermeldungen sorgfältig durchlesen aber nicht davon ausgehen, dass alles was darin steht richtig ist."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.13 Glossar\n",
    "\n",
    "Legen wir uns eine Liste mit den wichtigsten Begriffen an, die wir im Kapitel 5 gelernt haben:\n",
    "- Ganzzahldivision:\n",
    "- Restoperator: Ein Operator, bezeichnet durch ein Prozentzeichen (`%`), der auf ganzen Zahlen operiert und als Ergebnis den Rest zurückliefert, der sich bei Division der einen durch die andere Zahl ergibt.\n",
    "- Boolescher Ausdruck:\n",
    "- relationaler Operator:\n",
    "- logischer Operator:\n",
    "- Verzweigung:\n",
    "- Bedingung:\n",
    "- Verbundanweisung:\n",
    "- Zweig:\n",
    "- verkettete Verzweigung:\n",
    "- verschachtelte Verzweigung:\n",
    "- `return`-Anweisung\n",
    "- Rekursion:\n",
    "- Basisfall:\n",
    "- unendliche Rekursion:\n",
    "\n",
    "Ergänzen Sie die Liste in eigenen Worten. Das ist eine gute Erinnerungs- und Übungsmöglichkeit."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.14 Übung\n",
    "\n",
    "#### Aufgabe 1\n",
    "\n",
    "Das Modul `time` bietet eine Funktion, die ebenfalls `time` heißt, und die uns für die Zeitzone Greenwich Mean Time die Zeit (in Sekunden) zurückliefert, die seit einem Referenzpunkt vergangen ist. Der Referenzpunkt ist ziemlich willkürlich gewählt und ist meistens der 1. Januar 1970."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "seconds=time.time()\n",
    "minutes=seconds/60\n",
    "hours=minutes/60\n",
    "days=hours/24\n",
    "weeks=days/7\n",
    "years=days/365\n",
    "print(seconds, minutes, hours, days, weeks, years, sep='\\t')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Schreiben Sie eine Funktion `print_time`, die die aktuelle Zeit mit Hilfe von `time` abfragt und diese in eine Tageszeit in Stunden, Minuten und Sekunden sowie die Anzahl der Tage die seit dem Referenzpunkt vergangen sind konvertiert und diese Werte ausgibt:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "def print_time():\n",
    "    seconds=time.time()\n",
    "    days=seconds/(60*60*24)\n",
    "    whole_days=seconds//(60*60*24)\n",
    "    hours=(days-whole_days)*24\n",
    "    whole_hours=int((days-whole_days)*24)\n",
    "    minutes= (hours-whole_hours)*60\n",
    "    whole_minutes=int((hours-whole_hours)*60)\n",
    "    seconds_left=(minutes-whole_minutes)*60\n",
    "    whole_seconds=int((minutes-whole_minutes)*60)\n",
    "    print('days passed since January 1st 1970: ',int(whole_days),'\\nthe time (GMT) is :' ,whole_hours, ' hh : ',whole_minutes,' mm : ',whole_seconds, ' ss')\n",
    "    \n",
    "# Testaufruf\n",
    "print_time()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![If only we&#39;d chosen 1944-12-02 08:45:52 as the Unix epoch, we could&#39;ve combined two doomsday scenarios into one and added a really boring scene to that Roland Emmerich movie.](https://imgs.xkcd.com/comics/2038.png)\n",
    "\n",
    "([2038](https://xkcd.com/607/), Randall Munroe)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Aufgabe 2\n",
    "\n",
    "![Pierre de Fermat](https://upload.wikimedia.org/wikipedia/commons/f/f3/Pierre_de_Fermat.jpg)\n",
    "\n",
    "[Fermats letzter Satz](https://de.wikipedia.org/wiki/Gro%C3%9Fer_Fermatscher_Satz) besagt dass es keine positiven ganzen Zahlen $a$,$b$ und $c$ gibt, so dass\n",
    "\\begin{equation}\n",
    "a^n + b^n = c^n\n",
    "\\end{equation}\n",
    "für alle $n$ größer 2 gilt.\n",
    "\n",
    "1. Schreiben Sie eine Funktion `check_fermat` die vier Parameter erwartet - `a`, `b`, `c` und `n` - und prüft, ob Fermats letzter Satz gilt. Falls `n` größer als 2 ist und $a^n + b^n = c^n$ gilt, sollte das Programm \"Unglaublich, Fermat lag falsch!\" ausgeben, ansonsten \"Nein, das funktioniert nicht.\"\n",
    "2. Schreiben Sie eine Funktion, die den Nutzer bittet, Werte für a, b, c und n einzugeben, diese in ganze Zahlen umwandelt und dann die Funktion `check_fermat` nutzt, um zu prüfen, ob sie Fermats letzten Satz erfüllen. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_fermat(a,b,c,n):\n",
    "    if n>2:\n",
    "        a_n=a\n",
    "        b_n=b\n",
    "        c_n=c\n",
    "        for i in range(1,n):\n",
    "            a_n=a_n*a\n",
    "            b_n=b_n*b\n",
    "            c_n=c_n*c\n",
    "        if a_n+b_n==c_n:\n",
    "            print('Unglaublich, Fermat lag falsch!')\n",
    "        else:\n",
    "            print('Nein, das funktioniert nicht.')\n",
    "    else: \n",
    "        print('n muss größer als 2 sein, um Fermats Satz zu überprüfen')\n",
    "\n",
    "\n",
    "def  check_fermat2(a,b,c,n):\n",
    "    a=int(a)\n",