seminar05.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 5 Verzweigungen und Rekursion\n",
    "[Chapter 5: Conditionals and recursion](https://greenteapress.com/thinkpython2/html/thinkpython2006.html)\n",
    "\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. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1>Inhaltsverzeichnis<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#Ihre-Lernziele:\" data-toc-modified-id=\"Ihre-Lernziele:-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Ihre Lernziele:</a></span></li><li><span><a href=\"#Exkurs:-Was-mir-an-Python-gefällt\" data-toc-modified-id=\"Exkurs:-Was-mir-an-Python-gefällt-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>Exkurs: Was mir an Python gefällt</a></span></li><li><span><a href=\"#Ganzzahldivision-und-Restberechnung\" data-toc-modified-id=\"Ganzzahldivision-und-Restberechnung-3\"><span class=\"toc-item-num\">3&nbsp;&nbsp;</span>Ganzzahldivision und Restberechnung</a></span></li><li><span><a href=\"#Boolesche-Ausdrücke\" data-toc-modified-id=\"Boolesche-Ausdrücke-4\"><span class=\"toc-item-num\">4&nbsp;&nbsp;</span>Boolesche Ausdrücke</a></span></li><li><span><a href=\"#Logische-Operatoren\" data-toc-modified-id=\"Logische-Operatoren-5\"><span class=\"toc-item-num\">5&nbsp;&nbsp;</span>Logische Operatoren</a></span></li><li><span><a href=\"#Verzweigungen\" data-toc-modified-id=\"Verzweigungen-6\"><span class=\"toc-item-num\">6&nbsp;&nbsp;</span>Verzweigungen</a></span></li><li><span><a href=\"#Alternative-Verzweigung\" data-toc-modified-id=\"Alternative-Verzweigung-7\"><span class=\"toc-item-num\">7&nbsp;&nbsp;</span>Alternative Verzweigung</a></span></li><li><span><a href=\"#Verkettete-Verzweigungen\" data-toc-modified-id=\"Verkettete-Verzweigungen-8\"><span class=\"toc-item-num\">8&nbsp;&nbsp;</span>Verkettete Verzweigungen</a></span></li><li><span><a href=\"#Verschachtelte-Verzweigungen\" data-toc-modified-id=\"Verschachtelte-Verzweigungen-9\"><span class=\"toc-item-num\">9&nbsp;&nbsp;</span>Verschachtelte Verzweigungen</a></span></li><li><span><a href=\"#Rekursion\" data-toc-modified-id=\"Rekursion-10\"><span class=\"toc-item-num\">10&nbsp;&nbsp;</span>Rekursion</a></span></li><li><span><a href=\"#Stapeldiagramme-für-rekursive-Funktionen\" data-toc-modified-id=\"Stapeldiagramme-für-rekursive-Funktionen-11\"><span class=\"toc-item-num\">11&nbsp;&nbsp;</span>Stapeldiagramme für rekursive Funktionen</a></span></li><li><span><a href=\"#Unendliche-Rekursion\" data-toc-modified-id=\"Unendliche-Rekursion-12\"><span class=\"toc-item-num\">12&nbsp;&nbsp;</span>Unendliche Rekursion</a></span></li><li><span><a href=\"#Tastatur-Eingaben\" data-toc-modified-id=\"Tastatur-Eingaben-13\"><span class=\"toc-item-num\">13&nbsp;&nbsp;</span>Tastatur-Eingaben</a></span><ul class=\"toc-item\"><li><span><a href=\"#5.12-Debugging\" data-toc-modified-id=\"5.12-Debugging-13.1\"><span class=\"toc-item-num\">13.1&nbsp;&nbsp;</span>5.12 Debugging</a></span></li></ul></li><li><span><a href=\"#Glossar\" data-toc-modified-id=\"Glossar-14\"><span class=\"toc-item-num\">14&nbsp;&nbsp;</span>Glossar</a></span></li><li><span><a href=\"#Übung\" data-toc-modified-id=\"Übung-15\"><span class=\"toc-item-num\">15&nbsp;&nbsp;</span>Übung</a></span><ul class=\"toc-item\"><li><span><a href=\"#Aufgabe-1\" data-toc-modified-id=\"Aufgabe-1-15.1\"><span class=\"toc-item-num\">15.1&nbsp;&nbsp;</span>Aufgabe 1</a></span></li><li><span><a href=\"#Aufgabe-2\" data-toc-modified-id=\"Aufgabe-2-15.2\"><span class=\"toc-item-num\">15.2&nbsp;&nbsp;</span>Aufgabe 2</a></span></li><li><span><a href=\"#Aufgabe-3\" data-toc-modified-id=\"Aufgabe-3-15.3\"><span class=\"toc-item-num\">15.3&nbsp;&nbsp;</span>Aufgabe 3</a></span></li><li><span><a href=\"#Aufgabe-4\" data-toc-modified-id=\"Aufgabe-4-15.4\"><span class=\"toc-item-num\">15.4&nbsp;&nbsp;</span>Aufgabe 4</a></span></li><li><span><a href=\"#Aufgabe-5\" data-toc-modified-id=\"Aufgabe-5-15.5\"><span class=\"toc-item-num\">15.5&nbsp;&nbsp;</span>Aufgabe 5</a></span></li><li><span><a href=\"#Aufgabe-6\" data-toc-modified-id=\"Aufgabe-6-15.6\"><span class=\"toc-item-num\">15.6&nbsp;&nbsp;</span>Aufgabe 6</a></span></li></ul></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ihre Lernziele:\n",
    "Beschreiben Sie in 2-3 Stichpunkten kurz was Sie im Seminar heute lernen wollen. Klicken Sie dazu doppelt auf diesen Text und bearbeiten Sie dann den Text:\n",
    "\n",
    " - \n",
    " - \n",
    " - \n",
    " \n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exkurs: Was mir an Python gefällt\n",
    "\n",
    "Wir wünschen Ihnen ein frohes Fest und einen guten Rutsch ins neue Jahr."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\" \n",
    "Quelle: https://teampython.wordpress.com/2015/12/12/print-a-christmas-tree/\n",
    "Python 3 version by antiloquax (2015), based on code from datamungeblog.com.\n",
    "\"\"\"\n",
    " \n",
    "from random import choice\n",
    "from random import random\n",
    " \n",
    "# If you change this, use an odd number.\n",
    "size = 21\n",
    "\n",
    "# Probability that a character will be green.\n",
    "prob_gr = 0.6\n",
    "# Colour codes.\n",
    "colours = [31, 33, 34, 35, 36, 37]\n",
    "# Characters to use for decorations. Experiment with these.\n",
    "# The chr(169) and chr(174) characters may not work in all terminals\n",
    "# (extended ASCII, c and r in a circle).\n",
    "decs = ['@', '&', '*', chr(169), chr(174)]\n",
    "\n",
    "# Format string for printing blinking characters.\n",
    "blink_col = \"\\033[5;{0}m{1}\\033[0m\"\n",
    "# String to print a green octothorpe ('#').\n",
    "leaf = \"\\033[32m#\\033[0m\"\n",
    "\n",
    "# Width of the tree, will grow by 2 each time.\n",
    "width = 1\n",
    "# Initialise the tree string, with a star at the top.\n",
    "tree = \"\\n{}*\\n\".format(' ' * (size))\n",
    "\n",
    "\"\"\" Main Loop starts now.\"\"\"\n",
    " \n",
    "\"\"\" We can't use the normal \"format\" centering approach:\n",
    "    (\"{:^nn}\".format(string) where \"nn\" is the width of the line), \n",
    "    with these ansi codes. This is because Python sees the strings as being\n",
    "    more than one character long (15 & 10 for baubles and leaves).\"\"\"\n",
    "\n",
    "# Loop from (size - 1) down to 0, using the counter as the padding size.\n",
    "for pad in range(size - 1, -1, -1):\n",
    "    # Increase the width of the tree by 2.\n",
    "    width += 2\n",
    "     \n",
    "    # Put the characters for the line in \"temp\".\n",
    "    temp = \"\"\n",
    "    for j in range(width):\n",
    "        # Make some leaves.\n",
    "        if random() < prob_gr:\n",
    "            temp += leaf\n",
    "        # And also some baubles.\n",
    "        else:\n",
    "            temp += blink_col.format(choice(colours), choice(decs))\n",
    "\n",
    "    # Add that string to the line, with padding.\n",
    "    tree += \"{0}{1}\\n\".format(' ' * pad, temp)\n",
    "\n",
    "# Add a \"trunk\" of 2 lines and return.\n",
    "print(tree + \"{0}{1}\\n\".format(' ' * (size - 1), \"000\") * 2)\n",
    "print(\"\\x46\\x72\\x6f\\x68\\x65\\x20\\x46\\x65\\x73\\x74\\x74\\x61\\x67\\x65\\x21\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Und noch viele weitere schöne Beispiele](https://codegolf.stackexchange.com/questions/15860/) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Boolesche Ausdrücke\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.lib.display import YouTubeVideo\n",
    "YouTubeVideo('https://www.youtube.com/watch?v=ucsv_Nhhxmk&list=PL_pqkvxZ6ho3u8PJAsUU-rOAQ74D0TqZB&index=9')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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) [Erklärung des Comics](https://www.explainxkcd.com/wiki/index.php/1033:_Formal_Logic) falls Sie mehr erfahren möchten."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Logische Operatoren\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.lib.display import YouTubeVideo\n",
    "YouTubeVideo('https://www.youtube.com/watch?v=075l6R42tkQ&list=PL_pqkvxZ6ho3u8PJAsUU-rOAQ74D0TqZB&index=12')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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 zwei *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": [
    "## Verzweigungen\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.lib.display import YouTubeVideo\n",
    "YouTubeVideo('https://www.youtube.com/watch?v=b6KzYbM-Hvg&list=PL_pqkvxZ6ho3u8PJAsUU-rOAQ74D0TqZB&index=10')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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": [
    "x = 4\n",
    "\n",
    "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": [
    "## Alternative Verzweigung\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.lib.display import YouTubeVideo\n",
    "YouTubeVideo('https://www.youtube.com/watch?v=b6KzYbM-Hvg&list=PL_pqkvxZ6ho3u8PJAsUU-rOAQ74D0TqZB&index=11')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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": [
    "## 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": [
    "x = 2\n",
    "y = 3\n",
    "\n",
    "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": [
    "## 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": [
    "## Rekursion\n",
    "\n",
    "Um Rekursion zu verstehen, gehen Sie zu [Abschnitt 5.9](#5.9-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) [Erklärung des Comics](https://www.explainxkcd.com/wiki/index.php/244:_Tabletop_Roleplaying) falls Sie mehr wissen möchten. \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)"
   ]
  },
  {
   "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 dort erst definieren und dann auch 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": [
    "## Stapeldiagramme für rekursive Funktionen\n",
    "\n",
    "In [Abschnitt 3.12](notebooks_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",
    "    pass # Löschen Sie diese Zeile, wenn Sie anfangen, die Funktion zu implementieren\n",
    "\n",
    "\n",
    "# eine Testfunktion\n",
    "def testfunktion():\n",
    "    print(\"Ich wurde aufgerufen!\")\n",
    "\n",
    "# Funktionsaufruf von do_n\n",
    "do_n(testfunktion, 7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 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": [
    "## Tastatur-Eingaben\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.lib.display import YouTubeVideo\n",
    "YouTubeVideo('https://www.youtube.com/watch?v=I9h1c-121Uk&list=PL_pqkvxZ6ho3u8PJAsUU-rOAQ74D0TqZB&index=6')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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": [
    "## 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": [
    "## Ü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",
    "time.time()"
   ]
  },
  {
   "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:\n",
    "\n",
    "Wie gehabt folgen hier einige Hinweise zu einer möglichen Lösung.\n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">1. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Überlegen Sie zunächst wie der Zusammenhang zwischen Sekunden, Minuten, Stunden und Tagen aussieht. Wie viele Sekunden sind in einer Minute, wie viele Minuten sind in einer Stunde, wie viele Stunden sind in einem Tag?\n",
    "    \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">2. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "Wenn wir die Zeit seit dem Referenzzeitpunkt in sekunden haben, können wir damit ausrechnen, wie viele Minuten seit diesem Zeitpunkt vergangen sind. \n",
    "      \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">3. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    " Wir verwenden Ganzzahldivision um die Anzahl in Minuten als ganze Zahl zu erhalten. Um zu lernen wie viele Sekunden dann noch übrig sind, führen wir eine Restberechnung durch. Dies ist die aktuelle Sekundenzahl für unsere Uhrzeit.\n",
    "      \n",
    "  </div> \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">4. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Das ganze wird jetzt analog für die Anzahl and Stunden und Tagen seit dem Referenzzeitpunkt vorgenommen. Dabei wird die Uhrzeit über die Resteberechnung analog zur Sekundenzahl berechnet.\n",
    "\n",
    "  </div> \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Insgesamt werden 6 Berechnungen durchgeführt.\n",
    "\n",
    "  </div> \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">6. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Vergessen Sie nicht eine `print`-Anweisung zu schreiben, die Ihr Ergebnis ausgibt. Sie können ihr Ergebnis einfach überprüfen. Sie angegebene Zeit sollte genau 2 Stunden vor der aktuellen Zeit in Deutschland liegen.\n",
    "\n",
    "  </div> \n",
    "</details>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],