Tole niso ravno zapiski predavanj. V njih ni ničesar o tem, kaj je pravzaprav rekurzivna funkcija. Se pravi, ničesar o tem, da lahko funkcije kličejo same sebe. Tu je povzetek, tistega, kar se dogaja in kar programiramo na predavanjih. Za potrebe ponavljanja in učenja bi moralo zadoščati.
V letih, ko ravno ni nobene epidemije, na teh predavanjih navadno igramo s študenti takole igro.
Določeno število študentov dobi listke s svojim imenom, svojo starostjo in imeni svojih otrok. Jaz jim potem zastavljam različna vprašanja, oni pa se lahko sprašujejo med sabo. Po Zoomu to najbrž gre, vendar ... bomo videli.
Dogovorimo se za nekaj pravil:
Ko vas nekdo nekaj vpraša, mu odgovorite – njemu. Dokler mu ne odgovorite, stojite (na Zoomu ... pač ne).
Po potrebi lahko za to, da boste "sestavili odgovor" kaj vprašate druge – navadno svoje otroke. Pri tem vedno sprašujete samo enega naenkrat, tako da poveste njegovo ime in vprašanje. Vprašanje lahko izpustimo, če gre za enako vprašanje, kot ste ga pravkar zastavili komu drugemu ali pa ga je kdo pravkar zastavil vam.
Da bodo stvari lepše tekle, se dogovorimo še, da morate spraševati svoje otroke v takšnem vrstnem redu, kot so napisani na listu.
Vsak sliši samo odgovore, ki so namenjeni njemu. Predstavljajte si, da si pošiljamo listke.
Ko odgovorite temu, ki vas je nekaj vprašal, pozabite odgovor. (Vendar šele takrat: dokler zbirate informacije, potrebne za odgovor, le-teh seveda ne pozabite.) Če vas kasneje vpraša kaj podobnega (ali celo isto), morate odgovor pridobivati ponovno. Vse vaše trajno "znanje" je to, kar piše na listku – vaše ime in imena vaših otrok.
Najstarejši član rodbine Novakovih, Adam, 111 let, ima štiri otroke: Matjaža, Cilko, Danieka in Erika. Matjaž ima enega, namreč Viljema. Danijel ima Elizabeto in Hansa (kasneje se je Daniel namreč preselil v predmestje Graza, kjer ima manjše podjetje, in se poročil z Avstrijko), Cilka in Erik pa nimata otrok. In tako naprej. Vse skupaj je nabrano v spodnjem slovarju.
= {
otroci "Adam": ["Matjaž", "Cilka", "Daniel"],
"Aleksander": [],
"Alenka": [],
"Barbara": [],
"Cilka": [],
"Daniel": ["Elizabeta", "Hans"],
"Erik": [],
"Elizabeta": ["Ludvik", "Jurij", "Barbara"],
"Franc": [],
"Herman": ["Margareta"],
"Hans": ["Herman", "Erik"],
"Jožef": ["Alenka", "Aleksander", "Petra"],
"Jurij": ["Franc", "Jožef"],
"Ludvik": [],
"Margareta": [],
"Matjaž": ["Viljem"],
"Petra": [],
"Tadeja": [],
"Viljem": ["Tadeja"],
}
Znane so tudi starosti vseh teh ljudi. V teh zapiskih jih sicer ne bomo potrebovali, uporabne pa so za kakšne druge naloge.
= {
starost "Adam": 111, "Matjaž": 90, "Cilka": 88, "Daniel": 85, "Erik": 83,
"Viljem": 58, "Tadeja": 20, "Elizabeta": 68, "Hans": 64, "Ludvik": 50,
"Jurij": 49, "Barbara": 45, "Herman": 39, "Mihael": 32, "Franc": 30,
"Jožef": 29, "Margareta": 3, "Alenka": 9, "Aleksander": 5, "Petra": 7}
Celoten rodovnik je takšen (vendar tega študenti, vsaj v začetku igre, ne vidijo!).
Napišimo, takole, za preprosto vajo, funkcijo, ki ji podamo osebo in pove, koliko otrok ima.
def stevilo_otrok(oseba):
return len(otroci[oseba])
"Jožef") stevilo_otrok(
Kako pa bi izvemo število vnukov posamezne osebe? Tako da gremo prek vseh otrok in seštevamo število njihovih otrok, recimo z
def stevilo_vnukov(oseba):
= 0
v for otrok in otroci[oseba]:
+= len(otroci[otrok])
v return v
"Daniel") stevilo_vnukov(
ali, brez velike razlike,
def stevilo_vnukov(oseba):
= 0
v for otrok in otroci[oseba]:
+= stevilo_otrok(otrok)
v return v
"Daniel") stevilo_vnukov(
Uh, kaj kompliciramo, saj že od predprejšnjega tedna znamo
def stevilo_vnukov(oseba):
return sum(stevilo_otrok(otrok) for otrok in otroci[oseba])
Do sem - nič posebnega. Zdaj pa pridejo zanimive reči: za nekoga nas zanima, velika je njegova rodbina, skupaj z njim, njegovimi otroki, vnuki, pravnuki in tako naprej. Recimo, da ima rojstni dan in bo povabil vso svojo rodbino na večerjo. Koliko krožnikov za juho potrebuje.
(Na predavanjih navadno vprašam nekoga, recimo Adama, po velikosti njegove rodbine.)
Kaj mu je storiti? Vse svoje otroke, bo vprašal, kako velike so njihove rodbine. To bo seštel in prištel še sebe. Kako bodo ti otroci izvedeli velikosti svojih rodbin? Tako, da bodo vprašali vse svoje otroke po velikosti njihovih rodbin, to sešteli in prišteli še sebe. Pa njihovi otroci? Enako.
Spremenimo to v funkcijo. Velikost rodbine dobimo tako, da gremo prek otrok in seštevamo velikosti njihovih rodbin.
def velikost_rodbine(oseba):
= 0
v for otrok in otroci[oseba]:
+= velikost_rodbine(otrok)
v return v + 1
"Elizabeta") velikost_rodbine(
Za tiste, ki znajo snov izpred dveh tednov:
def velikost_rodbine(oseba):
return sum(velikost_rodbine(otrok) for otrok in otroci[oseba]) + 1
"Elizabeta") velikost_rodbine(
Tule je primeren trenutek, da povemo nekaj pomembnega - kar je
pravzaprav očitno, ampak vam malo kasneje morda ne bo: vsaka
funkcija ima svoje lokalne spremenljivke. To vemo že nekaj
časa. A tudi, ko funkcija kliče samo sebe, ima vsaka
"inkarnacija" funkcije svoje spremenljivke. Funkcija
velikost_rodbine
si pripravi v = 0
. Nato ga
povečuje. A ko kliče samo sebe, in si v (rekurzivnih) klicih funkcija
pripravi v = 0
, je to drug in ne isti
v
.
Kako odkriti, ali je v rodbini določene osebe oseba s takšnim in takšnim imenom?
Storiti nam je tole: če je tako ime ravno vprašani osebi, bo
odgovorila True
. Sicer bo enega za drugim spraševala
otroke, dokler prvi ne odgovori True
; tedaj vrnemo
True
. Če noben otrok nima takšnega potomca - in torej noben
otrok ne odgovori True
, odgovorimo False
. Z
drugimi besedami,
def obstaja_ime(oseba, ime):
if oseba == ime:
return True
for otrok in otroci[oseba]:
if obstaja_ime(otrok, ime):
return True
return False
"Elizabeta", "Franc") obstaja_ime(
S snovjo izpred dveh tednov:
def obstaja_ime(oseba, ime):
return oseba == ime or any(obstaja_ime(otrok, ime) for otrok in otroci[oseba])
"Elizabeta", "Franc") obstaja_ime(
"Elizabeta", "Herman") obstaja_ime(
Kako velika je največja družina v rodbini neke osebe - s tem mislimo le otroke, brez staršev? Tu osebe razmišljajo tako: najprej predpostavijo, da je to njihova družina - največ otrok je torej toliko otrok, kolikor jih imajo oni. Potem vprašajo vsakega od otrok, kako velika je največja družina v njegovi rodbini. Če naleti na koga z večjo družino, si to zapomni. Na koncu vrne največ, kar je videl.
def najvec_otrok(oseba):
= len(otroci[oseba])
najvec for otrok in otroci[oseba]:
= najvec_otrok(otrok)
koliko if koliko > najvec:
= koliko
najvec return najvec
Največja družina v Danielovi rodbini ima tri otroke, zato
"Daniel") najvec_otrok(
3
Kdor zna, zna takole:
def najvec_otrok(oseba):
return max([len(otroci[oseba])] + [najvec_otrok(otrok) for otrok in otroci[oseba]])
"Daniel") najvec_otrok(
3
Ob reševanju te naloge znajo študenti pogosto zagrešiti hud greh. Več o njem na koncu zapiskov.
Katero je najdaljše ime v rodbini neke osebe? Tole je precej podobno največjemu številu otrok: najdaljše je moje, razen če je daljše katero od imen v rodbini katerega od otrok.
def najdaljse_ime(oseba):
= oseba
najdaljse for otrok in otroci[oseba]:
= najdaljse_ime(otrok)
naj_pod if len(naj_pod) > len(najdaljse):
= naj_pod
najdaljse return najdaljse
"Adam") najdaljse_ime(
'Aleksander'
(Z izpeljanimi seznami bi šlo enako kot prej. A pustimo.)
Kako globoka je rodbina določene osebe? Torej, nekdo, ki nima otrok, ima rodbino globine 0. Če ima otroke, nima pa vnukov, ima rodbino globine 1. Če ima tudi kakega vnuka, vendar nobenega pravnuka, ima rodbino globine 2.
Globino rodbine izračunamo tako, da vprašamo vse otroke po globinah
njihovih rodbin in k največji globini, ki jo dobimo, prištejemo 1.
Začetna največja globina pa bo -1
; če oseba nima otrok, bo
tudi ostala -1, in ko bomo prišteli 1, bo 0. Kot mora biti.
def globina(oseba):
= -1
najvecja for otrok in otroci[oseba]:
= globina(otrok)
g if g > najvecja:
= g
najvecja return najvecja + 1
"Elizabeta") globina(
3
Ali, krajše
def globina(oseba):
return max([globina(otrok) for otrok in otroci[oseba]], default=-1) + 1
"Elizabeta") globina(
3
Pripadnike Novakove rodbine smo nato spraševali, koliko potomstva imajo. S potomci mislimo nekaj takšnega kot rodbino, a brez te osebe same. Jurij (ki ima dva otroka in tri vnuke) ima pet potomcev, čeprav je velikost njegove rodbine enaka 6.
Tale zahteva malo razmisleka. Navidez bi jo lahko ugnali tako, kot smo velikost rodbine, le 1 ne smemo prišteti na koncu, saj oseba ne sme šteti sebe.
def stevilo_potomcev(oseba):
= 0
v for otrok in otroci[oseba]:
+= stevilo_potomcev(otrok)
v return v
Zoprna reč je, da je ta funkcija nekoliko napačna. No, precej napačna. Vedno vrne 0 - ker nihče nikoli ničesar ne prišteje, vse seštevajo samo ničle. In iz ničel nikoli ne boš dobil ničesar, pa jih seštevaj, kolikor dolgo hočeš.
"Elizabeta") stevilo_potomcev(
0
Ena rešitev je, da vsak vrne število svojih otrok, ki čemur morajo otroci prišteti število svojih otrok, in vnuki število svojih...
def stevilo_potomcev(oseba):
= len(otroci[oseba])
potomcev for otrok in otroci[oseba]:
+= stevilo_potomcev(otrok)
potomcev return potomcev
"Elizabeta") stevilo_potomcev(
8
Ali isto, le na drug način:
def stevilo_potomcev(oseba):
= 0
potomcev for otrok in otroci[oseba]:
+= 1 + stevilo_potomcev(otrok)
potomcev return potomcev
"Elizabeta") stevilo_potomcev(
8
Lahko pa si pomagamo tudi z rodbino:
def stevilo_potomcev(oseba):
return velikost_rodbine(oseba) - 1
"Elizabeta") stevilo_potomcev(
8
Rešimo nekoliko preprostejšo nalogo od gornjih - ker bo vodila v nekoliko zahtevnejšo spodnjo. Izpisali bi radi vse člane rodbine določene osebe.
Naloga je res preprosta: vsak izpiše svoje ime in pozove svoje otroke, naj storijo isto.
def izpis(oseba):
print(oseba)
for otrok in otroci[oseba]:
izpis(otrok)
"Adam") izpis(
Adam
Matjaž
Viljem
Tadeja
Cilka
Daniel
Elizabeta
Ludvik
Jurij
Franc
Jožef
Alenka
Aleksander
Petra
Barbara
Hans
Herman
Margareta
Erik
Zdaj pa napišimo funkcijo rodbina(oseba)
, ki vrne seznam
imen vseh članov rodbine podane osebe. Funkcija je nadvse poučna zato,
ker jo študenti zelo vztrajno programirajo narobe. Na vsak način si jo
namreč želijo sprogramirati tako, da bi sestavili seznam, v katerega
mora vsak dopisati sebe in nato k temu povabiti še svoje otroke.
Slediti želijo gornji funkciji, le print
bi zamenjali z
append
. Tako naredijo tole.
def rodbina(oseba):
clani.append(oseba)for otrok in otroci[oseba]:
rodbina(otrok)
Ideja je, da se vsi dopisujejo v seznam clani
. In to -
kot je vsem, ki to napišejo, jasno na prvi pogled, ne deluje, ker nimamo
seznama clani
. Zato v resnici naredijo tole.
def rodbina(oseba):
= []
clani
clani.append(oseba)for otrok in otroci[oseba]:
rodbina(otrok)return clani
"Adam") rodbina(
['Adam']
Kot je jasno vsakemu, ki ve vsaj kaj malega o eni od treh razširjenih religijah, namreč judovski, krščanski in muslimanski (in order of appearance), je zgolj število trenutno živečih članov Adamove rodbine okrog sedem milijard in pol (število vseh ljudi, ki so bili kdaj na svetu, pa okrog sto milijard). No, v našem rodovniku pa jih je, skupaj z Adamom, 19. Funkcija pa vrne le Adama.
Zakaj? Logično. Kaj počnemo s seznamom člani? Pripravimo prazen
seznam, vanj dodamo osebo in ga vrnemo. Tisti dve vrstici, ki sta vmes
(zanka in klic v njej) se seznama clani
ne dotikata. Vsaka
funkcija ima svoje lokalne spremenljivke. Vsi ti klici funkcij
si ne delijo istega seznama clani
, saj ima - kot
smo se ponovno spomnili precej na začetku, ob funkciju
velikost_rodbine
, vsaka funkcija svoje lokalne
spremenljivke.
Študent, ki napiše gornje, je naredil zgolj napako. V obupu pa se zatečejo iz napake naravnost v greh. Naredijo pogodbo s hudičem (v obliki globalne spremenljivke) in mislijo, da jih bo to rešilo.
= []
clani
def rodbina(oseba):
clani.append(oseba)for otrok in otroci[oseba]:
rodbina(otrok)return clani
"Adam") rodbina(
['Adam',
'Matjaž',
'Viljem',
'Tadeja',
'Cilka',
'Daniel',
'Elizabeta',
'Ludvik',
'Jurij',
'Franc',
'Jožef',
'Alenka',
'Aleksander',
'Petra',
'Barbara',
'Hans',
'Herman',
'Margareta',
'Erik']
Nasvet nekoga, ki rad bere ljudske zgodbe in pripovedke: pogodbe s hudičem se nikoli ne splačajo. Kratkoročno izgleda, da je junak zgodbe uspel, potem pa pride tvist, kjer hudič zmaga. (Edina znana izjema v zgodovini človeštva je oni nemški kovač; več o njem na Myths and Legends, začetek zgodbe je pri 17:45.)
Torej: zgoraj je videti, da funkcija deluje. Za vsak slučaj poglejmo še Jožefovo rodbino, ki, kot vemo, obsega njega in njegove tri otroke.
"Jožef") rodbina(
['Adam',
'Matjaž',
'Viljem',
'Tadeja',
'Cilka',
'Daniel',
'Elizabeta',
'Ludvik',
'Jurij',
'Franc',
'Jožef',
'Alenka',
'Aleksander',
'Petra',
'Barbara',
'Hans',
'Herman',
'Margareta',
'Erik',
'Jožef',
'Alenka',
'Aleksander',
'Petra']
Razumemo, kaj se dogaja? Vsakič, ko pokličemo funkcijo, dodaja nove
ljudi v isti seznam. Ta bo vsakič vedno daljši. Potem se grešnik
domisli, da bi clani
spraznil na začetku klica
funkcije,
= []
clani
def rodbina(oseba):
= []
clani
clani.append(oseba)for otrok in otroci[oseba]:
rodbina(otrok)return clani
"Adam") rodbina(
['Adam']
To ne deluje iz enakega razloga, iz katerega ne deluje že prvič.
clani
je zdaj spet lokalna spremenljivka funkcije, katere
ime je slučajno enako imenu globalne spremenljivke.
Grešnik išče odrešenja v tem, da v funkciji ne naredi nove, lokalne spremenljivke, temveč sprazni globalno,
= []
clani
def rodbina(oseba):
clani.clear()
clani.append(oseba)for otrok in otroci[oseba]:
rodbina(otrok)return clani
"Adam") rodbina(
['Erik']
a tudi to ne obrodi bistveno boljši rezultatov, saj se ena in ista spremenljivka praznita ob vsakem rekurzivnem klicu in na koncu vsebuje tisto vrednost, ki jo je tja vpisala zadnja oseba, za katero smo poklicali funkcijo.
Kdor naredi pogodbo s hudičem, se zezne. Rekurzija in globalne spremenljivke so zelo slaba kombinacija.
Osnovni problem ni v tem, da ne bi znali sprogramirati, temveč že v
tem, da narobe razmišljamo. Tule znotraj funkcije očitno pokličemo
funkcijo rodbina(otrok)
, ki vrne nek rezultat, mi pa s tem
rezultatom na naredimo ničesar. To ne more biti prav, ne? (Picajzlasto
gledano: lahko bi bilo prav. Vendar bi bilo treba sprogramirati grše in
računati na "stranske efekte" funkcije, kar pa je prav tako zelo
grdo.)
Razmišljati moramo z vidika igre, ki jo igramo ob učenju rekurzije v predavalnici: vsak otrok sporoči svojo rodbino in to, kar vrnejo otroci, je potrebno seštevati.
def rodbina(oseba):
= [oseba]
clani for otrok in otroci[oseba]:
+= rodbina(otrok)
clani return clani
"Adam") rodbina(
['Adam',
'Matjaž',
'Viljem',
'Tadeja',
'Cilka',
'Daniel',
'Elizabeta',
'Ludvik',
'Jurij',
'Franc',
'Jožef',
'Alenka',
'Aleksander',
'Petra',
'Barbara',
'Hans',
'Herman',
'Margareta',
'Erik']
"Jožef") rodbina(
['Jožef', 'Alenka', 'Aleksander', 'Petra']
Funkcija globina_imena(oseba, ima)
naj pove, kako
globoko v rodbini podane osebe je potomec s podanim imenom. Če gre za
eno in isto osebo; naj vrne 0; če za otroka, vrne 1; če za vnuka, 2; če
za pravnuka, 3... Če oseba nima potomca s podanim imenom, pa naj
funkcija vrne None
.
Gre za variacijo funkcije obstaja_ime
. Tako kot prej
tudi tu vrnemo None
, če imena ni. Če kateri od otrok pove,
da je dotični potomec na globini n
, pa je ta potomec, glede
na to osebo, na globini n + 1
.
def globina_imena(oseba, ime):
if oseba == ime:
return 0
for otrok in otroci[oseba]:
= globina_imena(otrok, ime)
n if n != None:
return n + 1
return None
"Daniel", "Jožef") globina_imena(
3
Pri najvec_otrok
sem opozoril, da znajo študenti pri
programiranju te funkcije narediti zoprno napako. Tudi
globina_imena
ponuja podobno skušnjavo. Marsikateri študent
bi jo skrajšal za eno vrstico in naredil tako:
def globina_imena(oseba, ime):
if oseba == ime:
return 0
for otrok in otroci[oseba]:
if globina_imena(otrok, ime) != None:
return globina_imena(otrok, ime) + 1
return None
"Daniel", "Jožef") globina_imena(
3
def globina_imena(oseba, ime):
print(oseba)
if oseba == ime:
return 0
for otrok in otroci[oseba]:
= globina_imena(otrok, ime)
n if n != None:
return n + 1
return None
"Daniel", "Jožef") globina_imena(
Daniel
Elizabeta
Ludvik
Jurij
Franc
Jožef
3
Druga funkcija - tista, ki se pokliče dvakrat.
def globina_imena(oseba, ime):
print(oseba)
if oseba == ime:
return 0
for otrok in otroci[oseba]:
if globina_imena(otrok, ime) != None:
return globina_imena(otrok, ime) + 1
return None
"Daniel", "Jožef") globina_imena(
Daniel
Elizabeta
Ludvik
Jurij
Franc
Jožef
Jožef
Jurij
Franc
Jožef
Jožef
Elizabeta
Ludvik
Jurij
Franc
Jožef
Jožef
Jurij
Franc
Jožef
Jožef
3
Pričakovali bi dvakrat daljši spisek ... vendar je spisek očitno več kot dvakrat daljši.
Kolikokrat se na njem pojavi Jožef? Osemkrat!
Daniel dvakrat vpraša Elizabeto. To drži. Elizabeta dvakrat vpraša Jurija; vendar je sama vprašana dvakrat, torej je Jurij vprašan štirikrat. Jurij pa dvakrat vpraša Jožefa; Jurij sam je vprašaan štirikrat, torej je Jožef osemkrat. Kot je očitno iz spiska.
Število vprašanj se v vsakem nivoju podvoji. Pri drevesu globine 5, kot je naše, so nekateri vprašani 32-krat. Pri drevesu globine 10 so vprašani 1024-krat. Pri drevesu globine 20 pa že več kot milijonkrat - namesto dvajsetkrat.
V rekurziji se moramo res izogniti temu, da bi isto funkcijo brez potrebe klicali večkrat.
Več o tem in o lru_cache
pa v dodatnih predavanjih.
Še veliko nalog na temo rodbine najdete na strani predmeta.