{
"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
}