Rekurzija

Izkaže se, da lahko s tem, kar smo spoznali v prvem poglavju, napišemo čisto vse izračunljive funkcije na celih številih: ugotovimo lahko, katera števila so praštevila, katera so si prijateljska, katera so popolna, … To nam omogoča rekurzija, s katero dosežemo, da računalnik programa ne izvaja strogo od zgoraj navzdol, temveč se po potrebi tudi vrne in kakšen korak izvede večkrat. Da bomo imeli bolj pestre primere, si pred rekurzijo oglejmo še nize.

Nizi

V programih seveda ne delamo le s števili, temveč tudi z drugimi podatki, na primer besedili. V ta namen Python podpira nize, ki so strnjena zaporedja znakov.

Operacije na nizih

Nize običajno pišemo v enojnih narekovajih, na primer 'to je primer niza'. Nize lahko stikamo z operacijo + in množimo s celimi števili:

>>> 'Dober' + 'dan'
'Doberdan'
>>> 10 * 'ha'
'hahahahahahahahahaha'
>>> 'tro' + 4 * 'lo'
'trololololo'

Dolžino niza dobimo s funkcijo len:

>>> len('lokomotiva')
10
>>> len('')
0

Nize lahko med seboj tudi primerjamo. Pri tem Python nize ureja leksikografsko, torej tako, kot bi bili urejeni v leksikonu ali kazalu: najprej primerja prvi črki, če sta ti dve enaki, pogleda drugi dve, in tako naprej. Pri tem velike črke pridejo na vrsto pred malimi, na šumnike pa se brez posebnih knjižnic Python ne spozna.

>>> 'beseda' == 'konj'
False
>>> 'abak' <= 'abeceda'
True
>>> 'Z' <= 'a'
True
>>> 'd' >= 'č'
False

Na nizih imamo na voljo tudi predikat in, s katerim ugotovimo, ali se nek niz pojavlja kot podniz v drugem nizu. Na voljo je tudi not in, s katerim bolj berljivo zapišemo ravno nasprotno stvar:

>>> 'gram' in 'Uvod v programiranje'
True
>>> 'liter' in 'Uvod v programiranje'
False
>>> not ('liter' in 'Uvod v programiranje')
True
>>> 'liter' not in 'Uvod v programiranje'
True

Zapis nizov

Nize lahko pišemo tudi z dvojnimi narekovaji, ki jih ponavadi uporabimo takrat, kadar v nizu želimo uporabiti enojni narekovaj: "Tole je kr'neki!". V tem primeru niza ne moremo pisati med enojnimi narekovaji, saj bi Python po narekovaju za kr mislil, da je konec niza.

Včasih želimo uporabiti obe vrsti narekovajev. V tem primeru si pomagamo z ubežnimi znaki. To so znaki, ki jih na običajni način ne moremo zapisati, zato uporabimo poseben zapis, ki se začne z znakom \. Tedaj lahko pišemo '"Tole je kr\'neki," je rekla.' ali pa "\"Tole je kr'neki,\" je rekla.". Ubežne znake brez težav lahko pišemo tudi tedaj, kadar ni treba '\"Grem v rudnik,\" je rekla.'. Z ubežnimi znaki lahko zapišemo tudi znak za novo vrstico \n, za tabulator \t in seveda tudi za poševnico \\, saj je ne moremo pisati le kot \, ker bi Python to razumel kot začetek ubežnega znaka.

Nize lahko pišemo tudi med tri enojne (''') ali tri dvojne (""") narekovaje. V tem primeru za en sam narekovaj ne potrebujemo ubežnega znaka. Take nize lahko pišemo tudi čez več vrstic.

Indeksiranje

Do posameznega znaka v nizu pridemo z indeksi. Z izrazom niz[i] dostopamo do i-tega znaka v danem nizu:

>>> 'rekurzija'[3]
'u'
>>> 'rekurzija'[0]
'r'
>>> 'rekurzija'[-1]
'a'

Indeksi se začnejo šteti z 0. Če uporabimo negativna števila, lahko štejemo tudi od zadaj, vendar tam začnemo šteti z -1 (saj je -0 = 0).

 0   1   2   3   4   5   6   7   8
 R   E   K   U   R   Z   I   J   A
-9  -8  -7  -6  -5  -4  -3  -2  -1

Rezine

Na podoben način lahko dostopamo tudi do podnizov. Če napišemo niz[i:j] bomo dobili niz, ki mu pravimo rezina in sega od vključno i-tega do vključno j - 1-tega znaka. Če kakšno od meja izpustimo, bomo vzeli vse znake od začetka oziroma do konca.

>>> 'rekurzija'[2]
'k'
>>> 'rekurzija'[6]
'i'
>>> 'rekurzija'[2:6]
'kurz'
>>> 'rekurzija'[:6]
'rekurz'
>>> 'rekurzija'[2:]
'kurzija'

Pišemo lahko tudi niz[i:j:k], s čimer vzamemo le vsak k-ti znak:

>>> 'rekurzija'[1:8]
'ekurzij'
>>> 'rekurzija'[1:8:1]
'ekurzij'
>>> 'rekurzija'[1:8:2]
'euzj'
>>> 'rekurzija'[1:8:3]
'erj'
>>> 'rekurzija'[::-1]
'ajizruker'

Stavek print

Rekurzivni klici

Videli smo, da lahko iz funkcij kličemo tudi druge funkcije. Na primer, v funkciji povrsina_tetraedra smo poklicali funkcijo ploscina_trikotnika, v tej pa vgrajeno funkcijo math.sqrt. V resnici pa lahko v funkciji pokličemo tudi funkcijo samo. Takemu klicu pravimo rekurzivni klic. Poglejmo, kako bi izračunali \(n! = n \cdot (n - 1) \dots 3 \cdot 2 \cdot 1\). Kot vidimo velja \(n! = n \cdot (n - 1)!\), zato bomo \(n!\) izračunali tako, da bomo \(n\) pomnožili z \((n - 1)!\). Toda od kod bomo dobili tega? Preprosto, \(n - 1\) bomo pomnožili z \((n - 2)!\). Od kod pa tega? Ja iz \((n - 3)!\). In tako naprej vse do \(2!\), ki ga bomo dobili iz \(1!\), tega pa iz \(0!\), ki je po definiciji enak \(1\).

Torej lahko funkcijo, ki računa fakulteto, napišemo tako, da najprej pogleda svoj argument n. Če je enak 1, vrne 1, sicer pa izračunamo tako, da n pomnožimo z rezultatom klica fakulteta(n - 1):

def fakulteta(n):
    if n <= 1:
        return 1
    else:
        return n * fakulteta(n - 1)
>>> fakulteta(1)
1
>>> fakulteta(5)
120
>>> fakulteta(10)
3628800

Še en primer rekurzivne definicije so Fibonaccijeva števila. Velja \(F_0 = 0\), \(F_1 = 1\), za vse \(n \ge 2\) pa velja in \(F_{n} = F_{n - 1} + F_{n - 2}\). Funkcijo tedaj napišemo podobno na podoben način kot zgornjo: če je n enak 0, vrnemo 0, sicer pogledamo, ali je enak 1. V tem primeru vrnemo 1. Če pa tudi 1 ni enak, mora biti večji ali enak 2, zato se pokličemo rekurzivno.

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
>>> fibonacci(3)
2
>>> fibonacci(4)
3
>>> fibonacci(5)
5
>>> fibonacci(20)
6765

Kaj se zgodi, če poskušate izračunati fibonacci(35)? Po nekaj časa res dobite pravilen odgovor 9227465, vendar to kaže, da nekaj ni v redu. Težava je, da se pri fibonacci(35) funkcija pokliče dvakrat: enkrat na 34 in enkrat na 33. Tudi vsak od teh dveh klicov povzroči dva nadaljnja klica in tako naprej, vse dokler ne pridemo do 0 ali 1. Bolje bi bilo, če bi jo zastavili malo drugače. Poleg Fibonaccijevega zaporedja, ki se začne s številoma 0 in 1, obstaja tudi splošno Fibonaccijevo zaporedje, ki se začne s poljubnima členoma \(a\) in \(b\):

\[a, b, a + b, b + (a + b) = a + 2 b, (a + b) + (a + 2 b) = 2 a + 3 b, \ldots\]

Vidimo, da je \(n\). člen tega zaporedja ravno \(n - 1\). člen zaporedja, ki se začne s členoma \(b\) in \(a + b\). Tedaj lahko definiramo:

def splosni_fibonacci(n, a, b):
    if n == 0:
        return a
    elif n == 1:
        return b
    else:
        return splosni_fibonacci(n - 1, b, a + b)

Kot lahko sami preizkusimo, ta funkcija deluje veliko hitreje od prejšnje:

>>> splosni_fibonacci(35, 0, 1)
9227465
>>> splosni_fibonacci(25, 1, -1)
-28657
>>> splosni_fibonacci(25, 0, 2)
150050
>>> splosni_fibonacci(500, 0, 1)
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125

Pomembno ni torej samo to, da naš program pravilno izračuna iskani rezultat, temveč tudi to, kako učinkovito ga izračuna.

Stavek assert

Tudi funkcija splosni_fibonacci še ni popolna. Kaj se zgodi, če pokličemo splosni_fibonacci(-2, 0, 1)? Ker -2 ni enako ne 0 ne 1, bomo izvedli tretjo vejo pogojnega stavka in izračunali splosni_fibonacci(-3,  0, 1), iz tega pa podobno splosni_fibonacci(-4,  0, 1) in tako naprej, vse do trenutka, ko se bo Python pritožil:

>>> splosni_fibonacci(-2, 0, 1)
Traceback (most recent call last):
  ...
  File "...", line 8, in splosni_fibonacci
  File "...", line 8, in splosni_fibonacci
  File "...", line 8, in splosni_fibonacci
  File "...", line 8, in splosni_fibonacci
  File "...", line 8, in splosni_fibonacci
  File "...", line 8, in splosni_fibonacci
  File "...", line 3, in splosni_fibonacci
RecursionError: maximum recursion depth exceeded in comparison

Pravi nam, da je naša rekurzija šla pregloboko. O tem bomo še bolj natančno govorili, zaenkrat pa naj nam tako opozorilo pove, da smo program napisali tako, da se ne bo ustavil. Da podobne situacije preprečimo, lahko uporabimo stavek assert, v katerem napišemo pogoj, ki mu mora program zadoščati. Če mu ne, Python javi napako.

def splosni_fibonacci(n, a, b):
    '''Vrne n-ti člen Fibonaccijevega zaporedja, ki se začne z a in b.'''
    assert n >= 0
    if n == 0:
        return a
    elif n == 1:
        return b
    else:
        return splosni_fibonacci(n - 1, b, a + b)
>>> splosni_fibonacci(-2, 0, 1)
Traceback (most recent call last):
  ...
AssertionError

Še vedno dobimo napako, vendar je ta bolj obvladljiva, pa še takoj se pojavi. Stavke assert uporabljamo, kadar v nadaljevanju programa pričakujemo, da je nekim pogojem zadoščeno. Namesto assert pogoj bi seveda lahko pisali tudi nekaj v stilu:

if not pogoj:
    # ustavi program
    # javi napako

ampak ker je to pogosto koristno, so v ta namen uvedli assert.