p1/predavanja/10 - Rekurzivne funkcije.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "05d6f947",
   "metadata": {},
   "source": [
    "# Rekurzivne funkcije\n",
    "\n",
    "Preden sploh začnemo, si oglejmo tale nesmiselni program."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "1e90fca9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(x):\n",
    "    return g(x) + 1\n",
    "\n",
    "def g(x):\n",
    "    return 2 * x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1dd12a1",
   "metadata": {},
   "source": [
    "Sme funkcija `f` poklicati funkcijo `g`, še preden je slednja definirana?\n",
    "\n",
    "Ne. Vendar je tudi ne. Funkcija `f` bo poklicala funkcijo `g` šele, ko pokličemo `f`. Recimo zdaj."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "8afd3359",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "11"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "01ec562a",
   "metadata": {},
   "source": [
    "Python vidi definicijo funkcije `f` in si jo zapomni; izvajati je ne poskuša, zato (še) ne naleti na klic funkcije `g`. Nato vidi definicijo funkcije `g`. Ko potem pokličemo `f`, `g` že obstaja in vse je v redu.\n",
    "\n",
    "Narobe bi bilo, če bi funkcijo poklicali prezgodaj."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "d60eb4bf",
   "metadata": {
    "tags": [
     "raises-exception"
    ]
   },
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'j' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[3], line 4\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mh\u001b[39m(x):\n\u001b[1;32m      2\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m j(x) \u001b[38;5;241m+\u001b[39m \u001b[38;5;241m1\u001b[39m\n\u001b[0;32m----> 4\u001b[0m h(\u001b[38;5;241m5\u001b[39m)\n\u001b[1;32m      6\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mj\u001b[39m(x):\n\u001b[1;32m      7\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[38;5;241m2\u001b[39m \u001b[38;5;241m*\u001b[39m h\n",
      "Cell \u001b[0;32mIn[3], line 2\u001b[0m, in \u001b[0;36mh\u001b[0;34m(x)\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mh\u001b[39m(x):\n\u001b[0;32m----> 2\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m j(x) \u001b[38;5;241m+\u001b[39m \u001b[38;5;241m1\u001b[39m\n",
      "\u001b[0;31mNameError\u001b[0m: name 'j' is not defined"
     ]
    }
   ],
   "source": [
    "def h(x):\n",
    "    return j(x) + 1\n",
    "\n",
    "h(5)\n",
    "\n",
    "def j(x):\n",
    "    return 2 * h"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c9071d9c",
   "metadata": {},
   "source": [
    "Ampak tega ne bomo počeli."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b4954657",
   "metadata": {},
   "source": [
    "## Sodolihi in lihosodi\n",
    "\n",
    "Ni, da bi govoril. Bila sta oni dan dva lena študenta, Jože in Benjamin. Za domačo nalogo bi morala napisati naslednji funkciji.\n",
    "\n",
    "- `sodolihi(s)` prejme seznam celih števil in vrne `True`, če se v njem izmenjujejo **soda in liha števila, začenši s sodim**. Če ni tako, vrne `False`. Za prazen seznam vrne `True`.\n",
    "- `lihosodi(s)` prejme seznam celih števil in vrne `True`, če se v njem izmenjujejo **liha in soda števila, začenši s lihim**. Če ni tako, vrne `False`. Za prazen seznam vrne `True`.\n",
    "\n",
    "Ker sta imela domačih nalog iz programiranja dovolj, sta se dogovorila, da vsak sprogramira eno funkcijo, potem pa si ju izmenjata in malo preimenujeta spremenljivke v naivni veri, da ju ne bomo zalotili.\n",
    "\n",
    "Jože ni bil le len, temveč tudi zvit. Razmišljal je, da bo Benjamin sprogramiral funkcijo `lihosodi`, torej ne bo nič narobe, če njegova funkcija kliče Benjaminovo. In je naredil kar takole."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "d4f01937",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sodolihi(s):\n",
    "    if s == []:\n",
    "        return True\n",
    "    if s[0] % 2 == 1:\n",
    "        return False\n",
    "    return lihosodi(s[1:])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ec7eb61",
   "metadata": {},
   "source": [
    "Preveril je prazen seznam in prvi element, ostanek - v katerem se morajo izmenjevati lihi in sodi, začenši z lihim - pa prepustil Benjaminu.\n",
    "\n",
    "Tudi Benjamin ni le len, zvit. Zvit je natančno na isti način kot Jože. Češ, poskrbim za prazen seznam in za prvi element, ostalo lahko tako ali tako prepustim Jožetu. In je sprogramiral"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "79c5a7e3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def lihosodi(s):\n",
    "    if s == []:\n",
    "        return True\n",
    "    if s[0] % 2 == 0:\n",
    "        return False\n",
    "    return sodolihi(s[1:])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92681465",
   "metadata": {},
   "source": [
    "Jožetova funkcija bo očitno delovala, če bo delovala Benjaminova. In obratno: Benjaminova bo delovala, če bo Jožetova. Skratka, obe funkciji bosta delovali, če bosta delovali obe funkciji.\n",
    "\n",
    "Vprašanje je samo ... bo Python to res dovolil? Bo. Funkcije v Pythonu smejo klicati druge funkcije. In nič jim ne preprečuje, da slednje ne bi poklicale nazaj. (Za globlje misleče: da, lahko si zamislimo jezik - oziroma način izvajanja - v katerem to ne bi šlo. Takšne so bile zelo stare različice Fortrana; omejitev je bila v tem, da so bili argumenti funkcije zapisani na določenem mestu v pomnilniku. Kmalu so odkrili, da tako ne gre in je argumente in lokalne spremenljivke bolj smiselno shranjevati na skladu.)\n",
    "\n",
    "Sicer pa: poskusimo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "ee4aefb7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sodolihi([4, 7, 6, 1, 8])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "6130cb24",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sodolihi([4, 7, 6, 2, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4ff085a",
   "metadata": {},
   "source": [
    "Če hočemo slediti poteku, lahko naredimo funkciji zgovornejši."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "fb24e54d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sodolihi(s):\n",
    "    print(\"Sodolihi preverja\", s)\n",
    "    if s == []:\n",
    "        print(\"- prazen seznam: ok\")\n",
    "        return True\n",
    "    if s[0] % 2 == 1:\n",
    "        print(\"- prvi element ni ok\")\n",
    "        return False\n",
    "    print(\"- začatek je v redu, potrebno bo preveriti ostanek\")\n",
    "    ok = lihosodi(s[1:])\n",
    "    print(f\"Sodolihi je izvedel, da je ostanek {ok} in sporoča, da je {s} {ok}.\")\n",
    "    return ok\n",
    "\n",
    "def lihosodi(s):\n",
    "    print(\"Lihosodi preverja\", s)\n",
    "    if s == []:\n",
    "        print(\"- prazen seznam: ok\")\n",
    "        return True\n",
    "    if s[0] % 2 == 0:\n",
    "        print(\"- prvi element ni ok\")\n",
    "        return False\n",
    "    print(\"- začatek je v redu, potrebno bo preveriti ostanek\")\n",
    "    ok = sodolihi(s[1:])\n",
    "    print(f\"Lihosodi je izvedel, da je ostanek {ok} in sporoča, da je {s} {ok}.\")\n",
    "    return ok"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "f2cbb795",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sodolihi preverja [4, 7, 6, 1, 8]\n",
      "- začatek je v redu, potrebno bo preveriti ostanek\n",
      "Lihosodi preverja [7, 6, 1, 8]\n",
      "- začatek je v redu, potrebno bo preveriti ostanek\n",
      "Sodolihi preverja [6, 1, 8]\n",
      "- začatek je v redu, potrebno bo preveriti ostanek\n",
      "Lihosodi preverja [1, 8]\n",
      "- začatek je v redu, potrebno bo preveriti ostanek\n",
      "Sodolihi preverja [8]\n",
      "- začatek je v redu, potrebno bo preveriti ostanek\n",
      "Lihosodi preverja []\n",
      "- prazen seznam: ok\n",
      "Sodolihi je izvedel, da je ostanek True in sporoča, da je [8] True.\n",
      "Lihosodi je izvedel, da je ostanek True in sporoča, da je [1, 8] True.\n",
      "Sodolihi je izvedel, da je ostanek True in sporoča, da je [6, 1, 8] True.\n",
      "Lihosodi je izvedel, da je ostanek True in sporoča, da je [7, 6, 1, 8] True.\n",
      "Sodolihi je izvedel, da je ostanek True in sporoča, da je [4, 7, 6, 1, 8] True.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sodolihi([4, 7, 6, 1, 8])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "67b13c34",
   "metadata": {},
   "source": [
    "## Dodatna naloga: samisodi\n",
    "\n",
    "Opogumljena z uspehom sta se Jože in Benjamin lotila dodatne naloge:\n",
    "\n",
    "- napiši funkcijo `samisodi(s)`, ki vrne `True`, če podani seznam celih števil ne vsebuje nobenega lihega števila (in `False`, če ga).\n",
    "\n",
    "Zdaj je bilo potrebno napisati le eno funkcijo, tako da si nista mogla deliti dela. Idejo pa sta obdržala. Poglejmo, kako jima je uspelo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "a323eb4e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def samisodi(s):\n",
    "    if s == []:\n",
    "        return True\n",
    "    if s[0] % 2 == 1:\n",
    "        return False\n",
    "    return samisodi(s[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "18c43a2c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "samisodi([6, 8, 10, 2, 4, 6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "bfdc4652",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "samisodi([6, 4, 5, 2, 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3d6bd90f",
   "metadata": {},
   "source": [
    "Ideja je, torej enaka. Funkcija preveri prazen seznam in prvi element, ostalo delo pa prepusti, no, sama sebi.\n",
    "\n",
    "# Kako (ne) pisati rekurzivne funkcije\n",
    "\n",
    "Funkcijam, ki kličejo same sebe, pravimo *rekurzivne funkcije*. Študenti se jih iz nekega razloga bojijo. Morda zato, ker zahtevajo drugačen način razmišljanja, ali pa jih je, preprosto, strah, kako bo to delovalo. Če kaj, potem rekurzivne funkcije zahtevajo razsvetljenje. V nekem trenutku postanejo, preprosto *normalne* in jih pišemo enako brezskrbno kot \"navadne\".\n",
    "\n",
    "Prej pa nam mora priti nekaj stvari, povezanih z njimi v rutino."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7649baa8",
   "metadata": {},
   "source": [
    "## Korak bližje rešitvi\n",
    "\n",
    "Razlog, da rekurzivne funkcije delujejo, je, da smo z vsakim klicem bližje rešitvi. Poglejmo tale primer nesrečne funkcije, ki naj bi računala vsoto elementov seznama `s`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "450f1863",
   "metadata": {},
   "outputs": [],
   "source": [
    "def vsota(s):\n",
    "    return vsota(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "7b6e2513",
   "metadata": {
    "tags": [
     "raises-exception"
    ]
   },
   "outputs": [
    {
     "ename": "RecursionError",
     "evalue": "maximum recursion depth exceeded",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mRecursionError\u001b[0m                            Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[14], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m vsota([\u001b[38;5;241m2\u001b[39m, \u001b[38;5;241m5\u001b[39m, \u001b[38;5;241m8\u001b[39m])\n",
      "Cell \u001b[0;32mIn[13], line 2\u001b[0m, in \u001b[0;36mvsota\u001b[0;34m(s)\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mvsota\u001b[39m(s):\n\u001b[0;32m----> 2\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m vsota(s)\n",
      "Cell \u001b[0;32mIn[13], line 2\u001b[0m, in \u001b[0;36mvsota\u001b[0;34m(s)\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mvsota\u001b[39m(s):\n\u001b[0;32m----> 2\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m vsota(s)\n",
      "    \u001b[0;31m[... skipping similar frames: vsota at line 2 (2971 times)]\u001b[0m\n",
      "Cell \u001b[0;32mIn[13], line 2\u001b[0m, in \u001b[0;36mvsota\u001b[0;34m(s)\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mvsota\u001b[39m(s):\n\u001b[0;32m----> 2\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m vsota(s)\n",
      "\u001b[0;31mRecursionError\u001b[0m: maximum recursion depth exceeded"
     ]
    }
   ],
   "source": [
    "vsota([2, 5, 8])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc7dafea",
   "metadata": {},
   "source": [
    "To ne gre. Ta funkcija je prepustila *vse* delo sama sebi. Kliče se skoraj v nedogled - oziroma toliko časa, dokler se Pythonu zazdi, da je to že preveč in sproži napako \"maximum recursion depth exceeded\".\n",
    "\n",
    "Pravilna rešitev je"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "ace2cfdb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def vsota(s):\n",
    "    if s == []:\n",
    "        return 0\n",
    "    return s[0] + vsota(s[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "f8edcab2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vsota([2, 5, 8])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df1cc4b5",
   "metadata": {},
   "source": [
    "Ta, druga različica, naredi en korak: k prvemu elementu prišteje vsoto *ostalih*. Seznam, ki ga je potrebno sešteti, je v vsakem klicu za en element krajši; prej ko slej bomo prišli do praznega seznama.\n",
    "\n",
    "Razliko med (napačno) prvo in (pravilno) drugo obliko vidimo, če funkciji opišemo v slovenščini.\n",
    "\n",
    "- Druga pravi, da vsoto seznama dobimo tako, da k prvemu elementu prištejemo vsoto ostalih.\n",
    "- Prva pravi, da vsoto seznama dobimo tako, da izračunamo vsoto seznama.\n",
    "\n",
    "Druga zveni kot načrt. Prva zveni kot neumnost.\n",
    "\n",
    "Pravilno napisano rekurzivno funkcijo se da navadno tudi lepo opisati. Seznam vsebuje same sode elemente, če je prazen, ali pa je prvi element sod in so sodi tudi vsi ostali."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "88db907a",
   "metadata": {},
   "source": [
    "## Robni pogoj\n",
    "\n",
    "Rekurzivna funkcija bo torej z vsakim klicem bližje koncu. Na koncu, v nekem klicu (ali več klicih, kot bomo videli na primerih rekurzije na rodbinskem drevesu) ne bo več klica naprej. To se bo zgodilo takrat, ko bo problem (na primer podani seznam) že tako preprost, da bomo vedeli odgovor brez računanja. Prazni seznami ne vsebujejo lihih elementov. Vsota elementov praznih seznamov je 0.\n",
    "\n",
    "Rekurzivna funkcija se bo zato pogosto začela z nekim *robnim pogojem*, ki bo preverjal, ali je delo končano in nadaljnji klici niso več potrebni. Robni pogoj bo včasih impliciten, skrit. Tako bo recimo, ko bo v preiskovanju rodbinskega drevesa funkcija poklicala samo sebe za vse otroke določene osebe. Za osebe brez otrok se pač ne bo več poklicala. Tam ne bo nobenega `if`, pač pa se bo klic nahajal znotraj zanke, ki se morda ne bo izvedla nikoli."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d2609ad",
   "metadata": {},
   "source": [
    "## Rekurzija in lokalne spremenljivke\n",
    "\n",
    "Ena od težav pri razumevanju rekurzije izhaja iz napačne predstave o lokalnih spremenljivkah. Poglejmo si bolj zgovorno različico funkcije `sum`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "750d85c0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def vsota(s):\n",
    "    print(\"Računam vsoto\", s)\n",
    "    if s == []:\n",
    "        print(\"Prazen seznam, vračam 0.\")\n",
    "        return 0\n",
    "    prvi = s[0]\n",
    "    ostanek = s[1:]\n",
    "    print(\"Izvedeti moram vsoto\", ostanek)\n",
    "    vsota_ost = vsota(ostanek)\n",
    "    print(f\"Izvedel sem, da je vsota {ostanek} enaka {vsota_ost}; vračam {prvi} + {vsota_ost} = {prvi + vsota_ost}\")\n",
    "    return prvi + vsota_ost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "20c26412",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Računam vsoto [2, 5, 3, 1]\n",
      "Izvedeti moram vsoto [5, 3, 1]\n",
      "Računam vsoto [5, 3, 1]\n",
      "Izvedeti moram vsoto [3, 1]\n",
      "Računam vsoto [3, 1]\n",
      "Izvedeti moram vsoto [1]\n",
      "Računam vsoto [1]\n",
      "Izvedeti moram vsoto []\n",
      "Računam vsoto []\n",
      "Prazen seznam, vračam 0.\n",
      "Izvedel sem, da je vsota [] enaka 0; vračam 1 + 0 = 1\n",
      "Izvedel sem, da je vsota [1] enaka 1; vračam 3 + 1 = 4\n",
      "Izvedel sem, da je vsota [3, 1] enaka 4; vračam 5 + 4 = 9\n",
      "Izvedel sem, da je vsota [5, 3, 1] enaka 9; vračam 2 + 9 = 11\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "11"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vsota([2, 5, 3, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8eca98c3",
   "metadata": {},
   "source": [
    "Opazujte zadnje izpise: funkcija izpiše vrednost `ostanek`, in ta je najprej `[]`, potem `[1]`, nato `[3, 1]` in potem `[5, 3, 1]`.\n",
    "\n",
    "Lokalne spremenljivke niso *lokalne spremenljivke funkcije*, temveč *lokalne spremenljivke klica funkcije*. Nova spremenljivka `ostanek` nastane ob vsakem klicu funkcije in stari, prejšnji, \"čakajoči\" klic obdrži staro spremenljivko s staro vrednostjo. (Da ne bo zmotilo koga, ki razume kaj več, se moram še popraviti: ime `ostanek` se v vsakem klicu nanaša na drug objekt.)\n",
    "\n",
    "Ko torej znotraj rekurzije rečemo `ostanek = s[1:]`, ne pokvarimo vrednosti `ostanek` iz \"čakajočega\" klica."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d349b49",
   "metadata": {},
   "source": [
    "## Rekurzija in globalne spremenljivke\n",
    "\n",
    "Če dam študentom napisati rekurzivno funkcijo v slogu\n",
    "\n",
    "- napiši funkcijo `sodi(s)`, ki vrne seznam, ki vsebuje vse sode elemente seznama `s`,\n",
    "\n",
    "se navadno zgodi nekaj takšnega."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "80f128e9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sodi(s):\n",
    "    t = []\n",
    "    if s == []:\n",
    "        return t\n",
    "    if s[0] % 2 == 0:\n",
    "        t.append(s[0])\n",
    "    sodi(s[1:])\n",
    "    return t"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d9b80576",
   "metadata": {},
   "source": [
    "Logika je v tem, da funkcija poskrbi za prvi element - če je sod, ga doda v `t` - nato pa se rekurzivno pokliče z namenom, da bi v `t` dodala še vse ostale sode elemente.\n",
    "\n",
    "Žal ne deluje."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "ce2eb51f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sodi([2, 5, 3, 8, 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "94fd7798",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sodi([3, 4, 8, 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bef54fc6",
   "metadata": {},
   "source": [
    "Težava je prav v tem, da je `t` lokalna spremenljivka *klica*. V vsakem klicu dobimo nov `t`, vanj morda dodamo en element - v rekurzivnem klicu pa se zgodba ponovi z novim `t`.\n",
    "\n",
    "Študent zadevo reši tako, da `t` spremeni v globalno spremenljivko."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "fbd2b15d",
   "metadata": {},
   "outputs": [],
   "source": [
    "t = []\n",
    "\n",
    "def sodi(s):\n",
    "    if s == []:\n",
    "        return t\n",
    "    if s[0] % 2 == 0:\n",
    "        t.append(s[0])\n",
    "    sodi(s[1:])\n",
    "    return t"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f0f5dce",
   "metadata": {},
   "source": [
    "To \"deluje\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "ff29b4aa",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 8, 0]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sodi([2, 5, 3, 8, 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4f523be8",
   "metadata": {},
   "source": [
    "Ampak samo enkrat."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "ac6106c7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 8, 0, 4, 8, 0]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sodi([3, 4, 8, 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "216346b5",
   "metadata": {},
   "source": [
    "Seznama `t` nihče ne sprazni. Plan C je, da spremenljivko `t` spraznimo na začetku funkcije."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "e2af977d",
   "metadata": {},
   "outputs": [],
   "source": [
    "t = []\n",
    "\n",
    "def sodi(s):\n",
    "    t.clear()\n",
    "    if s == []:\n",
    "        return t\n",
    "    if s[0] % 2 == 0:\n",
    "        t.append(s[0])\n",
    "    sodi(s[1:])\n",
    "    return t"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "740c8ee0",
   "metadata": {},
   "source": [
    "Tudi to ne gre."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "687bf6a3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sodi([2, 5, 3, 8, 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "32e1ea00",
   "metadata": {},
   "source": [
    "Zdaj vsak klic pobriše vse, kar se je zgodilo doslej - do zadnjega, ki prav tako izprazni seznam in vanj ne doda ničesar, saj je `s` prazen.\n",
    "\n",
    "Rekurzija in globalne spremenljivke se ne marajo. (Če ne veste točno, kaj delate.)\n",
    "\n",
    "Pravilna rešitev je takšna: če je prvi element sod, vrnemo seznam, ki vsebuje ta element in vse sode elemente ostanka. Sicer vrnemo sode elemente ostanka."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "5e75170e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sodi(s):\n",
    "    if s == []:\n",
    "       return []\n",
    "    if s[0] % 2 == 0:\n",
    "        return [s[0]] + sodi(s[1:])\n",
    "    else:\n",
    "        return sodi(s[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "784d7b20",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 8, 0]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sodi([2, 5, 3, 8, 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1e94646",
   "metadata": {},
   "source": [
    "V zadnji rešitvi smo \"razmišljali rekurzivno\": funkcijo smo poklicali s krajšim seznamom in k dobljeni rešitvi dodali, kar je bilo treba (prvi element) (če je bilo treba). V prejšnjih, napačnih poskusih, je bila funkcija rekurzivna, razmišljanje pa ne. Rekurzivni klici so dodajali v isti seznam, vendar je rekurzija služila le kot zamenjava za zanko.\n",
    "\n",
    "Razlika se vidi: v pravilni rešitvi smo uporabili rezultat rekurzivnega klica. V napačnih smo ga zavrgli in nekako računali na \"stranski učinek\" klica - dodajanje v seznam."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21e52e04",
   "metadata": {},
   "source": [
    "## Akumulator\n",
    "\n",
    "Zanemariti rezultat in uporabiti stranski učinek sicer ni nujno narobe. Vendar si je potrebno v tem primeru celotno funkcijo zamisliti drugače. Napisali bomo funkcijo, ki kot argument prejme seznam celih števil in še en seznam, v katerega mora zložiti vse sode elemente prvega seznama"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "56dee718",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sodi(s, t):\n",
    "    if s == []:\n",
    "        return\n",
    "    if s[0] % 2 == 0:\n",
    "        t.append(s[0])\n",
    "    sodi(s[1:], t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "4776b4fb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 8, 0]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "e = []\n",
    "sodi([2, 5, 3, 8, 0], e)\n",
    "\n",
    "e"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f4ea2b9",
   "metadata": {},
   "source": [
    "Študenti znajo sproducirati nekaj takšnega. Nekateri bi poskušali na podoben način reševati tudi prvo nalogo in sicer tako, da bi ignorirali navodila naloge, ki pravijo, da bo `sodi` dobil le en argument, ter mu dodali `t`, ki ima privzeto vrednost `[]`. To ne deluje, ker spreminjanje `t`-ja potem spreminja privzeto vrednost. Pač pa gre tako:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "b4298d6c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sodi(s, t=None):\n",
    "    if t is None:\n",
    "        t = []\n",
    "    if s == []:\n",
    "        return t\n",
    "    if s[0] % 2 == 0:\n",
    "        t.append(s[0])\n",
    "    return sodi(s[1:], t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "b45bb3c2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 8, 0]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sodi([2, 5, 3, 8, 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c328de88",
   "metadata": {},
   "source": [
    "V prvi rešitvi, kjer smo imel `sodi(s, t)`, je bila rekurzija praktično zamenjava za zanko. Druga je še grša, saj je čuden križanec med temi, ki dopolnjujejo podani seznam in onimi, ki morajo vračati (nov) seznam.\n",
    "\n",
    "Če nam je všeč ali ne: pišemo tudi takšne rekurzivne funkcije. Argument, ki si ga podajamo, je \"akumulator\", v katerega se tekom rekurzije nabira rezultat in zadnji klic ga vrne, da si ga ostali podajajo nazaj.\n",
    "\n",
    "Funkcije v tej obliki znajo biti učinkovitejše. Zgodi se, da je lažje dopolnjevati akumulator kot stalno nekaj seštevati (ali karkoli že). Predvsem pa znajo nekateri jeziki pospešiti izvajanje *repne rekurzije*.\n",
    "\n",
    "## Repna rekurzija\n",
    "\n",
    "Tole nima zveze s Pythonom: Python tega ne zna. Po trditvah njegovega avtorja tudi nikoli ne bo znal, saj to za Python ni zanimivo.\n",
    "\n",
    "Gre pa za to: ko rekurzivna funkcija kliče samo sebe, mora biti ohranjena \"sled\" klicev: vedeti je potrebno, kdo je klical koga in komu mora vrniti rezultat. Poleg tega je potrebno ohranjati lokalne spremenljivke - kot recimo `ostanek`, ki smo ga videli nekaj razdelkov nazaj.\n",
    "\n",
    "Če je rekurzivni klic zadnja, ampak čisto čisto zadnja stvar, ki jo naredimo v funkciji, in na koncu zgolj vrnemo rezultat tega klica - ne da bi mu, recimo, še kaj prišteli ali pa ga prišteli *k* čemu - potem takšni rekurziji rečemo *repna rekurzija*. V tem primeru \n",
    "\n",
    "- ni potrebno pomnjenje lokalnih spremenljivk kličočih funkcij. Nobenega \"`ostanka`\" se nikoli nihče več ne bo dotikal.\n",
    "- ni potrebno vračati rezultata tistemu, ki je poklical funkcijo, temveč tistemu, ki je, če citiramo Vonneguta, vse skupaj začel.\n",
    "\n",
    "Zanimivo je predvsem slednje. Pokličemo funkcijo `sodi`. Ta pokliče sebe. Pokliče sebe. Pokliče sebe ... In rezultati se vračajo med temi klici nazaj -- vrne sebi, vrne sebi, vrne sebi ... in na koncu vrne nam. Če je rekurzija repna, lahko na koncu vrne kar nam in preskoči vse \"sebi\".\n",
    "\n",
    "Takšna rekurzija je veliko hitrejša. Jeziki, v katerih ni spremenljivk temveč le konstante in zato nimajo zank temveč le rekurzijo, zato praktično *morajo* optimizirati repno rekurzijo - programerji pa sestavljati funkcije, v katerih je rekurzivni klic zadnje, kar naredijo. Python ni eden od teh jezikov, zato tega ne optimizira. Z repno rekurzijo v Pythonu ne pridobimo ničesar."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1ed7e32e",
   "metadata": {},
   "source": [
    "## Rekurzija lahko eksplodira\n",
    "\n",
    "Zdaj pa napišimo funkcijo, ki vrne največje število v (nepraznem) seznamu."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "f5148059",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maks(s):\n",
    "    if len(s) == 1:\n",
    "        return s[0]\n",
    "    if s[0] > maks(s[1:]):\n",
    "        return s[0]\n",
    "    else:\n",
    "        return maks(s[1:]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "e3dca3ea",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maks([2, 3, 10, 5, 8])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "ffb3f37a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maks([2, 3, 8, 10])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "79290e4a",
   "metadata": {},
   "source": [
    "Deluje že, deluje. Ampak za kakšno ceno! Ob vsakem klicu izpišimo zvezdico "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "d8b288aa",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maks(s):\n",
    "    print(\"*\")\n",
    "    if len(s) == 1:\n",
    "        return s[0]\n",
    "    if s[0] > maks(s[1:]):\n",
    "        return s[0]\n",
    "    else:\n",
    "        return maks(s[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "c1164db9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maks([2, 3, 8, 10])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "85050483",
   "metadata": {},
   "source": [
    "Človek bi pričakoval nekako štiri zvezdice ne 15."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "e300a340",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maks([2, 3, 5, 8, 10])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c28c67ea",
   "metadata": {},
   "source": [
    "Tule pa jih je, če prav štejem, 31! En element več - dvakrat več zvezdic!\n",
    "\n",
    "Težava je v tem, da funkcija `maks` dvakrat pokliče samo sebe. Tudi v običajnih funkcijah ni lepo, če dvakrat pokličemo neko funkcijo z enakimi argumenti. Če gre za rekurzivno funkcijo, pa je to usodno. Funkcija `maks` dvakrat pokliče sebe. Ta v vsakem od teh dveh klicev dvakrat pokliče sebe - pa imamo štiri klice. Če vsak od teh štirih klicev dvakrat pokliče sebe, smo pri osmih klicih, iz teh osmih jih nastane šestnajst in iz šestnajstih dvaintrideset. (Eden manj je zato, ker ne gremo do praznega seznama temveč do seznama z enim elementom.)\n",
    "\n",
    "V času epidemije so nekateri prvič slišali besedno zvezo *eksponentna rast* in jo zdaj na veliko uporabljajo kot sinonim za *hitro rast*. To ni isto. Nekaj je eksponentno, če se njegova velikost (trajanje, vrednost, karkoli že) v vsakem koraku pomnoži z nekim faktorjem. No, to kar se dogaja tule, je primer *eksponentne rasti*.\n",
    "\n",
    "Zdravilo je enostavno. Funkcija se mora izogniti podvojenim klicem. Namesto"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "c6e3ff75",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maks(s):\n",
    "    print(\"*\")\n",
    "    if len(s) == 1:\n",
    "        return s[0]\n",
    "    if s[0] > maks(s[1:]):\n",
    "        return s[0]\n",
    "    else:\n",
    "        return maks(s[1:])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "949657f6",
   "metadata": {},
   "source": [
    "napišemo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "b01dc735",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maks(s):\n",
    "    print(\"*\")\n",
    "    if len(s) == 1:\n",
    "        return s[0]\n",
    "    m = maks(s[1:])\n",
    "    if s[0] > m:\n",
    "        return s[0]\n",
    "    else:\n",
    "        return m"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6c8d8421",
   "metadata": {},
   "source": [
    "pa bo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "6fcfc196",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maks([2, 3, 5, 8, 10])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af0b0850",
   "metadata": {},
   "source": [
    "## Izogibanje neizogibni eksploziji\n",
    "\n",
    "Imamo `n` stolov, na katere bomo posedli fante. Koliko jih posedemo - enega, dva, pet, več ... - je vseeno. Lahko posedemo tudi nobenega, se pravi, pustimo vse stole prazne. Pomembno je le tole: ker so fantje poredni, mora biti med dvema zasedenima stoloma vsaj en prost, da se ne bodo tepli.\n",
    "\n",
    "Vzemimo, recimo, šest stolov. Možni razporedi so\n",
    "\n",
    "```\n",
    "*.*.*. (1)\n",
    "*.*..* (2)\n",
    "*.*... (3)\n",
    "*..*.* (4)\n",
    "*..*.. (5)\n",
    "*...*. (6)\n",
    "*....* (7)\n",
    "*..... (8)\n",
    ".*.*.* (9)\n",
    ".*.*.. (10)\n",
    ".*..*. (11)\n",
    ".*...* (12)\n",
    ".*.... (13)\n",
    "..*.*. (14)\n",
    "..*..* (15)\n",
    "..*... (16)\n",
    "...*.* (17)\n",
    "...*.. (18)\n",
    "....*. (19)\n",
    ".....* (20)\n",
    "...... (21)\n",
    "```\n",
    "\n",
    "V nekaterih primerih smo posedli tri fante, v nekaterih manj, v zadnjem celo nobenega. Vseh možnih razporedov je 21.\n",
    "\n",
    "Znamo napisati funkcijo, ki izračuna število razporedov za `n` stolov?\n",
    "\n",
    "Znamo, in preprosteje bo, če bo rekurzivna. Takole razmišljamo: prvi sedež bo bodisi zaseden bodisi prazen. Razporedov, v katerih je prvi stol zaseden, je toliko, kolikor je razporedov na `n - 2` stolih. Če je prvi zaseden, bo namreč drugi prazen in razporejamo lahko le še `n - 2` stolov. Če pa je prvi prazen, je razporedov toliko, kolikor je razporedov na `n - 1` stolih.\n",
    "\n",
    "Ostane nam še robni pogoj. Če je stolov 0, je razpored le `1`. Če je stol eden, sta razporeda dva: stol je poln ali prazen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "1f67d1e5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def razporedov(n):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    if n == 1:\n",
    "        return 2\n",
    "    return razporedov(n - 1) + razporedov(n - 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "708797f2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "21"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "razporedov(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c2b17f07",
   "metadata": {},
   "source": [
    "Upam, da si, dragi bralec, med tistimi, ki so prepoznali gornjo funkcijo. Gre za Fibonacijevo zaporedje: vsak element zaporedja je enak vsoti prejšnjih."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "595c44a0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "5\n",
      "8\n",
      "13\n",
      "21\n",
      "34\n",
      "55\n",
      "89\n"
     ]
    }
   ],
   "source": [
    "for i in range(10):\n",
    "    print(razporedov(i))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16e2faaf",
   "metadata": {},
   "source": [
    "Fibonacijevega zaporedja nismo privlekli zaradi kakega predpisa, ki veleval, da gre za obvezno sestavino vsakega predavanja o rekurziji. Ne. Privlekli smo ga zaradi zvezdic."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "f1281fb2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def razporedov(n):\n",
    "    print(\"*\")\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    if n == 1:\n",
    "        return 2\n",
    "    return razporedov(n - 1) + razporedov(n - 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "e7913fda",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "razporedov(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "353c72ca",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "21"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "razporedov(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d318fd5",
   "metadata": {},
   "source": [
    "Spet je počilo. Eksplodiralo. Vendar tokrat nismo nič krivi. Prej smo brez potrebe dvakrat zapored poklicali isto funkcijo z istimi argumenti. Zdaj ne - zdaj jo pokličemo z različnimi.\n",
    "\n",
    "Razlog za eksplozijo je, seveda, v tem, da pri reševanju za `n` stolov pokličemo `n - 1` in `n - 2`. Za `n - 1` pa spet pokličemo `n - 2`. Vsak od dveh klicev za `n - 2` pokliče `n - 3` (ki ga sicer pokliče tudi `n - 1`) tako naprej. (Razmislite, koliko klicev je to. Namig: odgovor bo spet povezan s Fibonacijevimi števili, le ritensko.)\n",
    "\n",
    "Ko gre za Fibonacijeva števila, je rešitev očitna: namesto da bi jih računali rekurzivno, nazaj, jih računamo iterativno, naprej, tako kot vsi normalni ljudje in to že nekje od drugega tedna predavanj.\n",
    "\n",
    "Zgodi pa se, da naletimo na nalogo - študenti računalništva jih vidijo nesluteno število v drugem letniku pri Algoritmih in podatkovnih strukturah, predvsem pri dinamičnem programiranju - kjer je računanje nazaj, z rekurzijo, veliko preprostejše kot iterativno, naprej."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7ba7071c",
   "metadata": {},
   "source": [
    "## Memoizacija\n",
    "\n",
    "Tu nas reši trik: funkcija si mora zapomniti rezultat klica z določenimi argumenti. Ko jo naslednjič pokličemo z enakimi argumenti, ničesar ne računa, temveč le vrne, kar je naračunala in vrnila v prejšnjem klicu s takimi argumenti.\n",
    "\n",
    "Kako izvesti *memoizacijo*, je odvisno od jezika. V Pythonu funkcijo dekoriramo, ovijemo v drugo funkcijo, ki prestreza klice in pomni rezultate. Dekoriranje funkcij v Pythonu je splošnejši mehanizem, ki ga lahko uporabimo za marsikaj. O njem se ne bomo učili (tole je vendarle tečaj programiranja, ne Pythona), tule bomo le pogledali, kaj nam je storiti, da preprečimo pretirano število rekurzivnih klicev."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "c6f34a3a",
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import cache\n",
    "\n",
    "@cache\n",
    "def razporedov(n):\n",
    "    print(\"*\")\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    if n == 1:\n",
    "        return 2\n",
    "    return razporedov(n - 1) + razporedov(n - 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "94179f9f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n",
      "*\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "21"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "razporedov(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c5b2d940",
   "metadata": {},
   "source": [
    "Šest stolov, sedem zvezdic. Zadnja je za 0 stolov.\n",
    "\n",
    "Skratka: pred funkcijo napišemo `@cache`, pri čemer je `cache` funkcija, ki jo je potrebno uvoziti iz `functools`.\n",
    "\n",
    "Tehnični detajl, ki se ga je potrebno zavedati: `cache` deluje tako, da shranjuje argumente in pripadajoče rezultate v slovar. (Očitno. Kam drugam bi jih lahko? Le tako lahko hitro preveri, ali je določene argumente že kdaj videl in kakšen je bil pripadajoči rezultat.) Ker pa morajo biti ključi slovarja nespremenljive reči, dekoratorja `cache` ne moramo uporabiti za funkcije, ki sprejemajo sezname, slovarje ali množice (ali kaj drugega nespremenljivega). V tem primeru spremenimo funkcijo tako, da namesto seznamov sprejema terke, namesto množic zamrznjene množice (`frozenset`), namesto slovarjev pa, tough luck, sezname parov. No, slednje se mi še ni zgodilo, tako da ne boli preveč."
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Tags",
  "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.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}