seminar06.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Seminar Problemorientierte Programmierung\n",
    "\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": [
    "pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6 Ertragreiche Funktionen\n",
    "\n",
    "Viele Python-Funktionen die wir bis jetzt genutzt haben, wie z.B. die Mathematik-Funktionen aus dem `math`-Modul, erzeugen Rückgabewerte (*return values*). Aber die meisten Funktionen die wir bisher selber geschrieben haben sind \"leer\": sie bewirken etwas, beispielsweise die Ausgabe eines Wertes (mit Hilfe der `print`-Funktion) oder die Bewegung einer Schildkröte, aber sie haben keinen Rückgabewert. In diesem Kapitel werden wir lernen, wie wir \"ertragreiche Funktionen\", also solche mit Rückgabewert, schreiben können.\n",
    "\n",
    "![RFC 1149.5 specifies 4 as the standard IEEE-vetted random number.](https://imgs.xkcd.com/comics/random_number.png)\n",
    "\n",
    "([Random Number](https://xkcd.com/221/), Randall Munroe)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.1 Rückgabewerte\n",
    "\n",
    "Der Aufruf einer Funktion erzeugt einen Rückgabewert, den wir üblicherweise einer Variable zuweisen oder als Teil eines Ausdrucks verwenden:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "e = math.exp(1.0)\n",
    "height = radius * math.sin(radians)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die (meisten) Funktionen, die wir bisher geschrieben haben sind \"leer\" - sie haben keinen Rückgabewert. Präziser ausgedrückt ist ihr Rückgabewert `None` (also nichts).\n",
    "\n",
    "In diesem Kapitel schreiben wir (endlich) ertragreiche Funktionen. Das erste Beispiel ist die Funktion `kreisflaeche`, die die Fläche eines Kreises für einen gegebenen Radius berechnet:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def kreisflaeche(radius):\n",
    "    a = math.pi * radius**2\n",
    "    return a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir haben die `return`-Anweisung vorher schon einmal gesehen, aber in ertragreichen Funktionen folgt hinter der `return`-Anweisung ein Ausdruck (im Beispiel oben `a`). Die Anweisung bedeutet: \"Beende sofort diese Funktion und verwende den folgenden Ausdruck als Rückgabewert.\" Der Ausdruck kann beliebig kompliziert sein, wir könnten diese Funktion also auch kürzer schreiben: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def kreisflaeche(radius):\n",
    "    return math.pi * radius**2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Auf der anderen Seite können uns **temporäre Variablen** wie `a` beim Debugging helfen.\n",
    "\n",
    "Manchmal ist es nützlich, mehrere `return`-Anweisungen zu haben - eine in jedem Zweig einer Verzweigung:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def betrag(x):\n",
    "    if x < 0:\n",
    "        return -x\n",
    "    else:\n",
    "        return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Da solche `return`-Anweisungen in alternativen (sich gegenseitig ausschließenden) Zweigen liegen, wird nur eine davon ausgeführt.\n",
    "\n",
    "Sobald eine `return`-Anweisung ausgeführt wird, wird die Funktion beendet, ohne die folgenden Anweisungen auszuführen. Code der nach einer `return`-Anweisung folgt oder an einer anderen Stelle, die während der Ausführung niemals erreicht werden kann, wird **toter Code** (*dead code*) genannt.\n",
    "\n",
    "<center>\n",
    "{☠} \n",
    "<br/>\n",
    "dead code\n",
    "</center>\n",
    "\n",
    "In einer eintragreichen Funktion sollten wir sicherstellen, dass jeder mögliche Pfad durch den Code eine `return`-Anweisung erreicht. Zum Beispiel:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def betrag(x):\n",
    "    if x < 0:\n",
    "        return -x\n",
    "    if x > 0:\n",
    "        return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Diese Funktion ist falsch, denn wenn `x` gleich 0 ist, ist keine der beiden Bedingungen erfüllt und die Funktion wird beendet, ohne dass eine `return`-Anweisung erreicht wird. Wenn die Ausführung das Ende einer Funktion erreicht, ist der Rückgabewert `None`, was nicht der Betrag von 0 ist:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(betrag(0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Übrigens, Python bietet eine eingebaute Funktion `abs` die den Betrag einer Zahl berechnet:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(abs(-42))\n",
    "print(abs(0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Schreiben Sie eine Funktion `compare`, die zwei Parameter erwartet, `x` und `y`, und `1` zurückliefert, wenn `x > y` ist, `0` wenn `x == y` gilt und `-1` für `x < <`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier die Funktion compare"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.2 Schrittweise Entwicklung\n",
    "\n",
    "Wenn Sie größere Funktionen schreiben kann es sein, dass Sie mehr Zeit mit der Fehlersuche (Debugging) verbringen.\n",
    "\n",
    "Um mit zunehmend komplexeren Programmen klarzukommen, können Sie eine verwenden, die sich **schrittweise Entwicklung** (*incremental development*) nennt. Das Ziel bei der schrittweisen Entwicklung ist die Vermeidung langer Fehlersuch-Sitzungen, indem immer nur kleine Codestücke hinzugefügt und getestet werden.\n",
    "\n",
    "Nehmen wir z.B. an, dass wir die Entfernung zwischen zwei Punkten berechnen wollen, die durch die Koordinaten $(x_1, y_1)$ und $(x_2, x_2)$ gegeben sind. Nach dem [Satz des Pythagoras](https://de.wikipedia.org/wiki/Satz_des_Pythagoras) ist die Entfernung: \n",
    "\n",
    "$entfernung = \\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$\n",
    "\n",
    "Im ersten Schritt sollten wir uns überlegen, wie die Funktion `entfernung` in Python aussehen sollte. In anderen Worten: was sind die Eingaben (Parameter) und was ist das Ergebnis (Rückgabewert)?\n",
    "\n",
    "In diesem Fall sind die Eingaben zwei Punkte, die wir durch vier Zahlen repräsentieren können. Das Ergebnis ist die Entfernung, repräsentiert als Gleitkommazahl.\n",
    "\n",
    "Mit dieser Information können wir sofort eine Skizze der Funktion schreiben:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def entfernung(x1, y1, x2, y2):\n",
    "    return 0.0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ganz offensichtlich berechnet diese Variante nicht die Entfernung, sie liefert stets Null zurück. Aber sie ist syntaktisch korrekt und sie läuft, das heißt, wir können die Funktion testen, bevor wir sie verkomplizieren.\n",
    "\n",
    "Rufen Sie die Funktion mit Beispielargumenten auf, um sie zu testen: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "entfernung(1, 2, 4, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Diese Werte sind so gewählt, dass die horizontale Distanz drei ist und die vertikale Distanz 4 - dadurch ist das Ergebnis 5 - die Hypothenuse eines Dreiecks mit den Seitenlängen 3-4-5. Wenn wir die Funktion testen ist es hilfreich, das richtige Ergebnis zu kennen.\n",
    "\n",
    "![Satz des Pythagoras](https://upload.wikimedia.org/wikipedia/commons/d/d1/01-Rechtwinkliges_Dreieck-Pythagoras.svg) \n",
    "\n",
    "([Petrus3743](https://commons.wikimedia.org/wiki/File:01-Rechtwinkliges_Dreieck-Pythagoras.svg), Wikimedia Commons)\n",
    "\n",
    "An dieser Stelle haben wir uns davon überzeugt, dass die Funktion syntaktisch korrekt ist und wir können damit beginnen, Code zum Rumpf hinzuzufügen. Ein naheliegender nächster Schritt ist die Differenzen $x_2-x_1$ und $y_2-y_1$ zu berechnen. Die nächste Version speichert die Werte in temporären Variablen und gibt sie aus: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def entfernung(x1, y1, x2, y2):\n",
    "    dx = x2 - x1\n",
    "    dy = y2 - y1\n",
    "    print('dx ist', dx)\n",
    "    print('dy ist', dy)\n",
    "    return 0.0\n",
    "\n",
    "entfernung(1, 2, 4, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wenn die Funktion richtig funktioniert, sollte `dx ist 3` und `dx ist 4` ausgegeben werden. Wenn dem so ist wissen wir, dass die Funktion die Argumente richtig erhalten hat und die erste Berechnung korrekt durchgeführt wurde. Falls nicht, gibt es nur wenige Zeilen, die wir überprüfen müssen.\n",
    "\n",
    "Als nächstes berechnen wir die Summe der Quadrate von `dx` und `dy`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def entfernung(x1, y1, x2, y2):\n",
    "    dx = x2 - x1\n",
    "    dy = y2 - y1\n",
    "    dquadrat = dx**2 + dy**2\n",
    "    print('dquadrat ist: ', dquadrat)\n",
    "    return 0.0\n",
    "\n",
    "entfernung(1, 2, 4, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wieder rufen wir die Funktion mit bekannten Werten auf und prüfen das Ergebnis (das 25 sein sollte). Schließlich können wir die Funktion `math.sqrt` nutzen um das Ergebnis zu berechnen und zurückzugeben:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "def entfernung(x1, y1, x2, y2):\n",
    "    dx = x2 - x1\n",
    "    dy = y2 - y1\n",
    "    dquadrat = dx**2 + dy**2\n",
    "    ergebnis = math.sqrt(dquadrat)\n",
    "    return ergebnis\n",
    "\n",
    "entfernung(1, 2, 4, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Falls das richtig funktioniert, sind wir fertig. Ansonsten könnten wir beispielsweise den Wert von `ergebnis` vor der `return`-Anweisung mit `print` ausgeben.\n",
    "\n",
    "Die endgültige Version der Funktion zeigt nichts an (gibt nichts auf dem Bildschirm aus), wenn sie ausgeführt wird; sie gibt nur einen Wert zurück. Die `print`-Anweisungen die wir zwischendurch geschrieben haben sind hilfreich für die Fehlersuche, aber sobald die Funktion funktioniert, sollten wir sie entfernen. Solcher Code wird **Hilfscode** (*scaffolding*) genannt, denn er hilft beim Schreiben des Programms aber ist nicht Teil des endgültigen Produkts.\n",
    "\n",
    "Wenn Sie mit Programmieren beginnen, sollten sie jeweils nur ein bis zwei Zeilen auf einmal hinzufügen. Sobald Sie mehr Erfahrung gesammelt haben werden Sie merken, dass Sie größere Stücke Code auf einmal schreiben und testen. In jedem Fall kann Ihnen schrittweise Entwicklung viel Zeit bei der Fehlersuche ersparen.\n",
    "\n",
    "Die wichtigsten Punkte dieses Vorgehens sind:\n",
    "1. Beginnen Sie mit einem funktionierenden Programm und führen Sie nur kleine, inkrementelle Änderungen durch. Sollte ein Fehler auftreten, so sollten Sie zu jedem Zeitpunkt eine gute Idee davon haben, wodurch er hervorgerufen wird.\n",
    "2. Nutzen Sie Variablen, um Zwischenwerte zu speichern, so dass Sie diese ausgeben (`print`) und überprüfen können.\n",
    "3. Sobald das Programm funktioniert sollten Sie Teile des Hilfscodes entfernen oder mehrere Anweisungen zu einer Verbundanweisung zusammenfügen, aber nur, wenn sich dadurch die Lesbarkeit des Programms nicht verschlechtert.\n",
    "\n",
    "**Übung:** Nutzen Sie das Prinzip der schrittweisen Entwicklung, um eine Funktion `hypothenuse` zu schreiben, die die Länge der Hypothenuse eines rechtwinkligen Dreiecks zurückgibt, wenn die Längen der beiden Katheden gegeben sind. Dokumentieren Sie jeden Entwicklungsschritt hier im Notebook (d.h., erzeugen Sie eine Kopie der Funktion, bevor Sie den nächsten Entwicklungsschritt durchführen)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# beginnen Sie hier mit der Entwicklung der Funktion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.3 Komposition\n",
    "\n",
    "Wie Sie mittlerweile wissen sollten, können wir eine Funktion innerhalb einer anderen aufrufen. Als Beispiel werden wir eine Funktion schreiben, die zwei Punkte erwartet - den Mittelpunkt eines Kreises und einen Punkt auf dem Kreisumfang - und uns daraus die Fläche des Kreises berechnet.\n",
    "\n",
    "Angenommen, die Koordinaten des Mittelpunktes sind in den Variablen `xc` und `yc` gespeichert und die des Punktes auf dem Kreisumfang in `xp` und `yp`. Der erste Schritt ist, den Radius des Kreises zu berechnen, der sich aus der Entfernung der beiden Punkte ergibt. Wir haben gerade eine Funktion `entfernung` geschrieben, die das erledigt: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "radius = entfernung(xc, yc, xp, yp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der nächste Schritt ist, die Fläche eines Kreises mit diesem Radius zu berechnen. Das haben wir auch schon implementiert:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ergebnis = kreisflaeche(radius)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wenn wir diese Schritte in einer Funktion verkapseln, erhalten wir:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def kreisflaeche_2(xc, yc, xp, yp):\n",
    "    radius = entfernung(xc, yc, xp, yp)\n",
    "    ergebnis = kreisflaeche(radius)\n",
    "    return ergebnis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Hilfsvariablen `radius` und `ergebnis` sind hilfreich für  Entwicklung und Debugging, aber sobald das Programm funktioniert können wir es prägnanter aufschreiben durch die Komposition von Funktionsaufrufen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def kreisflaeche_2(xc, yc, xp, yp):\n",
    "    return kreisflaeche(entfernung(xc, yc, xp, yp))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Kreisfläche](https://upload.wikimedia.org/wikipedia/commons/d/d2/Circle_Area_de.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.4 Boolesche Funktionen\n",
    "\n",
    "Funkionen können Boolesche Werte zurückliefern. Das ist praktkisch, um  komplizierte Tests in einer Funktion zu verstecken. Zum Beispiel: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ist_teilbar(x, y):\n",
    "    if x % y == 0:\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Es ist üblich, Booleschen Funktionen Namen zu geben, die wie Ja-/Nein-Fragen klingen; `ist_teilbar` gibt entweder `True` oder `False` zurück und zeigt damit an, ob `x` durch `y` teilbar ist.\n",
    "\n",
    "Hier ist ein Beispiel:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ist_teilbar(6, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ist_teilbar(6, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das Ergebnis des `==`-Operators ist ein Boolescher Wert, daher können wir die Funktion kompakter aufschreiben, indem wir den Wert direkt zurückgeben:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ist_teilbar(x, y):\n",
    "    return x % y == 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Boolesche Funktionen werden oft in Verzweigungen genutzt:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if ist_teilbar(x, 2):\n",
    "    print('x ist eine gerade Zahl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Es mag verlockend erscheinen, stattdessen folgendes zu schreiben:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if ist_teilbar(x, 2) == True:\n",
    "    print('x ist eine gerade Zahl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Aber dieser zusätzliche Vergleich ist unnötig.\n",
    "\n",
    "Schreiben Sie als Übung eine Funktion `ist_zwischen(x, y, z)`, die `True` zurückgibt, wenn $x \\le y \\le z$ gilt und ansonsten `False`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# def implementieren Sie hier die Funktion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.5 Noch mehr Rekursion\n",
    "\n",
    "Wir haben bisher nur eine kleine Teilmenge von Python kennengelernt aber vielleicht interessiert es Sie zu wissen, dass diese Teilmenge eine *komplette* Programmiersprache darstellt. Das heißt, alles was berechnet werden kann, können wir mit den bisher erlernten Anweisungen und Funktionen ausdrücken! Jedes jemals geschriebene Programm könnten wir umschreiben, so dass es nur mit den Sprachmerkmalen auskommt, die wir bis jetzt gelernt haben (gut, wir bräuchten noch ein paar Anweisungen um Geräte wie z.B. die Maus, Festplatten, etc. zu kontrollieren).\n",
    "\n",
    "![Alan Turing](https://upload.wikimedia.org/wikipedia/commons/thumb/7/79/Alan_Turing_az_1930-as_%C3%A9vekben.jpg/372px-Alan_Turing_az_1930-as_%C3%A9vekben.jpg)\n",
    "\n",
    "Diese Behauptung zu beweisen ist eine nicht so ganz einfache Aufgabe, die zuerst von [Alan Turing](https://de.wikipedia.org/wiki/Alan_Turing) gelöst wurde. Er war einer der ersten Informatiker (einige würden argumentieren, dass er ein Mathematiker war, aber viele der ersten Informatiker begannen als Mathematiker). Dementsprechend wird dies oft als [Turing-These](https://de.wikipedia.org/wiki/Church-Turing-These) bezeichnet. \n",
    "\n",
    "Um einen Idee davon zu bekommen, was wir mit den Werkzeugen, die wir bisher kennengelernt haben, schon erreichen können, wollen wir einige rekursiv definierte mathematische Funktionen implementieren. Eine rekursive Definition ist ähnlich einer [zirkulären Definition](https://en.wikipedia.org/wiki/Circular_definition) (*circular definition* - leider konnte ich dafür keinen deutschen Begriff finden) in dem Sinne, dass die Definition eine Referenz auf das was definiert wird enthält. Eine richtig zirkuläre Definition ist nicht sehr nützlich:\n",
    "\n",
    "**vorpal:**\n",
    "- Ein Adjektiv welches genutzt wird, um etwas zu beschreiben, was vorpal ist.\n",
    "\n",
    "Wenn Sie so eine Definition in einem Wörterbuch sehen, sind sie vermutlich verärgert. Andererseits, wenn wir uns die Definition der Fakultätsfunktion heraussuchen (die mit dem Symbol ! bezeichnet wird), finden wir vermutlich etwas in der Art:\n",
    "\n",
    "\\begin{align}\n",
    "0! &= 1\\\\\n",
    "n! &= n(n-1)!\n",
    "\\end{align}\n",
    "\n",
    "Diese Definition sagt aus, dass die Fakultät von 0 gleich 1 ist und die Fakultät jedes anderen Wertes $n$ entspricht $n$ multipliziert mit der Fakultät von $n-1$.\n",
    "\n",
    "Also ist 3! gleich 3 mal 2!, was 2 mal 1! ist, was 1 mal 0! ist. Zusammengenommen ist 3! also gleich 3 mal 2 mal 1 mal 1 - also 6.\n",
    "\n",
    "Wenn wir etwas rekursiv definieren können, dann können wir auch eine Python-Funktion schreiben, um das ganze auszuwerten. Der erste Schritt ist, zu entscheiden, was die Parameter sein sollen. In diesem Beispiel sollte es klar sein, dass `fakultaet` eine ganze Zahl erwartet: \n",
    "\n",
    "```python\n",
    "def fakultaet(n):\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wenn das Argument 0 übergeben wird, müssen wir einfach nur 1 zurückgeben:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fakultaet(n):\n",
    "    if n == 0:\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ansonsten, und das ist der spannende Teil, müssen wir einen rekursiven Aufruf machen, um die Fakultät von $n-1$ zu berechnen und dann mit $n$ zu multiplizieren:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fakultaet(n):\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        rekursion = fakultaet(n-1)\n",
    "        ergebnis = n * rekursion\n",
    "        return ergebnis\n",
    "\n",
    "fakultaet(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der Kontrollfluss dieses Programms ist ähnlich dem von `countdown` in [Abschnitt 5.8](seminar05.ipynb#5.8-Rekursion). Wenn wir `fakultaet` mit dem Wert 3 aufrufen, passiert folgendes:\n",
    "\n",
    "Da 3 ungleich 0 ist, führen wir den zweiten Zweig aus und berechnen die Fakultät von $n-1$ ...\n",
    "- Da 2 ungleich 0 ist, führen wir den zweiten Zweig aus und berechnen die Fakultät von $n-1$ ...\n",
    "  - Da 1 ungleich 0 ist, führen wir den zweiten Zweig aus und berechnen die Fakultät von $n-1$ ...\n",
    "    - Da 0 gleich 0 ist, führen wir den ersten Zweig aus und geben 1 zurück, ohne weitere rekursive Aufrufe zu tätigen.\n",
    "    \n",
    "    Der Rückgabewert, 1, wird mit n multipliziert, was 1 ist, und das Ergebnis zurückgegeben.\n",
    "    \n",
    "  Der Rückgabewert, 1, wird mit n multipliziert, was 2 ist, und das Ergebnis zurückgegeben.\n",
    "  \n",
    "Der Rückgabewert, 2, wird mit n multipliziert, was 3 ist, und das Ergebnis 6 wird zum Rückgabewert des Funktionsaufrufs, der den ganzen Vorgang gestartet hat.\n",
    "\n",
    "Die folgende Abbildung zeigt wie das Stapeldiagramm für diese Folge von Funktionsaufrufen aussieht:\n",
    "\n",
    "![Stapeldiagramm](http://amor.cms.hu-berlin.de/~jaeschkr/teaching/spp/stapeldiagramm_fakultaet.svg)\n",
    "\n",
    "Das Diagramm zeigt, wie die Rückgabewerte im Stapel weiter nach oben durchgereicht werden. In jedem Block ist der Rückgabewert der Wert von `ergebnis`, was das Produkt von `n` und `rekursion` ist.\n",
    "\n",
    "Im letzten Block"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Speichern](https://amor.cms.hu-berlin.de/~jaeschkr/teaching/spp/floppy.png) Speichern Sie dieses Notebook, so dass Ihre Änderungen nicht verlorengehen (nicht auf einem Pool-Rechner). Klicken Sie dazu oben links auf das Disketten-Icon und nutzen Sie beispielsweise einen USB-Stick, E-Mail, Google Drive, Dropbox oder Ihre [HU-Box](https://box.hu-berlin.de/).  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Smiley](https://upload.wikimedia.org/wikipedia/commons/3/3e/Cool-smiley.svg)\n",
    "\n",
    "Herzlichen Glückwunsch! Sie haben das 5. Kapitel geschafft. Weiter geht es in [6: Ergebnisreiche Funktionen](seminar06.ipynb)."
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}