{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Rekursion und Datenstrukturen – Notebook\n",
    "\n",
    "**Informatik 12 · Rekursion**\n",
    "\n",
    "Rekursion ist im Heft eine Idee und ein Aufrufbaum. Hier wird sie messbar: Sie\n",
    "zählen Aufrufe, vergleichen mit der iterativen Fassung und sehen, was ein einziges\n",
    "`dict` aus einem unbrauchbaren Verfahren macht.\n",
    "\n",
    "Danach bauen Sie die beiden Datenstrukturen des Kapitels selbst — die verkettete\n",
    "Liste und den Suchbaum.\n",
    "\n",
    "Führen Sie zuerst die nächste Zelle aus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(10000)\n",
    "\n",
    "\n",
    "def zeile(*teile):\n",
    "    \"\"\"Kurze Hilfe fuer tabellarische Ausgaben.\"\"\"\n",
    "    print(\"  \".join(str(t).ljust(12) for t in teile))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 1 · Fakultät rekursiv und iterativ\n",
    "\n",
    "Schreiben Sie beide Fassungen und prüfen Sie, dass sie für $0 \\le n \\le 10$\n",
    "dasselbe liefern.\n",
    "\n",
    "**Frage:** Für welches $n$ bricht die rekursive Fassung ab, die iterative aber nicht? Probieren Sie es aus und erklären Sie den Unterschied mit dem Begriff *Aufrufstapel*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fakultaet_rekursiv(n):\n",
    "    # TODO\n",
    "    pass\n",
    "\n",
    "\n",
    "def fakultaet_iterativ(n):\n",
    "    # TODO\n",
    "    pass\n",
    "\n",
    "\n",
    "# for n in range(11):\n",
    "#     zeile(n, fakultaet_rekursiv(n), fakultaet_iterativ(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 2 · Fibonacci und der Preis des Aufrufbaums\n",
    "\n",
    "Schreiben Sie `fib` rekursiv und zählen Sie dabei die Aufrufe mit. Geben Sie für\n",
    "$n = 5, 10, 20, 25$ Ergebnis und Aufrufzahl aus.\n",
    "\n",
    "Das Heft nennt für `fib(5)` 15 Aufrufe und für `fib(10)` 177.\n",
    "\n",
    "**Frage:** Verdoppeln Sie $n$ von 10 auf 20. Um welchen Faktor wächst die Zahl der Aufrufe? Passt das zu „quadratisch“, oder ist es schlimmer?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "aufrufe = 0\n",
    "\n",
    "\n",
    "def fib(n):\n",
    "    global aufrufe\n",
    "    aufrufe += 1\n",
    "    # TODO: Abbruchfall und rekursiver Fall\n",
    "    return 0\n",
    "\n",
    "\n",
    "# for n in [5, 10, 20, 25]:\n",
    "#     aufrufe = 0\n",
    "#     wert = fib(n)\n",
    "#     zeile(n, wert, aufrufe)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 3 · Ein dict als Gedächtnis\n",
    "\n",
    "Der Aufrufbaum rechnet dieselben Werte immer wieder. Geben Sie `fib` ein\n",
    "Gedächtnis: ein `dict`, in dem schon berechnete Werte stehen.\n",
    "\n",
    "Zählen Sie auch hier die Aufrufe und vergleichen Sie mit Aufgabe 2.\n",
    "\n",
    "**Frage:** Die Zahl der Aufrufe wird mit Gedächtnis *linear* in $n$. Erklären Sie warum — wie viele verschiedene Argumente kann `fib` überhaupt bekommen?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "aufrufe = 0\n",
    "\n",
    "\n",
    "def fib_gemerkt(n, gedaechtnis=None):\n",
    "    global aufrufe\n",
    "    aufrufe += 1\n",
    "    if gedaechtnis is None:\n",
    "        gedaechtnis = {}\n",
    "    # TODO: Wert aus dem Gedaechtnis nehmen, sonst berechnen und ablegen\n",
    "    return 0\n",
    "\n",
    "\n",
    "# for n in [10, 20, 25, 100]:\n",
    "#     aufrufe = 0\n",
    "#     zeile(n, fib_gemerkt(n), aufrufe)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 4 · Die verkettete Liste\n",
    "\n",
    "Eine verkettete Liste besteht aus Knoten, die je einen Inhalt und den Verweis auf\n",
    "den nächsten Knoten tragen. Das Ende ist `None`.\n",
    "\n",
    "Bauen Sie `einfuegen_vorn`, `durchlaufen` und `laenge`.\n",
    "\n",
    "**Frage:** Warum ist `einfuegen_vorn` unabhängig von der Länge der Liste gleich schnell, `anhaengen` am Ende aber nicht?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Knoten:\n",
    "    def __init__(self, inhalt, naechster=None):\n",
    "        self.inhalt = inhalt\n",
    "        self.naechster = naechster\n",
    "\n",
    "\n",
    "def einfuegen_vorn(kopf, inhalt):\n",
    "    \"\"\"Gibt den neuen Kopf der Liste zurueck.\"\"\"\n",
    "    # TODO\n",
    "    return kopf\n",
    "\n",
    "\n",
    "def durchlaufen(kopf):\n",
    "    \"\"\"Gibt die Inhalte als Liste zurueck.\"\"\"\n",
    "    inhalte = []\n",
    "    # TODO: so lange weiterhangeln, bis None erreicht ist\n",
    "    return inhalte\n",
    "\n",
    "\n",
    "def laenge(kopf):\n",
    "    # TODO\n",
    "    return 0\n",
    "\n",
    "\n",
    "# liste = None\n",
    "# for wert in [3, 1, 4, 1, 5]:\n",
    "#     liste = einfuegen_vorn(liste, wert)\n",
    "# print(durchlaufen(liste), laenge(liste))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 5 · Der Suchbaum\n",
    "\n",
    "Bauen Sie den Suchbaum aus Abschnitt 3.4: einfügen, suchen und die drei Durchläufe.\n",
    "\n",
    "Fügen Sie 50, 30, 70, 20, 40, 60, 80 ein — genau den Baum aus dem Heft — und prüfen\n",
    "Sie, dass `inorder` die Zahlen sortiert liefert.\n",
    "\n",
    "**Frage:** `inorder` liefert sortiert. Welcher Durchlauf eignet sich, um den Baum abzuspeichern und später **gleich geformt** wieder aufzubauen? Probieren Sie es aus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Baumknoten:\n",
    "    def __init__(self, inhalt):\n",
    "        self.inhalt = inhalt\n",
    "        self.links = None\n",
    "        self.rechts = None\n",
    "\n",
    "\n",
    "def einfuegen(knoten, wert):\n",
    "    \"\"\"Gibt die Wurzel des Teilbaums zurueck.\"\"\"\n",
    "    if knoten is None:\n",
    "        return Baumknoten(wert)\n",
    "    # TODO: nach links oder rechts weiterreichen\n",
    "    return knoten\n",
    "\n",
    "\n",
    "def suchen(knoten, wert):\n",
    "    # TODO\n",
    "    return False\n",
    "\n",
    "\n",
    "def inorder(knoten, raus=None):\n",
    "    if raus is None:\n",
    "        raus = []\n",
    "    # TODO: links, Knoten, rechts\n",
    "    return raus\n",
    "\n",
    "\n",
    "def preorder(knoten, raus=None):\n",
    "    if raus is None:\n",
    "        raus = []\n",
    "    # TODO\n",
    "    return raus\n",
    "\n",
    "\n",
    "# baum = None\n",
    "# for wert in [50, 30, 70, 20, 40, 60, 80]:\n",
    "#     baum = einfuegen(baum, wert)\n",
    "# print(\"inorder \", inorder(baum))\n",
    "# print(\"preorder\", preorder(baum))\n",
    "# print(suchen(baum, 40), suchen(baum, 41))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 6 · Tiefe, Knotenzahl und die Form des Baums\n",
    "\n",
    "Schreiben Sie `knotenzahl` und `tiefe` rekursiv. Bauen Sie dann zwei Bäume mit\n",
    "denselben sieben Zahlen: einmal in der Reihenfolge oben, einmal aufsteigend\n",
    "sortiert.\n",
    "\n",
    "**Frage:** Beide Bäume enthalten dieselben Werte. Warum ist die Suche im zweiten so viel langsamer? Welche Tiefe hätte ein Baum mit 1000 Werten bestenfalls, welche schlimmstenfalls?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def knotenzahl(knoten):\n",
    "    # TODO\n",
    "    return 0\n",
    "\n",
    "\n",
    "def tiefe(knoten):\n",
    "    \"\"\"Tiefe der Wurzel ist 0; ein leerer Baum hat die Tiefe -1.\"\"\"\n",
    "    # TODO\n",
    "    return -1\n",
    "\n",
    "\n",
    "# gut, schlecht = None, None\n",
    "# for wert in [50, 30, 70, 20, 40, 60, 80]:\n",
    "#     gut = einfuegen(gut, wert)\n",
    "# for wert in sorted([50, 30, 70, 20, 40, 60, 80]):\n",
    "#     schlecht = einfuegen(schlecht, wert)\n",
    "# zeile(\"Baum\", \"Knoten\", \"Tiefe\")\n",
    "# zeile(\"gemischt\", knotenzahl(gut), tiefe(gut))\n",
    "# zeile(\"sortiert\", knotenzahl(schlecht), tiefe(schlecht))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "### Abgabe\n",
    "\n",
    "Fertig ist das Notebook, wenn es fehlerfrei durchläuft, `fib(10)` ohne Gedächtnis\n",
    "auf 177 Aufrufe kommt und mit Gedächtnis auf deutlich weniger, und `inorder` die\n",
    "Zahlen sortiert ausgibt.\n",
    "\n",
    "Notieren Sie am Ende in einer Markdown-Zelle, was der entscheidende Unterschied\n",
    "zwischen dem gemischten und dem sortierten Suchbaum ist — in zwei Sätzen."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
