Zanke

Rekurzivni klici nam omogočajo, da se pri izvajanju poljubno mnogokrat vrnemo na poljubne konce programa. V veliki večini primerov pa nam je dovolj že to, da ponovimo določen del programa. Temu so namenjene zanke.

Zanka while

Z zanko while določene ukaze izvajamo toliko časa, dokler velja dani pogoj.

while pogoj:
    # stavki,
    # ki naj se izvajajo
    # dokler velja pogoj

Na primer, program

n = 12
while n < 1000:
    n = n * 2
    print(n)

bo n nastavil na 12, nato pa ga toliko časa podvojeval, dokler njegova vrednost ne bo dosegla 1000. Program bo tako izpisal:

24
48
96
192
384
768
1536

V programih bomo pogostokrat novo vrednost spremenljivke izračunali tako, da bomo spremenili staro (zato tudi govorimo o _spremenljivkah_). Na primer, ko bomo šteli vsa praštevila med 1 in 1000000, bomo imeli spremenljivko, ki bo imela na začetku vrednost 0, nato pa jo bomo ob vsakem praštevilu povečali za 1. V ta namen lahko namesto n = n * 2 pišemo kar operator n *= 2, saj je *= operacija, ki spremenljivko na levi pomnoži z vrednostjo na desni. Tudi za ostale operacije obstajajo podobne bližnjice, na primer -=, *=, //= in tako naprej.

>>> x = 3
>>> x += 2
>>> x *= 4
>>> x
20

Za primer izračunajmo stopnjo največje potence števila 2, ki še deli število 1580160. To storimo tako, da število zaporedoma celoštevilsko delimo z 2 in ob vsakem deljenju števec stopnje povečamo za 1. Ukaze ponavljamo toliko časa, dokler je ostanek pri deljenju z 2 enak 0:

n = 1580160
stopnja = 0
while n % 2 == 0:
    n //= 2
    stopnja += 1

Ko se izvajanje zaključi, lahko preverimo, da velja

>>> stopnja
7

Zgornji program lahko pretvorimo v splošnejšo funkcijo:

def stopnja_najvecje_potence(n, k):
    '''Vrne stopnjo največje potence števila k, ki še deli n.'''
    stopnja = 0
    while n % k == 0:
        n //= k
        stopnja += 1
    return stopnja
>>> stopnja_najvecje_potence(81, 3)
4
>>> stopnja_najvecje_potence(1580160, 2)
7

Isto funkcijo bi lahko napisali tudi z rekurzijo:

def stopnja_najvecje_potence_rek(n, k):
    '''Vrne stopnjo največje potence števila k, ki še deli n.'''
    if n % k == 0:
        return 1 + stopnja_najvecje_potence_rek(n // k, k)
    else:
        return 0
>>> stopnja_najvecje_potence_rek(1580160, 2)
7
>>> stopnja_najvecje_potence_rek(81, 3)
4

V praksi pa za tiste programe, pri katerih neko stvar ponavljamo toliko časa, dokler velja določen pogoj, raje uporabimo zanko while, saj je učinkovitejša (vsaj v Pythonu, v drugih jezikih je rekurzija ravno tako učinkovita). Tako bi z zanko while lahko napisali tudi Evklidov algoritem:

def gcd(m, n):
    '''Vrne največji skupni delitelj števil m in n.'''
    while n != 0:
        m, n = n, m % n
    return m

Kot smo videli, se Python pritoži, če gremo pri rekurziji pregloboko. Običajno se to zgodi takrat, kadar smo rekurzijo napisali tako, da se ne ustavi. Vendar računalnik tega ne more vedeti, zato se Python ustavi takrat, ko naredimo približno 1000 rekurzivnih klicev:

>>> stopnja_najvecje_potence_rek(2 ** 985, 2)
985
>>> stopnja_najvecje_potence_rek(2 ** 986, 2)
Traceback (most recent call last):
  ...
  File "...", line 4, in stopnja_najvecje_potence_rek
  File "...", line 4, in stopnja_najvecje_potence_rek
  File "...", line 4, in stopnja_najvecje_potence_rek
  File "...", line 4, in stopnja_najvecje_potence_rek
  File "...", line 4, in stopnja_najvecje_potence_rek
  File "...", line 3, in stopnja_najvecje_potence_rek
RecursionError: maximum recursion depth exceeded in comparison

Pri zankah teh težav ni:

>>> stopnja_najvecje_potence(2 ** 985, 2)
985
>>> stopnja_najvecje_potence(2 ** 986, 2)
986
>>> stopnja_najvecje_potence(2 ** 10000, 2)
10000

Seveda tudi pri zanki while obstaja nevarnost, da se njeno izvajanje nikoli ne zaključi. Na primer, če bi poklicali

>>> stopnja_najvecje_potence(12345, 1)

bi bil ostanek pri deljenju z 1 v pogoju vedno enak 0, zato bi zanka tekla v neskončnost. Ko se naveličamo čakanja, lahko pritisnemo Ctrl-C in izvajanje prekinemo.

Bisekcija

Izračun korena

Poglejmo si enostaven algoritem, s katerim lahko izračunamo kvadratni koren pozitivnega števila. Recimo, da že vemo, da se koren števila \(n\) nahaja na intervalu \([a, b]\) (npr. vemo, da se zagotovo nahaja na intervalu \([0, n]\)). Naj bo \(c = (a + b) / 2\) sredina intervala. Tedaj ločimo tri primere:

  • Če imamo srečo, je \(c^2 = n\), zato smo našli koren in postopek lahko končamo.
  • Če je \(c^2 > n\), je tudi \(c > \sqrt{n}\), zato lahko na podoben način nadaljujemo z iskanjem korena na intervalu \([a, c]\).
  • V nasprotnem primeru pa mora biti \(c^2 < n\) in \(c < \sqrt{n}\), zato lahko z iskanjem nadaljujemo na intervalu \([c, b]\).

Ker interval vedno razdelimo na pol, postopku pravimo bisekcija. Ker lahko realna števila poljubno delimo, se zgornji postopek ne bo nikoli ustavil (razen, če imamo srečo in naletimo točno na koren). Toda ker nas zanima le približek korena, lahko postopek ustavimo takrat, ko se krajišči intervala razlikujeta za dovolj majhno vrednost \(\varepsilon\). Načeloma v algoritmu prvo možnost (ko je \(c^2 = n\)) kar izpustimo, saj je preveč redka, pa tudi brez nje algoritem najde pravo rešitev.

V Pythonu bi algoritem zapisali kot:

def kvadratni_koren(n, eps):
    '''Z metodo bisekcije poišče koren števila n.'''
    a, b = 0, n
    while b - a > eps:
        c = (a + b) / 2
        if c * c > n:
            b = c
        else:
            a = c
    return c
>>> kvadratni_koren(10, 1e-5)
3.1622791290283203
>>> kvadratni_koren(10, 1e-10)
3.1622776602307567
>>> kvadratni_koren(10, 1e-15)
3.162277660168379

Neobvezni argumenti

Včasih imamo za nekatere argumente funkcij v mislih že prav določeno vrednost. Na primer, za izračun logaritma potrebujemo dve števili: osnovo in argument (tudi logaritmand). Toda velikokrat za osnovo vzamemo \(10\), zato namesto \(\log_{10} x\) pišemo kar \(\log x\). Tudi pri Pythonu je podobno. Če se nam ob klicu funkcije ne ljubi navajati vrednosti vseh argumentov, lahko za nekatere od njih v prvi vrstici definicije navedemo privzeto vrednost. Na primer, pri funkciji kvadratni_koren ne pričakujemo, da bo uporabnik vedno znova vnašal natančnost, na katero želi izračunati koren. Če želimo, da ima eps privzeto vrednost 1e-15, lahko napišemo:

def kvadratni_koren(n, eps=1e-15):
    '''Z metodo bisekcije poišče koren števila n.'''
    a, b = 0, n
    while b - a > eps:
        c = (a + b) / 2
        if c * c > n:
            b = c
        else:
            a = c
    return c

Tedaj se bo vedno uporabila privzeta vrednost za tiste argumente, ki jih ne podamo izrecno.

>>> kvadratni_koren(10, eps=1e-5)
3.1622791290283203
>>> kvadratni_koren(10, eps=1e-15)
3.162277660168379
>>> kvadratni_koren(10)
3.162277660168379

Klic deluje tudi, če neobveznih argumentov ne poimenujemo, vendar lahko to vodi do zmede, če je argumentov več, zato se takih klicev izogibamo.

>>> kvadratni_koren(10, 1e-15)
3.162277660168379

Iskanje ničel

Na podoben način lahko približno izračunamo ničlo zvezne realne funkcije \(f\) na intervalu \([a, b]\), če vemo, da sta vrednosti \(f(a)\) in \(f(b)\) različno predznačeni. Če je \(c = (a + b) / 2\) zopet sredina intervala, ločimo tri primere:

  • Če imamo srečo, je \(f(c) = 0\), zato smo našli ničlo in postopek lahko končamo. Sicer je \(f(c)\) neničelno število, zatorej ima nek predznak.
  • Če je predznak \(f(c)\) različen od predznaka \(f(a)\) lahko na podoben način nadaljujemo z iskanjem ničle na intervalu \([a, c]\).
  • V nasprotnem primeru pa mora biti predznak \(f(c)\) različen od predznaka \(f(b)\) (ker imata \(f(a)\) in \(f(b)\) različen predznak), zato lahko z iskanjem nadaljujemo na intervalu \([c, b]\).

Podobno kot prej bi algoritem zapisali kot:

def bisekcija(f, a, b, eps):
    '''Z metodo bisekcije izračuna ničlo f na intervalu [a, b].'''
    while b - a > eps:
        c = (a + b) / 2
        if f(a) * f(c) < 0:
            b = c
        else:
            a = c
    return c
>>> import math
>>> bisekcija(math.sin, 2, 4, 0.01)
3.1484375
>>> bisekcija(math.sin, 2, 4, 0.00001)
3.1415939331054688
>>> bisekcija(math.sin, 2, 4, 10 ** -10)
3.141592653642874
>>> bisekcija(math.sin, 2, 4, 1e-10)
3.141592653642874

Funkcije višjega reda

Zgoraj lahko opazimo, da nam Python dopušča, da za argumente funkcij ne podajamo le števil, temveč tudi druge funkcije. Pravimo, da podpira funkcije višjega reda. Če želimo, lahko za argumente podamo tudi funkcije, ki smo jih definirali sami:

def moj_f(x):
    return x ** 2 - 2
>>> bisekcija(moj_f, 1, 2, 0.000001)
1.4142141342163086

Če se nam neke funkcije, ki bi jo uporabili samo v enem primeru (kot je ta zgoraj), ne da poimenovati, lahko uporabimo anonimne oziroma lambda funkcije, v katerih za telo napišemo enostaven izraz. Zgornji primer bi z njimi pisali kot:

>>> bisekcija(lambda x: x ** 2 - 2, 1, 2, 0.000001)
1.4142141342163086

Funkcij z zapletenejšim telesom in tistih, v katerih uporabljemo več stavkov, ne pišemo z lambdami. Tako ali tako je bolje, da zapletenejšim funkcijam damo ime, da se vidi, kaj počnejo.

Zanka for

Zanko while torej uporabimo takrat, kadar želimo ukaze ponavljati, dokler velja nek pogoj. Včasih pa že vnaprej vemo, kolikokrat bomo te ukaze ponovili. Na primer, funkcijo za izračun fakultete bi lahko pisali kot:

def fakulteta(n):
    '''Vrne fakulteto naravnega števila n.'''
    produkt = 1
    i = 1
    while i <= n:
        produkt *= i
        i += 1
    return produkt

vendar vemo, da se bo zanka izvedla natanko enkrat za vsako število od 1 do \(n\). Poleg tega se nam hitro zgodi, da vrstico i += 1 po nesreči pozabimo ali napišemo kot i + 1 ali kot i = 1, zaradi česar se zanka izvaja v neskončnost. Za primere, ko vemo, kolikokrat izvedemo določeno kodo, raje uporabimo zanko for.

for spremenljivka in podane_vrednosti:
    # stavki, ki se izvedejo
    # po enkrat za vsako izmed
    # podanih vrednost spremenljivke

Zanka for na razponih

Na primer, fakulteto števila 10 bi lahko izračunali kot:

fakulteta10 = 1
for i in range(1, 11):
    fakulteta10 *= i
>>> fakulteta10
3628800

V zanki for smo uporabili funkcijo range, ki vrne vsa cela števila v razponu od vključno prvega do tistega pred drugim (tako kot pri rezinah). V naši zanki for se spremenljivka i torej sprehodi po vseh vrednostih od 1 do 10. Koda se obnaša tako, kot če bi pisali:

fakulteta10 = 1
i = 1
fakulteta10 *= i
i = 2
fakulteta10 *= i
i = 3
fakulteta10 *= i
i = 4
fakulteta10 *= i
i = 5
fakulteta10 *= i
i = 6
fakulteta10 *= i
i = 7
fakulteta10 *= i
i = 8
fakulteta10 *= i
i = 9
fakulteta10 *= i
i = 10
fakulteta10 *= i

Funkcijo fakulteta pa bi napisali kot:

def fakulteta(n):
    '''Vrne fakulteto naravnega števila n.'''
    produkt = 1
    for i in range(1, n + 1):
        produkt *= i
    return produkt

Zanka for na nizih

Po vseh znakih danega niza se lahko sprehodimo z zanko for:

def je_samoglasnik(crka):
    return crka in 'aeiouAEIOU'

def stevilo_samoglasnikov(niz):
    '''Vrne število samoglasnikov v danem nizu.'''
    stevilo = 0
    for znak in niz:
        if je_samoglasnik(znak):
            stevilo += 1
    return stevilo

def brez_samoglasnikov(niz):
    '''Vrne niz enak danemu, le da smo iz njega izpustili vse samoglasnike.'''
    niz_brez_samoglasnikov = ''
    for znak in niz:
        if not je_samoglasnik(znak):
            niz_brez_samoglasnikov += znak
    return niz_brez_samoglasnikov
>>> stevilo_samoglasnikov('Uvod v programiranje')
7
>>> brez_samoglasnikov('Uvod v programiranje')
'vd v prgrmrnj'

Kot vidimo zgoraj, lahko vejo else tudi izpustimo (tako v običajnem kot v razširjenem pogojnem stavku). V tem primeru se ob neizpolnjevanju pogoja ne zgodi nič.

Stavki break, continue in pass

V zankah lahko uporabimo tudi posebne ukaze, ki spreminjajo običajen potek programa. Stavek break prekine trenutno zanko. Na primer:

for n in range(1, 5):
    print(n)
    if n == 2 or n == 3:
        break
    print('x')

izmenično izpisuje števila od 1 do 4 ter znak x. V trenutku, ko pride do števila 2, ki zadošča pogoju n == 2 or n == 3, izvajanje zanke v celoti prekine, zato izpiše le

1
x
2

Primer je napisan za zanko for, vendar enako deluje tudi za zanko while.

Stavek continue zanke ne ustavi, temveč le preskoči preostanek trenutnega obhoda zanke in gre nazaj na začetek z naslednjo vrednostjo. Na primer:

for n in range(1, 5):
    print(n)
    if n == 2 or n == 3:
        continue
    print('x')

pri številih 2 in 3, ki zadoščata pogoju, preskoči izpis znaka x, ki bi moral slediti. Celoten izpis je tako:

1
x
2
3
4
x

Tudi stavek continue deluje tako za zanko for kot za zanko while.

Stavek pass pa ne stori ničesar. Na primer:

for n in range(1, 5):
    print(n)
    if n == 2 or n == 3:
        pass
    print('x')

pri številih 2 in 3, ki zadoščata pogoju, vstopi v pogojni stavek, vendar tam ne stori ničesar. Tako je izpis enak, kakor bi bil za program brez pogojnega stavka:

1
x
2
x
3
x
4
x

Stavek pass lahko uporabljamo kjerkoli v Pythonu, ne le v zankah. Najpogosteje ga uporabimo takrat, kadar Python zahteva, da napišemo vsaj en ukaz, vendar ne želimo storiti ničesar. Recimo, da imamo program:

for x in range(100):
    if x % 2 == 0:
        print(x, 'je sod')
    else:
        print(x, 'je lih')

in za trenutek želimo izklopiti izpisovanje sodih števil. Če bi napisali le

for x in range(100):
    if x % 2 == 0:
        # print(x, 'je sod')
    else:
        print(x, 'je lih')

bi se Python pritožil, da je prva veja pogojnega stavka prazna, saj komentarje ignorira. Seveda bi lahko celoten program preuredili v

for x in range(100):
    if x % 2 != 0:
        print(x, 'je lih')

vendar tega ne želimo (sploh pri večjih programih). S pomočjo stavka pass pa lahko napišemo

for x in range(100):
    if x % 2 == 0:
        # print(x, 'je sod')
        pass
    else:
        print(x, 'je lih')

Tudi če se odločimo, da bi zopet vklopili izpisovanje, lahko stavek pass pustimo v kodi, ker ne stori ničesar.