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. Pišemo jo kot

while pogoj:
    # stavki, ki jih ponavljamo
    # od prvega do zadnjega,
    # dokler velja pogoj

Na primer, program

n = 12
while n < 1000:
    n = n * 2
    print(n)
24
48
96
192
384
768
1536

bo n nastavil na 12, nato pa ga toliko časa podvojeval in izpisoval, dokler njegova vrednost ne bo presegla 1000.

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

Zgornji program bi tako na krajše lahko napisali kot:

n = 12
while n < 1000:
    n *= 2
    print(n)
24
48
96
192
384
768
1536

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
    print(stopnja)
stopnja
1
2
3
4
5
6
7
7

Program bi lahko pretvorili tudi v splošnejšo funkcijo:

def celostevilski_logaritem(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
celostevilski_logaritem(81, 3)
4
celostevilski_logaritem(1580160, 2)
7

Isto funkcijo bi lahko napisali tudi z rekurzijo:

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

Vseeno v praksi 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). Poleg tega 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 po določenem številu klicev ustavi:

celostevilski_logaritem_rek(2 ** 2950, 2)
2950
celostevilski_logaritem_rek(2 ** 2960, 2)
---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-12-aae401b5e439> in <module>
----> 1 celostevilski_logaritem_rek(2 ** 2960, 2)

<ipython-input-8-fbdf32098d56> in celostevilski_logaritem_rek(n, k)
      2     """Vrne stopnjo največje potence števila k, ki še deli n."""
      3     if n % k == 0:
----> 4         return 1 + celostevilski_logaritem_rek(n // k, k)
      5     else:
      6         return 0

... last 1 frames repeated, from the frame below ...

<ipython-input-8-fbdf32098d56> in celostevilski_logaritem_rek(n, k)
      2     """Vrne stopnjo največje potence števila k, ki še deli n."""
      3     if n % k == 0:
----> 4         return 1 + celostevilski_logaritem_rek(n // k, k)
      5     else:
      6         return 0

RecursionError: maximum recursion depth exceeded in comparison

Pri zankah teh težav ni:

celostevilski_logaritem(2 ** 2950, 2)
2950
celostevilski_logaritem(2 ** 2960, 2)
2960
celostevilski_logaritem(2 ** 10000, 2)
10000

Se pa lahko pri zanki while zgodi, da se njeno izvajanje nikoli ne zaključi. Na primer, če bi poklicali celostevilski_logaritem(12345, 1), bi bil ostanek pri deljenju z 1 v pogoju vedno enak 0 in zanka bi tekla v neskončnost. Ko se naveličamo čakanja, lahko pritisnemo Ctrl-C in izvajanje prekinemo.

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, ki jo pišemo kot:

for spremenljivka in vrednosti:
    # stavki, ki jih izvedemo
    # po enkrat za vsako izmed
    # podanih vrednost spremenljivke

izvede pa se enako, kot če bi napisali

# v spremenljivko shrani prvo vrednost
# izvedi vse stavke v telesu zanke
# v spremenljivko shrani drugo vrednost
# izvedi vse stavke v telesu zanke
# ...
# v spremenljivko shrani zadnjo vrednost
# izvedi vse stavke v telesu zanke

Na primer, čez vse črke danega niza se sprehodimo kot:

for znak in 'to je en niz':
    print(znak)
t
o
 
j
e
 
e
n
 
n
i
z

samoglasnike pa lahko preštejemo kot:

def stevilo_samoglasnikov(niz):
    stevilo = 0
    for znak in niz:
        if znak.lower() in 'aeiou':
            stevilo += 1
    return stevilo
stevilo_samoglasnikov('Uvod v programiranje')
7

Če se želimo sprehoditi po številih, uporabimo funkcijo range. Ta zaporedoma vrača vsa števila v danem razponu:

for x in range(5, 10):
    print(x ** 2)
25
36
49
64
81

Vidimo, da tako kot rezine tudi range ne doseže zgornje meje. Če funkciji range podamo en argument, bo začela šteti z 0, če pa ji podamo še tretji argument, ga bo uporabila za velikost koraka (kot pri rezinah).

for x in range(5):
    print(x)
0
1
2
3
4
for x in range(5, 10, 2):
    print(x)
5
7
9

S pomočjo funkcije range bi fakulteto torej napisali kot:

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

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')
1
x
2

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 in preneha z izpisovanjem.

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')
1
x
2
3
4
x

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

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')
1
x
2
x
3
x
4
x

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

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.

Metoda Monte-Carlo

TODO