Rekurzija

Na današnjih vajah bomo spoznali povezavo med zankami in rekurzijo. Naučili se bomo tudi nekaj tehnik programiranja z rekurzivnimi funkcijami.

Iz zanke v rekurzijo

Reference in zanke v Ocamlu

Ko v OCamlu definiramo vrednost x z let x = e₁ in e₂ je x nespremenljiva vrednost. Če želimo spremenljivo vrednost, moramo narediti referenco:

• z ref v naredimo novo referenco z vrednostjo v
• z !r ali r.contents dobimo trenutno vrednost reference r
• z r := v nastavimo vrednost reference r.

Primer:

# let r = ref 5 ;;
val r : int ref = {contents = 5}
# !r ;;
- : int = 5
# !r + 10 ;;
- : int = 15

Ločiti je treba med referenco r in njeno vrednostjo !r:

# r + 10 ;;
Characters 0-1:
  r + 10 ;;
  ^
Error: This expression has type int ref
       but an expression was expected of type int

Poskusimo, kako se nastavi vrednost reference:

# r := 8 ;;
- : unit = ()
# !r ;;
- : int = 8
# !r + 10 ;;
- : int = 18

OCaml ima tudi zanki while in for. Prvo zapišemo

while ⟨pogoj⟩ do
  ⋯
done

in drugo

for i = ⟨spodnja-meja⟩ to ⟨zgornja-meja⟩ do
  ⋯
done

Mi bomo večinoma uprabljali while, nič pa ni narobe, če v svojih rešitvah uporabite for. Tu je program ki sešteje prvih 42 lihih števil:

let vsota_lihih_42 =
  let v = ref 0 in
  let i = ref 0 in
  while !i < 42 do
    v := !v + (2 * !i + 1) ;
    i := !i + 1
  done ;
  !v

Števec i in vsota v sta referenci, ker se njuni vrednosti spreminjata. To je običajno, kadar uporabljamo zanke.

Naloga 1

Sestavite funkcijo vsota1 : int -> int, ki sprejme n in vrne vsoto 1 + 2 + ⋯ + n. Uporabite reference in zanko while.

Naloga 2

Sestavite funkcijo fibonacci1 : int -> int, ki sprejme n in vrne n-to Fibonaccijevo število F(n). Nauk: Fibonaccijevo zaporedje je definirano s predpisom:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

Uporabite reference in zanko while.

Rekurzivne funkcije

Zanko while lahko sistematično pretvorimo v rekurzivno funkcijo. Še prej pa malce ponovimo rekurzivne funkcije.

Naloga 3

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.

Naloga 4

Sestavite funkcijo fibonacci2 : int -> int, ki sprejme n in vrne n-to Fibonaccijevo število F(n). Funkcija naj bo rekurzivna in naj ne uporablja zank in referenc.

Akumulatorji in repna rekurzija

Pravimo, da je rekurzivni klic funkcije repni klic ali klic na repu (angl. tail recursive), če je rezultat rekurzivnega klica hkrati tudi rezultat funkcije. Povedano z drugimi besedami, funkcija se pokliče rekurzivno in nato takoj vrne rezultat rekurzivnega klica.

Na primer, v rekurzivni funkciji

let rec f = function
  | 0 -> 1
  | n ->
     if n mod 2 = 0 then
       f (n / 2)
     else
       3 * f (n - 1)

je prvi rekurzivni klic repni, ker se izvede f (n / 2) in nato nič drugega, drugi rekurzivni klic pa ni repni, ker je treba rezultat rekurzivnega klica f (n - 1) še množiti s 3.

Mnogi prevajalniki (vendar ne Java in Python) repne klice optimizirajo tako, da jih kar pretvorijo v zanko, kar je dosti bolj učinkovito. Pogosto lahko rekurzivno funkcijo, ki nima repnih klicev, predelamo v tako, ki ima repne klice. Pri tem uporabimo t.i. tehniko akumulatorjev, ki imajo v rekurzivni funkciji podobno vlogo kot pomožne spremenljivke v zanki.

Poglejmo, kako bi pretvorili funkcijo vsota_lihih1 n, ki z uporabo zanke izračuna vsoto

1 + 3 + 5 + ⋯ + (2 n - 1)

v repno rekurzivno funkcijo:

let vsota_lihih1 n =
  let v = ref 0 in
  let i = ref 0 in
  while !i < n do
    v := !v + (2 * !i + 1) ;
    i := !i + 1
  done ;
  !v

Recept je naslednji: ker zanka uporablja dve spremenljivki, namreč v in i, bo imela rekurzivna funkcija dva argumenta v in i. Namesto, da bi spreminjali vrednosti v in i (česar ne moremo, saj v in i ne bosta več referenci), bomo naredili repni rekuzivni klic s popravljenima vrednostma v in i:

let vsota_lihih2 n =
  let rec vsota v i =
    if i < n then
      vsota (v + (2 * i + 1)) (i + 1)
    else
      v
  in
  vsota 0 0

Kot vidimo, funkcija vsota_lihih2 ni rekurzvina, ampak vsebuje pomožno rekurzivno funkcijo vsota, ki igra vlogo zanke. Klic vsota 0 0 nato izvede vsota z ustreznima začetnima vrednostma v in i.

Naloga 5

Po zgornjem receptu predelajte funkcijo vsota1 v funkcijo vsota3, ki uporablja akumulatorje in repno rekurzijo. Nato primerajte delovanje funkcij vsota1, vsota2 in vsota3. Ali lahko vse tri izračunajo npr. vsoto prvih 1000000 števil?

Naloga 6

Po zgornjem receptu predelajte funkcijo fibonacci1 v funkcijo fibonacci3, ki uporablja akumulatorje in repno rekurzijo.

Splošna pretvorba zanke while v rekurzivno funkcijo

Premislimo še, ali lahko zanko while v splošnem prevedemo v rekurzivno funkcijo z akumulatorjem in repnim klicom. Obravnavajmo zanko while oblike (zapisali smo jo v namišljenem ukaznem programskem jeziku):

s := s₀
while p(s) do
  s := f(s)
done ;
return r(s)

Tu smo z s označili skupno stanje vseh spremenljivk, ki nastopajo v zanki, s₀ je začetno stanje, p(s) je pogoj (ki je odvisen od stanja s), zanka vsakič trenutno stanje s nastavi na novo stanje f(s), na koncu pa vrne rezultat r(s) (ki je spet odvisen od s). Na primer, zanko, ki izračuna n-to Fibonaccijevo število bi zapisali takole:

(a,b,i) := (0,1,0)
while i < n do
   (a,b,i) = (b,a+b,i+1)
done ;
return a

Zgornjo zanko lahko predelamo v rekurzivno funkcijo zanka, ki spreme s₀, p, f in r ter izračuna to, kar bi sicer izračunala zanka while:

let zanka s0 p f r =
  let rec loop s =
    if p s then loop (f s) else r s
  in
  loop s0

Tip funkcije zanka je

α → (α → bool) → (α → α) → (α → β) → β

kar pomeni, da ima začetno stanje s₀ (poljuben) tip α, pogoj p je funkcija, ki slika stanje v bool, f je funkcija, ki stanje predela v novo stanje, in r je funkcija, ki stanje predela v rezultat (poljubnega) tipa β.

Naloga 7

Sestavite funkcijo vsota4, ki izračuna vsoto števil 1 + 2 + ⋯ + n, tako da uporabite funkcijo zanka. Torej, vaša rešitev mora biti oblike

let vsota4 n = zanka ⋯ ⋯ ⋯ ⋯

kjer ⋯ nadomestite z ustreznimi vrednostmi s₀, p, f in r.

Naloga 8

Sestavite funkcijo fibonacci4, ki izračuna n-to Fibonaccijevo, tako da uporabite funkcijo zanka. Torej, vaša rešitev mora biti oblike

let fibonacci4 n = zanka ⋯ ⋯ ⋯ ⋯

kjer ⋯ nadomestite z ustreznimi vrednostmi s₀, p, f in r.

Naloga 9

Sestavite rekurzivno funkcijo forzanka, ki izračuna to, kar izračuna spodnja koda v namišljenem ukaznem programskem jeziku. Pri tem ne uporabljajte zank ali referenc.

s := s₀
for i = a to b do
  s := f(i, s)
done ;
return r(s)

Enako kot prej tukaj s označuje skupno stanje vseh spremenljivk, ki nastopajo v zanki, 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:

v := 0
for i = 1 to n do
    v := v+i
done ;
return v

Funkcija forzanka naj prejme začetno stanje s₀, spodnjo in zgornjo mejo a oziroma b ter funkciji f in r. Njen tip bo torej

α → int → int → (int → α → α) → (α → β) → β

Naloga 10

Sestavite funkcijo fibonacci5, ki izračuna n-to Fibonaccijevo, tako da uporabite funkcijo forzanka. Torej, vaša rešitev mora biti oblike

let fibonacci5 n = forzanka ⋯ ⋯ ⋯ ⋯ ⋯

kjer ⋯ nadomestite z ustreznimi vrednostmi s₀, a, b, f in r.