210_rekursion.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rekursion\n",
    "\n",
    "### Fakultät"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# iterativ\n",
    "def fakultaet(n):\n",
    "    '''\n",
    "    n: ganze Zahl >= 0\n",
    "    returns: n! (= n Fakultät)\n",
    "    '''\n",
    "    result = 1\n",
    "    for i in range(1,n+1):\n",
    "        result = result * i\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# rekursiv \n",
    "def fakultaet(n):\n",
    "    '''\n",
    "    n: ganze Zahl >= 0\n",
    "    returns: n! (= n Fakultät)\n",
    "    '''\n",
    "    if n == 0: return 1\n",
    "    return n * fakultaet(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3628800"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fakultaet(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Weitere Beispiele"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1024"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def zweihoch(n):\n",
    "    '''\n",
    "    n: ganze Zahl >= 0\n",
    "    returns: 2 hoch n\n",
    "    '''\n",
    "    if n == 0: return 1\n",
    "    return 2 * zweihoch(n-1)\n",
    "\n",
    "zweihoch(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'suvreS'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def dreheUm(s):\n",
    "    '''\n",
    "    s: String\n",
    "    returns: den String s in umgedrehter Reihenfolge\n",
    "    '''\n",
    "    if len(s) == 0: return ''\n",
    "    return s[-1]+dreheUm(s[:-1])\n",
    "\n",
    "dreheUm('Servus')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5050"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def summe(n):\n",
    "    '''\n",
    "    n: positive ganze Zahl\n",
    "    returns: Die Summe der Zahlen von 1 bis n\n",
    "    '''\n",
    "    if n == 1: return 1\n",
    "    return n + summe(n-1)\n",
    "\n",
    "summe(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Türme von Hanoi\n",
    "\n",
    "<img src=\"./img/rekursion_01.png\" width=\"300\"/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hanoi(n, start, ziel, zwischen):\n",
    "    '''\n",
    "    n: ganze Zahl >= 0\n",
    "    start, ziel, zwischen: Strings, die 3 Stapel bezeichnen\n",
    "    returns: None, druckt Anweisungen für die Verlegung von n Scheiben von\n",
    "       Stapel start nach Stapel ziel unter Zuhilfenahme von Stapel zwischen\n",
    "       nach den Regeln der 'Türme von Hanoi'.\n",
    "    '''\n",
    "    if n == 0: return\n",
    "    hanoi(n-1,start,zwischen,ziel)\n",
    "    print(\"Scheibe\",n,\"von\",start,\"nach\",ziel)\n",
    "    hanoi(n-1,zwischen,ziel,start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Scheibe 1 von A nach B\n",
      "Scheibe 2 von A nach C\n",
      "Scheibe 1 von B nach C\n",
      "Scheibe 3 von A nach B\n",
      "Scheibe 1 von C nach A\n",
      "Scheibe 2 von C nach B\n",
      "Scheibe 1 von A nach B\n",
      "Scheibe 4 von A nach C\n",
      "Scheibe 1 von B nach C\n",
      "Scheibe 2 von B nach A\n",
      "Scheibe 1 von C nach A\n",
      "Scheibe 3 von B nach C\n",
      "Scheibe 1 von A nach B\n",
      "Scheibe 2 von A nach C\n",
      "Scheibe 1 von B nach C\n"
     ]
    }
   ],
   "source": [
    "hanoi(4,'A','C','B')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"./img/rekursion_02.png\" width=\"500\"/>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Fibonacci Zahlen\n",
    "\n",
    "<img src=\"./img/rekursion_04.png\" width=\"500\"/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    '''\n",
    "    n: positive ganze Zahl\n",
    "    returns: n-te Fibonacci Zahl\n",
    "    '''\n",
    "    if n <= 2: return 1\n",
    "    return fib(n-2) + fib(n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "832040\n",
      "1346269\n",
      "2178309\n",
      "3524578\n",
      "5702887\n",
      "9227465\n",
      "14930352\n",
      "24157817\n"
     ]
    }
   ],
   "source": [
    "for i in range(30,38):\n",
    "    print(fib(i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "832040\n",
      "1346269\n",
      "2178309\n",
      "3524578\n",
      "5702887\n",
      "9227465\n",
      "14930352\n",
      "24157817\n"
     ]
    }
   ],
   "source": [
    "def fib(n):\n",
    "    '''\n",
    "    n: positive ganze Zahl\n",
    "    returns: n-te Fibonacci Zahl\n",
    "    '''\n",
    "    if n <= 2: return 1\n",
    "    a,b = 1,1\n",
    "    for i in range(n-2):\n",
    "        c = a+b\n",
    "        a,b = b,c\n",
    "    return c\n",
    "\n",
    "for i in range(30,38):\n",
    "    print(fib(i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die rekursive Programmierung der Fibonacci Zahlen ist sehr unwirtschaftlich, da viele Berechnungen mehrfach durchgeführt werden.\n",
    "Die Berechnung folgt einer **Top-Down** Bewegung.\n",
    "\n",
    "Der bessere Ansatz folgt einer **Bottom-Up** Bewegung, bei der zunächst die kleineren Probleminstanzen gelöst werden. Durch speichern der notwendigen Zwischenergebnisse erreicht man schließlich die Lösung. Dieser Ansatz nennt sich \n",
    "**dynamische Programmierung**.\n",
    "\n",
    "Der rekursive Ansatz lässt sich retten durch **Memoization**. Um Mehrfachberechnungen zu vermeiden merkt man sich alle\n",
    "Berechnungen in einem dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(n,memo={}):\n",
    "    if n <= 2: return 1\n",
    "    if n in memo: return memo[n]\n",
    "    tmp = fib(n-2,memo) + fib(n-1,memo)\n",
    "    memo[n] = tmp\n",
    "    return tmp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "267914296"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fib(42)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Euklidscher Algorithmus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# klassischer Euklidscher Algorithums\n",
    "def euklid(a,b):\n",
    "    '''\n",
    "    a, b: positive ganze Zahlen\n",
    "    returns: größter gemeinsamer Teiler von a und b\n",
    "    '''\n",
    "    if a == b: return a\n",
    "    if a < b:\n",
    "        return euklid(a,b-a)\n",
    "    else:\n",
    "        return euklid(a-b,b)\n",
    "    \n",
    "euklid(84,54)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# moderner Euklidscher Algorithums\n",
    "def turboEuklid(a,b):\n",
    "    '''\n",
    "    a, b: positive ganze Zahlen\n",
    "    returns: größter gemeinsamer Teiler von a und b\n",
    "    '''\n",
    "    if b == 0: return a\n",
    "    return turboEuklid(b, a % b)\n",
    "\n",
    "turboEuklid(84,54)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Binäre Suche"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binaereSuche(a,x,i=0,j=None):\n",
    "    '''\n",
    "    a: sortierte Liste mit Zahlen\n",
    "    x: Zahl\n",
    "    i,j: ints zwischen 0 und len(a)-1\n",
    "    returns: True, wenn x im Bereich zwischen i und j (einschließlich) in\n",
    "       Liste a ist.\n",
    "    '''\n",
    "    if j is None: j = len(a)-1\n",
    "    if i > j: return False\n",
    "    mitte = (i + j) // 2\n",
    "    if a[mitte] == x: return True\n",
    "    if a[mitte] < x:\n",
    "        return binaereSuche(a,x,mitte+1,j)\n",
    "    else:\n",
    "        return binaereSuche(a,x,i,mitte-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "a = [2, 4, 6, 12, 22, 42, 49]\n",
    "print(binaereSuche(a,42))\n",
    "print(binaereSuche(a,13))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}