Zapiski

Sodi in lihi

Recimo, da si želimo napisati funkciji, ki bosta povedal, ali je seznam sestavljen iz izmenjujočih se lihih in sodih števil. Prva, sodo_lihi(s) vrne True, če se seznam začne s sodimi številom (in nadaljuje z lihim, sodim, lihim...) Druga vrne True, če se začne z lihim (in nadaljujej s sodim, lihim, sodim...) Za prazne sezname obe funkciji vrneta True.

Lotimo se najprej prve. Kar počasi. Najprej bomo le preverili, ali je seznam morda prazen in v tem primeru veseli vrnili True.

def sodo_lihi(s): if len(s) == 0: return True

Nato preverimo, ali je prvi element lih. (Seznam s na tej točki gotovo ima vsaj element, sicer bi že vrnili True in tako končali računanje). Če je lih, vrnemo False.

if s[0] % 2 == 1: return False

Zdaj, ko bi morali začeti z resnim delom, pa se spomnimo bližnjice (študenti se pač vedno spomnijo bližnjice). Rekli smo, da bomo napisali dve funkciji, namreč sodo_lihi in liho_sodi. Za prvi element tegale seznama s vemo, da je sod, ostanek seznama pa mora biti lih, sod, lih, sod ... Z drugimi besedami: ostanek seznama mora biti liho_sod. Ker bomo imeli za preverjanje liho-sodosti posebno funkcijo (no, ja, res je v tem trenutku sicer še nimamo, ampak vsak čas jo bomo napisali), lahko preostanek dela opravimo kar v oni funkciji. Celotna funkcija sodo_lihi bi bila torej

def sodo_lihi(s): if len(s) == 0: return True if s[0] % 2 == 1: return False return liho_sodi(s[1:])

Torej: če je prazen, je sodo-lih. Če se začne z lihim, ni sodo-lih. Sicer pa le preverimo, ali je seznam od prvega elementa naprej (s[1:]) liho sod. Če je, je celoten seznam sodo-lih, če ni, ni. Funkcija lahko torej preprosto vrne to, kar vrne liho_sodi na preostanku seznama.

Funkcijo sodo_lihi smo torej prigoljufali. Zdaj pa zares sprogramirajmo liho_sodi.

Začne se zelo podobno: če je seznam prazen, je liho-sod. Če se začne s sodim, ni liho-sod.

def liho_sodi(s): if len(s) == 0: return True if s[0] % 2 == 0: return False

Zdaj pa ponovimo razmislek od prej: ves seznam od drugega elementa naprej mora biti sodo-lih, drži? In na srečo imamo funkcijo - je mar nismo ravnokar napisali? - ki preveri, ali je nek seznam sodo-lih.

def liho_sodi(s): if len(s) == 0: return True if s[0] % 2 == 0: return False return sodo_lihi(s[1:])

Da bo še očitneje, kaj smo naredili in kako učinkoviti lenuhi smo, napišimo funkciji krajše.

def sodo_lihi(s): return not s or s[0] % 2 == 0 and liho_sodi(s[1:]) def liho_sodi(s): return not s or s[0] % 2 == 1 and sodo_lihi(s[1:])

Seznam je sodo-lih, če je prazen ali pa je prvi element sod in ostanek seznama liho-sod.

Seznam je liho-sod, če je prazen ali pa je prvi element lih in ostanek seznama sodo-lih.

Kot je rekel nekdo na predavanjih, je to preveč lepo (uporabno? preprosto? - pozabil sem točne besede), da bi lahko delalo. No, pa dela.

Kako deluje, si oglejmo na primeru. Recimo, da pokličemo funkcijo sodo_lihi([2, 7, 4, 1, 8]). Ta ugotovi, da je prvi element sod in se odloči, da bo potrebno le še preveriti, ali je preostanek liho-sod, zato pokliče liho_sodi([7, 4, 1, 8]). Funkcija liho_sodi ugotovi, da je prvi element zgledno lih in se odloči preveriti, ali je ostanek sodo-lih, zato pokliče sodo_lihi([4, 1, 8]). Funkcija sodo_lihi je zadovoljna s sodostjo štirice in se odloči preveriti, ali je ostanek liho sod, zato pokliše liho_sodi([1, 8]). Ker je število težko še bolj liho, kot je liha enica, je potrebno preveriti le še, ali je ostanek sod, torej pokliče sodo_lihi([8]). Ta ugotovi, da je 8 soda in preveri, ali je ostane liho-sod, zato pokliče liho_sodi([]). Prazen seznam je liho-sod, zato funkcija vrne True, ne da bi preverjala karkoli drugega. Ta rezultat vrne funkciji, ki jo je poklicala. Ta ga vrne funkciji, ki jo je poklicala. Ta ga vrne ... in tako naprej.

V zvezi s tem se pri študentih pojavi blago nelagodje. Po doslej zbranih podatkih, izvira iz več dejstev.

Prvič: v funkciji sodo_lihi kličemo funkcijo, ki še ni definirana. (Da v funkciji liho_sodi pokličemo funkcijo sodo_lihi, zveni manj škandalozno.)

S tem ni nič narobe. Funkcija mora biti definirana takrat, ko jo kličemo, ne takrat, ko se prvič sklicujemo nanjo. Funkcija liho_sodi mora biti torej definirana v trenutku, ko pokličemo funkcijo sodo_lihi. To pa je. (Mimogrede, v mnogih jezikih to ni tako samoumevno. V nekaterih bi morali pred funkcijo sodo_lihi obljubiti, da bomo nekoč nekje definirali tudi liho_sodi, zraven pa še povedati, koliko kakšnih argumentov bo sprejemala. V nekaterih drugih pa bi morali obe funkciji definirati nekako v "paketu".)

Drugič: če ena funkcija kliče drugo in druga nazaj prvo - se bo to sploh kdaj končalo? Se bo vedno končalo?

Odgovor je očiten. Tole se vedno konča, ker je seznam v vsakem klicu za en element krajši. Prej ko slej bo prazen in tedaj se ne kličemo več.

Tretjič: kako, da se imena ne pomešajo med sabo? Saj se vendar vsi argumenti imenujejo s. Je kaj narobe, ker imamo toliko s-ov?

O tem smo se učili prejšnjič. Vsaka funkcija ima svoje lokalne spremenljivke. Koliko, katere, kako jih imenuje - je njena stvar. Enako velja za argumente. Vsaka druga funkcija v Pythonu (in, najbrž, vseh normalnih jezikih), ima spremenljivko z imenom i. Ampak vsaka funkcija ima svoj i - pa čeprav je vsem ime i. In še več: če takole večkrat pokličemo isto funkcijo - v tem perverznem podajanju dela - ima funkcija ob vsakem klicu svoj s. Lokalne spremenljivke pravzaprav ne pripadajo funkcijam, temveč klicem te funkcije.

Da imamo toliko teh s-ov (in še druge šare - predstavljajte si funkcijo, ki bi imela veliko lokalnih spremenljivk) sicer porabi nekaj pomnilnika, vendar se zaradi tega ne vznemirjamo. V Pythonu ta slog programiranja - klicanje tja in nazaj - uporabljamo le, kadar je potrebno in ne gre tako zelo globoko, da bi nas to začelo motiti. Jeziki, v katerih se to več uporablja, pa imajo določene trike, s katerimi zagotovijo, da reč požre manj pomnilnika.

Četrtič: kako Python ve, kje je?

To pa ni vaš problem. Ve pač. Tule je pomembna vera. Po tem, ko ste poskrbeli, da se bo reč nekoč končala, se obnašate, kot da funkcije, ki jih potrebujemo, obstajajo in delajo, kar naj bi delale. Če verjamete, da bodo delovale in jih uporabljate, potem tudi v resnici bodo delovale. (Seveda le, če so pravilno napisane.)

Python postavlja v zvezi s tem neko omejitev: klici funkcij lahko gredo do 1000 nivojev globoko. Potem javi napako, ker verjame, da smo nekje nekaj zamočili. To mejo lahko tudi dvignemo, saj ni "tehnična", temveč le "varnostna".

Sodi

Zdaj ko smo morda pregnali dvome, priženimo stvar še dlje. Napišimo funkcijo sodi(s), ki ugotovi, ali seznam s vsebuje sama soda števila.

Seznam vsebuje sama soda števila, če je prazen ali pa, če je prvo število sodo in tudi preostanek vsebuje samo soda števila.

Povejmo počasi in sproti programirajmo. Seznam vsebuje sama soda števila, če je prazen (not s) ali (or) pa je prvo število sodo (s[0] % 2 == 0) in (and) tudi preostanek vsebuje samo soda števila. Hm, pa imamo kakšno funkcijo, s katero bi lahko ugotovili ali preostanek (s[1:]) vsebuje sama soda števila? Seveda: preostanek je pač seznam in mi seveda imamo (točneje: pravkar dobivamo) funkcijo, ki preveri, ali nek seznam vsebuje sama soda števila.

def sodi(s): return not s or s[0] % 2 == 0 and sodi(s[1:])

Tole zveni precej hujše od onega prej. Tam je funkcija sodi_lihi klicala neko drugo funkcijo (ki je pač klicala to funkcijo nazaj. Zdaj pa funkcija kliče kar samo sebe! Se to sploh sme?

Če pogledamo malo širše, tudi prej ni bilo veliko drugače. Funkcija sodi_lihi je posredno klicala samo sebe. Če je delalo tisto, ni razloga, da ne bi tudi to.

Takšnim funkcijam, kot je sodi, pravimo rekurzivne funkcije. Rekurzija pomeni nanašanje samo nase. Rekurzivna definicija (recimo rekurzivna definicija neke matematične funkcije) vsebuje samo sebe. V Google vtipkajte "recursion" in boste dobili nekaj zanimivega.

Tudi to, kar smo počeli s sodimi in lihimi, je rekurzija, le nekoliko neobičajnejša (a vseeno nič posebnega) od te.

Vsota

Za konec poglejmo še eno rekurzivno funkcijo: vsota(s), ki vrne vsoto elementov seznama s. Izračunamo jo takole: če je seznam prazen, je vsota 0. Sicer pa dobimo vsoto elementov tako, da k prvemu elementu prištejemo vsoto ostalih.

def vsota(s): if not s: return 0 return s[0] + vsota(s[1:])

Rekurzija je nekakšno prelaganje dela. Namesto da bi naredili, kar moramo, naredimo nekaj malega in ostanek prepustimo nekomu drugemu (čeprav smo ta, drugi, morda mi sami).

Pri tem "prelaganju dela" mora biti preloženo delo nekoliko manjše. Če bi napisali

def vsota(s): return vsota(s)

to ne bi delovalo, ker bi bil seznam vedno enako dolg. Po tisoč klicih bi Python obupal in javil napako.

Zgoraj pa smo naredili nekaj malega in ostanek prepustili funkciji, ki jo pišemo. To pa deluje.