{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "material-stock",
   "metadata": {},
   "source": [
    "# Vaje 7: Rekurzija\n",
    "\n",
    "Na današnjih vajah bomo spoznali povezavo med zankami in rekurzijo. Naučili se\n",
    "bomo tudi nekaj tehnik programiranja z rekurzivnimi funkcijami.\n",
    "\n",
    "## Iz zanke v rekurzijo\n",
    "\n",
    "### Reference in zanke v Ocamlu\n",
    "\n",
    "Ko v OCamlu definiramo vrednost `x` z `let x = e₁ in e₂` je `x` *nespremenljiva*\n",
    "vrednost. Če želimo spremenljivo vrednost, moramo narediti *referenco*:\n",
    "\n",
    "* z `ref v` naredimo novo referenco z vrednostjo `v`\n",
    "* z `!r` dobimo trenutno vrednost reference `r`\n",
    "* z `r := v` nastavimo vrednost reference `r`.\n",
    "\n",
    "Primer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "adapted-clerk",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val r : int ref = {contents = 5}\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 5\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 15\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let r = ref 5 ;;\n",
    "!r ;;\n",
    "!r + 10 ;;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "functioning-asian",
   "metadata": {},
   "source": [
    "Ločiti je treba med referenco `r` in njeno vrednostjo `!r`:\n",
    "\n",
    "    # r + 10 ;;\n",
    "    Characters 0-1:\n",
    "      r + 10 ;;\n",
    "      ^\n",
    "    Error: This expression has type int ref\n",
    "           but an expression was expected of type int"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lonely-response",
   "metadata": {},
   "source": [
    "Poskusimo, kako se nastavi vrednost reference:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "historic-correspondence",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 8\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 18\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r := 8 ;;\n",
    "!r ;;\n",
    "!r + 10 ;;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ready-marriage",
   "metadata": {},
   "source": [
    "OCaml ima tudi zanki `while` in `for`. Prvo zapišemo\n",
    "\n",
    "    while ⟨pogoj⟩ do\n",
    "      ⋯\n",
    "    done\n",
    "\n",
    "in drugo\n",
    "\n",
    "    for i = ⟨spodnja-meja⟩ to ⟨zgornja-meja⟩ do\n",
    "      ⋯\n",
    "    done\n",
    "\n",
    "Mi bomo večinoma uprabljali `while`, nič pa ni narobe, če v svojih rešitvah\n",
    "uporabite `for`. Tu je program, ki sešteje prvih `42` lihih števil:\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "eligible-slovenia",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val vsota_lihih_42 : int = 1764\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let vsota_lihih_42 =\n",
    "    let v = ref 0 in\n",
    "    let i = ref 0 in\n",
    "    while !i < 42 do\n",
    "    v := !v + (2 * !i + 1) ;\n",
    "    i := !i + 1\n",
    "    done ;\n",
    "    !v"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "protected-network",
   "metadata": {},
   "source": [
    "Števec `i` in vsota `v` sta referenci, ker se njuni vrednosti spreminjata. To je\n",
    "običajno, kadar uporabljamo zanke."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "national-cancellation",
   "metadata": {},
   "source": [
    "### Naloga 1\n",
    "\n",
    "Sestavite funkcijo `vsota1 : int -> int`, ki sprejme `n` in vrne vsoto `1 + 2 +\n",
    "⋯ + n`. Uporabite reference in zanko `while`.\n",
    "\n",
    "#### Rešitev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "descending-hospital",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "forced-lemon",
   "metadata": {},
   "source": [
    "### Naloga 2\n",
    "\n",
    "Sestavite funkcijo `fibonacci1 : int -> int`, ki sprejme `n` in vrne `n`-to\n",
    "Fibonaccijevo število `F(n)`. Nauk: Fibonaccijevo zaporedje je definirano s\n",
    "predpisom:\n",
    "\n",
    "    F(0) = 0\n",
    "    F(1) = 1\n",
    "    F(n) = F(n-1) + F(n-2)\n",
    "\n",
    "Uporabite reference in zanko `while`.\n",
    "\n",
    "#### Rešitev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "extensive-discrimination",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "isolated-compression",
   "metadata": {},
   "source": [
    "## Rekurzivne funkcije\n",
    "\n",
    "Zanko `while` lahko sistematično pretvorimo v rekurzivno funkcijo. Še prej pa\n",
    "malce ponovimo rekurzivne funkcije.\n",
    "\n",
    "### Naloga 3\n",
    "\n",
    "Sestavite funkcijo `vsota2 : int -> int`, ki sprejme `n` in vrne vsoto `1 + 2 + ⋯ + n`. Funkcija naj bo rekurzivna in naj ne uporablja zank in referenc.\n",
    "\n",
    "#### Rešitev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "forty-syndication",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "armed-stockholm",
   "metadata": {},
   "source": [
    "### Naloga 4\n",
    "\n",
    "Sestavite funkcijo `fibonacci2 : int -> int`, ki sprejme `n` in vrne `n`-to\n",
    "Fibonaccijevo število `F(n)`. Funkcija naj bo rekurzivna in naj ne uporablja\n",
    "zank in referenc.\n",
    "\n",
    "#### Rešitev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "exceptional-brick",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "generous-trick",
   "metadata": {},
   "source": [
    "## Akumulatorji in repna rekurzija\n",
    "\n",
    "Pravimo, da je rekurzivni klic funkcije **repni klic** ali **klic na repu**\n",
    "(angl. _tail recursive_), če je rezultat rekurzivnega klica hkrati tudi rezultat\n",
    "funkcije. Povedano z drugimi besedami, funkcija se pokliče rekurzivno in nato takoj\n",
    "vrne rezultat rekurzivnega klica.\n",
    "\n",
    "Na primer, v rekurzivni funkciji\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "detailed-logistics",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val f : int -> int = <fun>\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec f = function\n",
    "| 0 -> 1\n",
    "| n ->\n",
    "    if n mod 2 = 0\n",
    "    then f (n / 2)\n",
    "    else 3 * f (n - 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "spare-plate",
   "metadata": {},
   "source": [
    "je prvi rekurzivni klic repni, ker se izvede `f (n / 2)` in nato nič drugega,\n",
    "drugi rekurzivni klic pa ni repni, ker je treba rezultat rekurzivnega klica `f\n",
    "(n - 1)` še množiti s `3`.\n",
    "\n",
    "Mnogi prevajalniki (vendar ne Java in Python) repne klice optimizirajo tako, da\n",
    "jih kar pretvorijo v zanko, kar je dosti bolj učinkovito. Pogosto lahko\n",
    "rekurzivno funkcijo, ki nima repnih klicev, predelamo v tako, ki ima repne\n",
    "klice. Pri tem uporabimo t.i. tehniko *akumulatorjev*, ki imajo v rekurzivni\n",
    "funkciji podobno vlogo kot pomožne spremenljivke v zanki.\n",
    "\n",
    "Poglejmo, kako bi pretvorili funkcijo `vsota_lihih1 n`, ki z uporabo zanke\n",
    "izračuna vsoto\n",
    "\n",
    "    1 + 3 + 5 + ⋯ + (2 n - 1)\n",
    "\n",
    "v repno rekurzivno funkcijo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "engaged-supplier",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val vsota_lihih1 : int -> int = <fun>\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let vsota_lihih1 n =\n",
    "    let v = ref 0 in\n",
    "    let i = ref 0 in\n",
    "    while !i < n do\n",
    "        v := !v + (2 * !i + 1) ;\n",
    "        i := !i + 1\n",
    "    done ;\n",
    "    !v"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "postal-equity",
   "metadata": {},
   "source": [
    "Recept je naslednji: ker zanka uporablja dve spremenljivki, namreč `v` in `i`,\n",
    "bo imela rekurzivna funkcija dva argumenta `v` in `i`. Namesto, da bi\n",
    "spreminjali vrednosti `v` in `i` (česar ne moremo, saj `v` in `i` ne bosta več\n",
    "referenci), bomo naredili repni rekuzivni klic s popravljenima vrednostma `v` in\n",
    "`i`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "attended-prince",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val vsota_lihih2 : int -> int = <fun>\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let vsota_lihih2 n =\n",
    "    let rec vsota v i =\n",
    "        if i < n\n",
    "        then vsota (v + (2 * i + 1)) (i + 1)\n",
    "        else v\n",
    "        in\n",
    "    vsota 0 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "transsexual-reset",
   "metadata": {},
   "source": [
    "Kot vidimo, funkcija `vsota_lihih2` ni rekurzvina, ampak vsebuje *pomožno*\n",
    "rekurzivno funkcijo `vsota`, ki igra vlogo zanke. Klic `vsota 0 0` nato izvede\n",
    "`vsota` z ustreznima začetnima vrednostma `v` in `i`.\n",
    "\n",
    "### Naloga 3\n",
    "\n",
    "Po zgornjem receptu predelajte funkcijo `vsota1` v funkcijo `vsota3`, ki\n",
    "uporablja akumulatorje in repno rekurzijo. Nato primerajte delovanje funkcij\n",
    "`vsota1`, `vsota2` in `vsota3`. Ali lahko vse tri izračunajo npr. vsoto prvih\n",
    "`1000000` števil?\n",
    "\n",
    "#### Rešitev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "foreign-hunger",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "(* let time f =\n",
    "    let t = Unix.gettimeofday () in\n",
    "    let res = f () in\n",
    "    Printf.printf \"Execution time: %f seconds\\n\"\n",
    "    (Unix.gettimeofday () -. t) ; flush stdout ;\n",
    "    res\n",
    ";;\n",
    "\n",
    "(* 1000000 -> 100000 *)\n",
    "let vsota1_runtime = time (fun () -> vsota1 100000) ;;\n",
    "let vsota2_runtime = time (fun () -> vsota2 100000) ;;\n",
    "let vsota3_runtime = time (fun () -> vsota3 100000) ;; *)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "allied-senator",
   "metadata": {},
   "source": [
    "### Naloga 4\n",
    "\n",
    "Po zgornjem receptu predelajte funkcijo `fibonacci1` v funkcijo `fibonacci3`, ki\n",
    "uporablja akumulatorje in repno rekurzijo.\n",
    "\n",
    "#### Rešitev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "atlantic-driver",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "unnecessary-taxation",
   "metadata": {},
   "source": [
    "## Splošna pretvorba zanke `while` v rekurzivno funkcijo\n",
    "\n",
    "Premislimo še, ali lahko zanko `while` v splošnem prevedemo v rekurzivno\n",
    "funkcijo z akumulatorjem in repnim klicom. Obravnavajmo zanko `while` oblike\n",
    "(zapisali smo jo v namišljenem ukaznem programskem jeziku):\n",
    "\n",
    "    s := s₀\n",
    "    while p(s) do\n",
    "      s := f(s)\n",
    "    done ;\n",
    "    return r(s)\n",
    "\n",
    "Tu smo z `s` označili skupno stanje vseh spremenljivk, ki nastopajo v zanki,\n",
    "`s₀` je začetno stanje, `p(s)` je pogoj (ki je odvisen od stanja `s`), zanka\n",
    "vsakič trenutno stanje `s` nastavi na novo stanje `f(s)`, na koncu pa vrne\n",
    "rezultat `r(s)` (ki je spet odvisen od `s`). Na primer, zanko, ki izračuna\n",
    "`n`-to Fibonaccijevo število bi zapisali takole:\n",
    "\n",
    "    (a,b,i) := (0,1,0)\n",
    "    while i < n do\n",
    "       (a,b,i) = (b,a+b,i+1)\n",
    "    done ;\n",
    "    return a\n",
    "\n",
    "Zgornjo zanko lahko predelamo v rekurzivno funkcijo `zanka`, ki spreme `s₀`,\n",
    "`p`, `f` in `r` ter izračuna to, kar bi sicer izračunala zanka `while`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "mighty-heart",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val zanka : 'a -> ('a -> bool) -> ('a -> 'a) -> ('a -> 'b) -> 'b = <fun>\n"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let zanka s0 p f r =\n",
    "    let rec loop s =\n",
    "        if p s then loop (f s) else r s\n",
    "    in loop s0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "statutory-douglas",
   "metadata": {},
   "source": [
    "Tip funkcije `zanka` je\n",
    "\n",
    "    α → (α → bool) → (α → α) → (α → β) → β\n",
    "\n",
    "kar pomeni, da ima začetno stanje `s₀` (poljuben) tip `α`, pogoj `p` je\n",
    "funkcija, ki slika stanje v `bool`, `f` je funkcija, ki stanje predela v novo\n",
    "stanje, in `r` je funkcija, ki stanje predela v rezultat (poljubnega) tipa `β`.\n",
    "\n",
    "### Naloga 5\n",
    "\n",
    "Sestavite funkcijo `vsota4`, ki izračuna vsoto števil `1 + 2 + ⋯ + n`, tako da\n",
    "uporabite funkcijo `zanka`. Torej, vaša rešitev mora biti oblike\n",
    "\n",
    "    let vsota4 n = zanka ⋯ ⋯ ⋯ ⋯\n",
    "\n",
    "kjer `⋯` nadomestite z ustreznimi vrednostmi `s₀`, `p`, `f` in `r`.\n",
    "\n",
    "#### Rešitev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "indirect-uncertainty",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "silent-japan",
   "metadata": {},
   "source": [
    "### Naloga 6\n",
    "\n",
    "Sestavite funkcijo `fibonacci4`, ki izračuna `n`-to Fibonaccijevo, tako da\n",
    "uporabite funkcijo `zanka`. Torej, vaša rešitev mora biti oblike\n",
    "\n",
    "    let fibonacci4 n = zanka ⋯ ⋯ ⋯ ⋯\n",
    "\n",
    "kjer `⋯` nadomestite z ustreznimi vrednostmi `s₀`, `p`, `f` in `r`.\n",
    "\n",
    "#### Rešitev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "european-period",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "accessory-nerve",
   "metadata": {},
   "source": [
    "### Naloga 7\n",
    "\n",
    "Sestavite rekurzivno funkcijo `forzanka`, ki izračuna to, kar izračuna spodnja koda v namišljenem ukaznem programskem jeziku:\n",
    "\n",
    "    s := s₀\n",
    "    for i = a to b do\n",
    "      s := f(i, s)\n",
    "    done ;\n",
    "    return r(s)\n",
    "\n",
    "Enako kot prej tukaj `s` označuje skupno stanje vseh spremenljivk, ki nastopajo v zanki,\n",
    "`s₀` pa začetno stanje. Zanka za vsak `i` med vključno `a` in `b` pokliče funkcijo `f`, ki glede `i` in trenutno stanje `s` izračuna novo stanje, na koncu pa vrne rezultat `r(s)`. Na primer, zanko `for`, ki izračuna vsoto prvih `n` naravnih števil, bi zapisali takole:\n",
    "\n",
    "    v := 0\n",
    "    for i = 1 to n do\n",
    "        v := v+i\n",
    "    done ;\n",
    "    return v\n",
    "\n",
    "Funkcija `forzanka` naj prejme začetno stanje `s₀`, spodnjo in zgornjo mejo `a` oziroma `b` ter funkciji `f` in `r`. Njen tip bo torej\n",
    "\n",
    "    α → int → int → (int → α → α) → (α → β) → β\n",
    "\n",
    "#### Rešitev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "interracial-croatia",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "going-difficulty",
   "metadata": {},
   "source": [
    "### Naloga 8\n",
    "\n",
    "Sestavite funkcijo `fibonacci5`, ki izračuna `n`-to Fibonaccijevo, tako da\n",
    "uporabite funkcijo `forzanka`. Torej, vaša rešitev mora biti oblike\n",
    "\n",
    "    let fibonacci5 n = forzanka ⋯ ⋯ ⋯ ⋯ ⋯\n",
    "\n",
    "kjer `⋯` nadomestite z ustreznimi vrednostmi `s₀`, `a`, `b`, `f` in `r`.\n",
    "\n",
    "#### Rešitev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "respective-phone",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "spatial-ultimate",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "OCaml default",
   "language": "OCaml",
   "name": "ocaml-jupyter"
  },
  "language_info": {
   "codemirror_mode": "text/x-ocaml",
   "file_extension": ".ml",
   "mimetype": "text/x-ocaml",
   "name": "OCaml",
   "nbconverter_exporter": null,
   "pygments_lexer": "OCaml",
   "version": "4.08.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}