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": [
    "## 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** (siehe **modulo**) 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:"
   ]
  },
  {