{ "cells": [ { "cell_type": "markdown", "id": "ec8e6f5d-a713-48f6-b93c-ed3197fd1255", "metadata": {}, "source": [ "# Rekurze\n", "\n", "Rekurzivní funkce je ta, jejíž vykonání volá samo sebe (a to i nepřímo). Jednoduchým případem je Fibonacciho posloupnost $f(N) = f(N-2) + f(N-1)$. Jejich složitost lze často vyjádřit pomocí vzorce:\n", "\n", "$T(n) = a T(\\frac{n}{b}) + f(n)$,\n", "\n", "kde $a$ je počet rekurzivních zavolání z jednoho průchodu funkce, $\\frac{n}{b}$ je velikost vstupu pro dané podproblémy (vstup $n$ je rozdělen na $b$ stejných částí) a $f(n)$ je složitost jednoho průchodu funkce. Typicky složitost rozdělení dat a složení podvýsledků dohromady.\n", "\n", "Složitost rekurzivních funkcí lze počítat různými způsoby:\n", "- Substituční metodou - Odhadem a následným ověřením skrze důkaz indukcí.\n", "- Metodou rekurzivních stromů - rozkreslením stromu voláním a sečtením složitosti.\n", "- Mistrovskou větou (Master theorem) - Master theorem nám říká, jak vyjdou rekurzivní stromy za určitých podmínek. Stačí nám tedy zkontrolovat podmínku a máme výsledek.\n", " - pokud $f(n) \\in \\mathrm{O}\\left(n^{\\log_b(a) - \\epsilon}\\right), \\epsilon > 0$, pak $T(n) \\in \\Theta \\left(n^{\\log_b(a)}\\right)$,\n", " - pokud $f(n) \\in \\Theta\\left(n^{\\log_b(a)}\\right)$, pak $T(n) \\in \\Theta\\left(n^{\\log_b(a)}\\log(n)\\right)$,\n", " - pokud $f(n) \\in \\Omega\\left(n^{\\log_b(a) + \\epsilon}\\right), \\epsilon > 0$, a $a f\\left(\\frac{n}{b}\\right) \\leq c f(n), c < 1$, pak $T(n) \\in \\Theta\\left(f(n)\\right)$." ] }, { "cell_type": "markdown", "id": "16325088-ffa1-4873-a68b-a69db920f9d9", "metadata": {}, "source": [ "**Řešená úloha 1:** Kolikrát bude zavolána funkce xyz() při zavolání rekur(5)?" ] }, { "cell_type": "code", "execution_count": null, "id": "fe481d43-c55a-406a-841e-a67fa8f95cc9", "metadata": {}, "outputs": [], "source": [ "def rekur(x):\n", " if x < 1: return\n", " rekur(x-1)\n", " xyz()\n", " rekur(x-2)" ] }, { "cell_type": "code", "execution_count": null, "id": "d2dcd530-cbf5-4f74-9601-98b45c0c0227", "metadata": {}, "outputs": [], "source": [ "calls = 0\n", "\n", "def xyz():\n", " global calls\n", " calls = calls + 1\n", "\n", "rekur(5)\n", "#print(calls)" ] }, { "cell_type": "markdown", "id": "553a525e-8172-4b76-93ee-18149a79a711", "metadata": {}, "source": [ "**Řešená úloha 3:** Napište rekurzivní funkci, která pro zadané číslo $N$ vypíše řetězec skládající se z $N$ jedniček následovaných $2N$ dvojkami. Pro dané NN bude funkce volat sama sebe právě NN-krát. Příklad: pro $N=2$ vypíše $112222$." ] }, { "cell_type": "code", "execution_count": null, "id": "d26000a8-466d-4ad1-ba1b-246035008823", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "c7c915fc-510a-4401-985c-6d52aa5548bc", "metadata": {}, "source": [ "**Úloha 6:** Určete, jakou hodnotu vypíše program po vykonání příkazu print(rekur(4))." ] }, { "cell_type": "code", "execution_count": null, "id": "d43d97d6-67cd-4270-a9ce-4e25f9835170", "metadata": {}, "outputs": [], "source": [ "def rekur(x):\n", " if x < 1: \n", " return 2\n", " return (rekur(x-1) + rekur(x-1))" ] }, { "cell_type": "markdown", "id": "9b4ae00e-bf73-48f5-be84-be3c0cd960e3", "metadata": {}, "source": [ "Co tato funkce počítá?" ] }, { "cell_type": "code", "execution_count": null, "id": "ca1685e0-2c4d-4d9a-8b3f-87dd5894bc19", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "79df4c23-09a8-4143-bb29-befa95809702", "metadata": {}, "source": [ "**Úloha 7:** Uvažujte podobnou funkci jako ve cvičení 2. Doplňte prázdná místa tak, aby vracela $x^y$." ] }, { "cell_type": "code", "execution_count": null, "id": "1813a2e3-c1f9-4541-8924-b7af1a5ae2c8", "metadata": {}, "outputs": [], "source": [ "def f(x, y):\n", " if #TODO: \n", " return #TODO\n", " return #TODO" ] }, { "cell_type": "markdown", "id": "200f8185-0a22-4063-aed0-5908ded27d56", "metadata": {}, "source": [ "**Úloha 8:** Daná funkce $ff$ je volána takto: $ff(a, b)$, $a$ i $b$ jsou celá kladná čísla. Napište vztah, který určí, kolikrát bude volána funkce $abc(x)$, v závislosti na hodnotě parametrů $a$, $b$." ] }, { "cell_type": "code", "execution_count": null, "id": "33c7215d-4b31-419c-84c0-b3b997f3b812", "metadata": {}, "outputs": [], "source": [ "def ff(x, p):\n", " if x > 0: ff(x-p, p)\n", " abc(x)\n", " if x > 0: ff(x-p, p)" ] }, { "cell_type": "markdown", "id": "2a3a77f7-b5b7-4684-ab74-715e91b9503f", "metadata": {}, "source": [ "**Úloha 16: Sierpińského koberce**\n", "\n", "Prvky pole $P_N$ o velikosti $3N×3N$ jsou pouze čísla $1$ a $0$.\n", "Obrázky níže znázorňují pole $P_N$ pro několik hodnot $N$, modrá barva představuje hodnotu $1$, bílá $0$. \n", "Napište kód, který pro dané $N$ vytvoří a vyplní pole $P$ podle daného vzoru.\n" ] }, { "cell_type": "code", "execution_count": null, "id": "9a19a734-152c-4216-a4d9-9fbd2dce702c", "metadata": {}, "outputs": [], "source": [ "!pip install numpy matplotlib" ] }, { "cell_type": "code", "execution_count": null, "id": "b0860b7e-4f75-4d39-856d-04a5db52e891", "metadata": {}, "outputs": [], "source": [ "def sierpin_carpet(array, #TODO):\n", " pass" ] }, { "cell_type": "code", "execution_count": null, "id": "e14ad122-e4ba-4bec-b356-7ed13d646aab", "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "\n", "N = 4\n", "\n", "array = np.zeros((3*N, 3*N))\n", "\n", "sierpin_carpet(array)" ] }, { "cell_type": "code", "execution_count": null, "id": "6311b7e5-4de8-44fa-9798-cb84eaccede9", "metadata": {}, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "\n", "plt.imshow(array, cmap='binary', vmin=0, vmax=1)\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "9561cf40-5eb4-449f-9c90-0ed208940cd0", "metadata": {}, "source": [ "**Úloha 17:**\n", "Seznamte se s [Ackermanovou funkcí](https://en.wikipedia.org/wiki/Ackermann_function#Definition:_as_m-ary_function).\n", "\n", "$$\n", "\\begin{equation*}A(n, m) = \\begin{cases}\n", "m + 1 & n = 0 \\\\\\\n", "A(n-1, 1) & n > 0, m = 0 \\\\\\\n", "A(n-1, A(n, m-1)) & n > 0, m > 0 \\\\\\\n", "\\end{cases}\n", "\\end{equation*}\n", "$$\n", "\n", "Zkuste spočítat hodnotu $A(4, 4)$." ] }, { "cell_type": "code", "execution_count": null, "id": "d7938565-328e-4eb3-8797-6e43bfb16156", "metadata": {}, "outputs": [], "source": [ "def ackerman(n, m):\n", " global calls\n", " calls += 1\n", " if n == 0:\n", " return m + 1\n", " elif n > 0 and m == 0:\n", " return ackerman(n-1, 1)\n", " elif n > 0 and m > 0:\n", " return ackerman(n-1, ackerman(n, m-1))\n" ] }, { "cell_type": "code", "execution_count": null, "id": "8a790654-d2c6-4e52-baaa-b717d825255a", "metadata": {}, "outputs": [], "source": [ "calls = 0\n", "\n", "print(ackerman(3,4), calls)" ] }, { "cell_type": "code", "execution_count": null, "id": "aec66cf9-67f4-49d1-a1e8-836714fb3d9f", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "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.13.5" } }, "nbformat": 4, "nbformat_minor": 5 }