{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "95d22754-cc8b-4187-9bf2-214aa285c737",
   "metadata": {
    "editable": false,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "# Rekursion\n",
    "\n",
    "*\"Wer Rekursion verstehen will, muss vorher Rekursion verstehen.\"*\n",
    "\n",
    "Unter einer **rekursiven Funktion** versteht man eine Funktion, die **sich selbst wieder aufruft**.\n",
    "\n",
    "Damit diese Aufrufe nicht *unendlich* weitergehen und das Programm zu einem Ergebnis kommt, brauchen wir eine **Abbruchbedingung**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4390feea-e740-4eac-bc30-2170b5a50c6b",
   "metadata": {
    "editable": false,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "## Hinweis: Abbrechen der Ausführung\n",
    "\n",
    "Kommt es im Jupyter-Notbook zu einer *Endlosschleife* bzw. nicht abbrechende Rekursion, so würde das Programm ohne Ende weiter laufen.\n",
    "\n",
    "Läuft die Ausführung im Jupyter immer weiter (erkennbar am Stern vor der Zeile), so muss die Ausführung manuell gestoppt werden!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad00d229-4993-46b4-950b-2638d5632853",
   "metadata": {
    "editable": false,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "## Beispiel\n",
    "\n",
    "Die Summe von $1$ bis zu einer Zahl $n$ lässt sich auch rekursiv berechnen, denn es gilt:\n",
    "$$\\mathrm{summe}(1) = 1$$\n",
    "sowie\n",
    "$$\\mathrm{summe}(n) = n + \\mathrm{summe}(n-1)$$\n",
    "\n",
    "Eine rekursive Funktion lässt sich also folgendermaßen programmieren:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "f83dd8bc-1f01-4a34-8ea3-6bc2822ff47d",
   "metadata": {
    "editable": false,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[33m21\u001b[39m"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function summe(n) {\n",
    "    // Abbruchbedingung: wenn n===1 ist das Ergebnis auch 1\n",
    "    if (n === 1) return 1\n",
    "\n",
    "    // andernfalls ist das Ergebnis n + summe(n-1)\n",
    "    return n + summe( n-1 )\n",
    "}\n",
    "summe(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9116f0d3-2c22-4356-88de-3fa960ac5cc4",
   "metadata": {
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "Die Zeile `return n + summe( n-1 )` sorgt mit einem rekursiven Aufruf dazu, dass die Summe berechnet wird.\n",
    "\n",
    "Die erste Zeile `if (n === 1) return 1` ist dafür verantwortlich, dass die Aufrufe abbrechen."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Deno",
   "language": "typescript",
   "name": "deno"
  },
  "language_info": {
   "codemirror_mode": "typescript",
   "file_extension": ".ts",
   "mimetype": "text/x.typescript",
   "name": "typescript",
   "nbconvert_exporter": "script",
   "pygments_lexer": "typescript",
   "version": "5.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}