131 lines
3.2 KiB
Plaintext
131 lines
3.2 KiB
Plaintext
{
|
|
"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
|
|
}
|