Kakih šest (neuspešnih) načinov poučevanje rekurzije

Predavanje ne bo govorilo o teoriji, temveč o praksi -- o tem, kaj sem doslej počel, ko sem učil rekurzijo. Vse sem delal čisto "po občutku", kar pa ne pomeni, da je s teorijo skregano. Nasprotno, na vsako stvar bom poskusil vsaj malo posvetiti s kakšno (post hoc) teoretično utemeljitvijo.

Rekurzija je otročje lahka

Z različnimi skupinami otrok - od krožkov do raznih delavnic in dogodivščin Hiše eksperimentov - pogosto urejamo plastenke. Otroci skoraj vedno odkrijejo urejanje z izbiranjem. To je imenitno, ker je - od "običajnih" algoritmov - edini z enakim številom primerjav v najslabšem in najboljšem primeru. Če delamo po skupinah ugotovimo, da so vse (razen morda kake, kjer so se zmotili) potrebovale enako število primerjav. Preverimo, zakaj je tako, poiščemo formulo in vidimo, kako reč narašča. In začnemo razmišljati, ali morda obstaja hitrejši postopek. Učenci ga še nikoli niso našli, zato običajno nadaljujem tako, da vzamem eno od plastenk (pri čemer malo goljufam in jih potežkam nekaj, tako da vzamem približno mediano) in ostale razdelim na lažje (levo) in težje (desno) od te. To pa postavim vmes, na sredo. Nato opozorim, da plastenke s tem še niso urejene in vprašam, kaj moram storiti zdaj.

Ko sem to naredil prvič, v krožku z učenci 5. in 6. razreda, me je presenetilo, ko so se mnogi hkrati oglasili, da pač ponovimo isto na obeh straneh. Drugič, tretjič in n-tič sem videl, da je to otrokom čisto jasno. Ker ... zakaj ne bi bilo? Da odkrijejo hitro urejanje, jim je potrebno namigniti prvi korak, delitev na pol glede na en element. Naprej je jasno. Pravzaprav jim nisem izdal prvega koraka, temveč vse korake. To, da ta korak pač ponavljamo na obeh straneh, zanje ni miselni preskok. Pri otroku prepoznaš miselni preskok po tem, da se mu zasvetijo oči ali da se začne smejati, kot pri dobri šali. Tu se niso smejali, ker je bila šala preveč očitna. Kaj pa je to takega?

Osem let kasneje sedijo ti otroci v PA na Večni poti 113. Osem let in pol kasneje sedijo ti otroci v učilnicah. V letu 2016/17 sem Programiranje 1 predaval 230 študentov treh različnih študijev. 150 jih je opravilo sprotno delo in večina teh (130) je prišla na prvi izpitni rok. Reševali so pet nalog, med katerimi so morali pri eni napisati rekurzivno funkcijo. S to nalogo se je spopadlo 46 študentov. Od tega dobrih dvajset dovolj uspešno, da so dobili večino točk -- funkcija je morda imela kako napako, a rekurzijo znajo.

Zakaj otroci razumejo rekurzijo pri desetih letih, ne pa pri dvajsetih? Ker je desetletnikom nisem dal programirati? In je ni težko razumeti, težko jo je sprogramirati? Pokazal bom argument proti. In tudi za.

Recept, ki je v tvoji glavi

Pri Programiranju 1 spodbujam študente, naj ob programiranju razmišljajo, kako bi oni to naredili. Seveda moraš za to postaviti primerno zgodbo in primerne omejitve. Primer je recimo, ko začnemo s seznami in zanko for (v Pythonu je logično sezname obravnavati pred zanko for, saj brez seznamov s for nimamo kaj početi). Tako, recimo, iščemo največji element seznama tako, da vajo najprej izvedemo s študenti: jaz povem kakih dvajset števil in oni mi morajo povedati največjo. Potem jim rečem, naj mi naštejejo vsa števila; ko ne znajo, ker si jih niso zapomnili, jih vprašam, kako da potem vejo, katero je bilo največje ... in potem sprogramiramo tisto, kar so "razmišljali", ko so poslušali moje naštevanje.

Skladno s tem sem imel, ko sem prvo leto predaval programiranje, prvo (od mnogih) genialnih idej, kako predavati rekurzijo. (Vsi jih imamo, vem.) Določil sem sedem prostovoljcev, jih postrojil pred tablo in dal vsakemu nekaj listov papirja. Računali mi bodo Fibonaccijeva števila: če jim kdo da v roko marker, morajo nanj napisati vsak svoje Fibonaccijevo število. Prvi prvo, drugi drugo in tako naprej. Vendar imajo spomin kot prislovična zlata ribica. Svojega števila si ne zapomnijo in ga morajo vedno znova računati. Če torej dobijo marker, ga podajo tistemu, ki stoji v vrsti pred njimi in čakajo, dokler jim ta ne vrne markerja hkrati z listom papirja z njegovo številko. Nato podajo marker svojemu predpredhodniku in počakajo. Ko imajo dva lista z dvema številkama, ju seštejejo, napišejo na svež list in ga skupaj z markerjem vrnejo tistemu, ki jim je podal marker. Izjema sta le prva dva v vrsti, ki ne podajata nikomur, temveč na list napišeta 1.

Ko so bila navodila jasna, sem dal marker tistemu, ki je bil na koncu vrste in počakal, da mi je čez par minut podal list s številko 13.

Po desetih letih sem letos ponovil to vajo s študenti pri Poučevanju algoritmičnega razmišljanja. Rezultat je bil takšen, kot sem ga želel: komentirali so, da je to toliko poučno kot oni madžarski plesi, ki kažejo algoritme urejanja. (Te sem jim pokazal teden ali dva prej in ugotovili smo, da je možno iz plesa prepoznati algoritem, ki naj bi se ga učil, vendar le, če ga res dobro poznaš.)

Kaj sem hotel s to vajo pokazati in zakaj mi je tako dobro neuspelo?

Moj pogled na rekurzivno funkcijo (ali formulo), ki je najbrž tudi pravilni, praktični pogled na rekurzivno funkcijo, je, da le-ta pravilno opiše en korak. Ta se skliče, pokliče, vsebuje, druge korake, ne ukvarja pa se s celotno sliko. Hotel sem povedati - pravzaprav sem eksplicitno povedal - da se je vsaka od teh "zlatih ribic" z markerjem ukvarjala le s svojim delom. Zanimalo jo je le od koga je dobila marker, komu ga mora podati in kaj mora početi z rezultati. Komu ga bodo podajali drugi, kako si bodo oni zapomnili, kam mora iti marker ... vse to jih ne briga. Celotna pot markerja je lahko zapletena, a zlatih ribic to ne skrbi. Ukvarjajo se samo s svojim korakom.

To sem hotel pokazati. Kaj pa so študenti videli? Kup šelestenja papirja. In marker, za katerega nihče ni vedel, kje je že bil in kam bo še šel. Morda so udeleženci sami razumeli, kako brezskrbni so lahko in kako celotna slika ni njihov problem.

Kakorkoli. Bistvo vaje je bilo, da smo potem sprogramirali "program, ki je tekel v njihovih glavah". Če gre za študenta z indeksom 0 ali 1, vrne 1. Sicer vrne vsoto števil, ki jih vrneta študenta pred njim.

def fibo(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fibo(n - 1) + fibo(n - 2)

Če je bila celotna vaja nepregledna in je morda pustila celo napačni vtis, da je rekurzija nekaj nerazumljivega, zapletenega, nesledljivega, pa mislim, da je vsaj ta ideja sprogramiraj, kako razmišljaš pravilna. Tako ali tako vedno, od prve ure, predavam programiranje kot formalno kodiranje postopkov, receptov, ki bi jih lahko izvajali tudi ročno.

Leta kasneje sem bral Paperta. Želva da je imenitna zato, ker se lahko otroci vživijo vanjo. Želva jim je blizu, ker bi lahko te stvari - obrni se levo, desno, pojdi naprej, nazaj - lahko počeli sami. Tudi pri Programiranju je zato po mojem dobro izhajati iz resničnega življenja, običajnega razmišljanja, iz tega, kar "že znajo".

Skladovnica stvari, ki jih moram še narediti

Potem so študenti dobili domačo nalogo. Morali so napisati funkcijo, ki kot argument prejme seznam, katerega elementi so seznami ali številke. Ti seznami lahko vsebujejo sezname ali številke... Njihova funkcija je morala vrniti vsoto vseh teh števil.

Moral sem jim povedati - česar sicer pri Programiranju 1 ne počnem - za funkcijo isinstance(obj, type), ki vrne True, če je obj objekt razreda type. Tako naj bi dobili nekaj v slogu

def vsota(s):
    v = 0
    for e in s:
        if isinstance(e, list):
            v += vsota(e)
        else:
            v += e
    return v

Zadnja leta se o izpeljanih seznamih in generatorjih učimo že precej prej, tako da bi lahko od boljših pričakoval tudi kaj v slogu

def vsota(s):
    return sum(vsota(e) if isinstance(e, list) else e
               for e in s)

Tisto leto sem bil tudi sam svoj (so)asistent, in tudi domače naloge sem popravljal. To je koristno, saj sem videl, kakšne težave imajo študenti. Bega jih, da ne vedo, kako bo računalnik to obvladal. To je, kako računalnik ve, kje je marker.

To je skladno z eno od hipotez o tem, zakaj se zdi rekurzija učencem težka. In, tako menijo nekateri, bi se dalo pomagati tako, da bi jim to mehaniko razložili. V to nisem tako prepričan: parkrat sem poskusil in ni pomagalo.

Morda bi jim to lahko pokazali z razhroščevalnikom. V resnici sem poskusil, a ne vem, ali je bilo kaj haska. Takrat sem jim sklad raje pokazal "v živo". Vzel sem nek seznam, na primer [3, [2, [1, 5], 2, [5]], [2, 1], 5] in ga napisal na papir, češ, tole moram sešteti. Odložil sem ga na mizo, na kup stvari, ki jih moram sešteti. Kup je takrat seveda vseboval samo ta list.

Nato sem s kupa vzel prvi list, ki ga moram sešteti. Pač ta list. Imel je štiri elemente, 3, [2, [1, 5], 2, [5]], [2, 1] in 5. Vsakega sem napisal na nov list, jih dal na mizo, prvi list pa vrgel proč.

Nato sem s kupa vzel prvi list. Ta je imel število 3, torej je moja vsota doslej enaka 3. List sem vrgel proč.

Nato sem vzel naslednji list. Ta je imel štiri elemnete, ki sem jih prepisal na štiri liste in dal na vrh kupa. In tako naprej.

Mislim, da so študenti tole dobro razumeli. Danes tudi vem, zakaj. Ker tako tudi sami razmišljajo. In posledično sprogramirajo tole:

v = 0
def vsota(s):
    global v
    for e in s:
        if isinstance(e, list):
            vsota(e)
        else:
            v += e
    return v

Seveda jim ne povem za globalne spremenljivke. Sami jih odkrijejo. No, včasih jim povem; naredim jim očetovski nagovor, da so zdaj dovolj stari, da jim lahko povem nekaj, za kar bi mi bilo ljubše, če izvejo od mene, ne od vrstnikov.

Tale program je v resnici točno to, kar sem izvajal ob svojem prekladanju listov. Takšna (jasno, nepravilna) rekurzija je študentom jasna. (Tudi, da njihova funkcija deluje, preskusijo, in potem se pritožujejo, da je nekaj narobe z mojimi testi, katerih greh pa je samo ta, da funkcije ne pokličejo samo enkrat. Ko to razčistimo, prestavijo v = 0 v funkcijo. Kar dela še slabše. Potem gre spet ven, v funkcijo pa dajo kakšno drugo čudno packarijo.)

Moja metafora z listi pravzaprav ni bil primer rekurzivne funkcije temveč bolj primer, "odpravljanja" rekurzijo tako, da sami skrbimo za sklad. Da je to kaj pomagalo pri razumevanju rekurzije, pa nisem prepričan.

Vrste in "repna rekurzija"

Naslednje leto smo poskusili nekaj bolj dramatičnega. V P1 (na Tržaški) sem ugasnil luči v predavalnici in si svetil s telefonom. Šel sem k študentu v prvi vrsti in mu povedal, da sedi v prvi vrsti. Je že vedel. Rekel sem mu, naj to pove vsakemu, ki bi ga vprašal. Nato sem šel po sredi predavalnice do študenta, ki je bil bolj nekje zadaj in ga vprašal, v kateri vrsti sedi. Seveda ni vedel. Rekel sem mu, naj si pomaga s študentom pred sabo. Po nekaj pogajanja, ga je vprašal, v kateri vrsti sedi. Ta ni vedel. In, če se prav spomnim, mu tudi ni prišlo na misel, da bi vprašal tistega pred sabo.

Vsaj navadno jim ne pride na misel. Zdaj pa se spomnimo urejanja plastenk. Kako, da otrokom pride na misel, študentom pa ne?

No, po še nekaj pogajanja smo pognali tole rekurzijo in odkrili, v kateri vrsti sedi ta študent. Potem smo sprogramirali funkcijo

def dolzina_seznama(s):
    if s == []:
        return 0
    else:
        return 1 + dolzina_seznama(s[1:])

Mislim, da so študenti lepo razumeli, kaj se dogaja. Vajo lahko obračaš na kup načinov. Koliko študentk je določeni vrsti? Vsak vpraša, koliko študentk je pred njim in k rezultatu prišteje 1 zase ali pa (običajno) ne. Kar je podobno, kot če bi se vprašali, koliko lihih števil vsebuje določen seznam.

def n_lihih(s):
    if s == []:
        return 0
    if s[0] % 2 == 1:
        return 1 + n_lihih(s[1:])
    else:
        return n_lihih(s[1:])

Ja, vem, vem.

def n_lihih(s):
    if s == []:
        return 0
    return s[0] % 2 == 1 + n_lihih(s[1:])

Ali pa, ker smo v Pythonu

def n_lihih(s):
    return s and s[0] % 2 == 1 + n_lihih(s[1:])

Ampak študente hočemo učiti, ne begati.

Ko smo dve uri takole telovadili, sam jih vprašal, če razumejo. Določil sem študenta, ki ne razume in potem vprašal prvega v vrsti, ali vsi v tej vrsti razumejo. Vsak je vprašal soseda, ali razume ... dokler nismo naleteli na tistega, ki ne. Ta je rekel, da ne, ne da bi spraševal naprej.

In potem smo sprogramirali funkcijo, ki vrne True, če v seznamu ni nobene ničle.

def razumejo(s):
    if s == []:
        return True
    if s[0] == 0:
        return False
    return razumejo(s[1:])

In v tem primeru (bomo videli, zakaj) bi bilo morda celo smiselno napisati

def razumejo(s):
    return s == [] or (s[0] != 0 and razumejo(s[1:]))

Šli smo celo tako daleč, da sem študenta vprašal, ali sedi v sodi vrsti in ta je (kakor katero leto) izvedel bodisi

def soda_dolzina(s):
    if s == []:
        return True
    else:
        return not soda_dolzina(s[1:])

ali, pogosteje

def soda_dolzina(s):
    if s == []:
        return True
    else:
        return liha_dolzina(s[1:])

def liha_dolzina(s):
    if s == []:
        return False
    else:
        return soda_dolzina(s[1:])

Šele leta kasneje sem začel v takih primerih pisati tudi krajšo različico; zakaj se mi zdi to dobra ideja, bom pokazal kasneje.

def soda_dolzina(s):
    return s == [] or not soda_dolzina(s[1:])

oziroma

def soda_dolzina(s):
    return s == [] or liha_dolzina(s[1:])

def liha_dolzina(s):
    return s != [] and soda_dolzina(s[1:])

Predvsem zadnji par se mi zdi lep.

Presenetilo me je, da študentov ta oblika rekurzije ni motila. Prav nič.

Tu prvič srečamo problem, kako postaviti pravo vprašanje. To je zanimivo, ker se problem pojavi tako v slovenščini kot v Pythonu. Študente moram prepričati, naj tistemu pred sabo postavijo takšno vprašanje, da ga bo lahko le-ta nespremenjenega postavil tistemu pred sabo. Izjema so sodi-lihi, kjer se izmenjujeta dve vprašanji, ali pa morebitni "argumenti" vprašanja (ekvivalenti argumentov funkcije). Drugi problem je, kako pretvoriti rezultat, ki smo ga dobili v rezultat, ki ga moramo vrniti. Tudi s tem imamo težave tako v slovenščini kot pri programiranju. A o tem več kasneje.

Tole reč sem počel par let. Zaradi teme v predavalnici je bila vaja dramatična, študentom je bilo všeč, pa tudi funkcije so dobro razumeli. Kako uspešno so reševali naloge, se ne spomnim.

Vendar ima tale reč dva problema.

1. Kolega Slivnik mi je potožil (in upam, da ne tudi verjel), da mu študenti pravijo, da sem rekel, da se rekurzija ne uporablja, ker je počasna. Predpostavljam, da sem jim rekel, da so gornje funkcije počasnejše, kot če bi napisali običajno zanko. To je dejstvo: klic funkcije je počasnejši od skoka. (Kar še bolj boli, če jezik/prevajalnik/interpreter, ki ga uporabljamo, ne ve za repno rekurzijo.) Najbrž jim nisem omenil še tega, da imajo tile programi linearno pomnilniško zahtevnost.

2. Vsa ta telovadba z vrstami vodi v repno rekurzijo ali, vsaj, rekurzijo, kjer imamo v funkciji le en rekurzivni klic. Če učimo le rekurzivne funkcije v tej obliki, bodo imeli študenti težave, ko bodo hoteli prehoditi kako drevo.

Če me drugo pri Programiranju 1 morda še niti ne bi toliko motilo: moti me prvo. Kadar učim, študente ali osnovnošolce, hočem, da je stvar motivirana. Z mojim hišnim petošolcem sva se igrala z matriko z 8x8 LED, ki sva jo priključila na Arduina in krmilila premikanje ene pike po zaslonu. Hotel je narediti kačo (igro Snake). Hitro je odkril, da bo moral brisati rep, torej bo moral poznati vse točke, kjer je trenutno kača. Povedal je, da bo s petimi spremenljivkami kača lahko dolga največ 5 (in potem enako hitro ugotovil, da jih bo potreboval 10, ker ima dva koordinati). Ko sem ga vprašal, kako bo to rešil, je povedal, da s seznami. Skratka, motivacija za seznam mora biti kača. Motivacija za slovar ... preštevanje frekvenc črk v besedilu. Motivacija za objekte je lahko, da hočemo sprogramirati želvo in to tako, da bomo lahko imeli tudi več želv.

Kaj pa je tule motivacija za rekurzijo? Vse to se da preprosteje rešiti s čisto običajno zanko. No, morda je za nas rekurzija enako preprosta kot zanka, zanje pa ne. Tudi za odraslega je hoja bolj preprosta od kobacanja po vseh štirih, vendar vedo razvojni psihologi povedati, da kobacač ne bo zamenjal kobacanja za (nevarno) hojo, dokler ne bo videl dobrega razloga za to. In kakšen dober razlog za rekurzijo imamo, če hočemo ugotoviti, ali seznam vsebuje kako ničlo? Ne rečem, v Lispu ali Prologu, ampak Python ima tako indekse kot "pravo" zanko for (ne C-jevske).

Malo teorije? Nekateri pravijo, da bi bilo potrebno rekurzijo učiti v funkcijskih jezikih. O tem bi lahko razpravljali toliko časa kot o tem, kateri jezik uporabljati za Programiranje 1. Zakaj? Zato, ker naj bi bila ta v funkcijskih jezikih naravna.

Zakaj sem pisal one enovrstične funkcije zgoraj? Zato, ker bi natančno tako te stvari zapisali v funkcijskih jezikih. In ko bi prišli do malenkost težjih problemov, bi bila rekurzivna formulacija v funkcijskem jeziku morda lepša, saj so pač narejeni za takšne formulacije.

Z nalogami, v kakršne vodi to skakanje po predavalnici, torej Python v nekem smislu uporabljamo kot funkcijski jezik. Vse skupaj torej ni čisto zgrešeno.

Drevo rodbine

Iskal sem torej primer, ko bi bila rekurzija

• naravna v tem smislu, da je ne bi vsilili z nekimi umetnimi omejitvami (ugotovi dolžino seznama, ne da bi poklical len ali uporabil zanko),
• naravna v smislu, da gre za primer iz vsakdanjega življenja, ki je vsem jasen in ga lahko odigrajo,
• nekako neizogibna, tako da bi bila nerekurzivna rešitev težka. Lep primer bi bilo hitro urejanje, vendar je prezapleteno.

Tako sem prišel do celjskih grofov (prave rodbine, prvo leto) oziroma rodbine Novakovih, ker je bilo pri celjskih grofih preveč enakih imen.

Študentom po predavalnici naključno razdelim liste z imeni in imeni njihovih otrok. Gornjega drevesa pa jim še ne pokažem.

Pazim le, da je Elizabeta vedno kak študent, po možnosti z basom. Študije kažejo, da si študenti zapomnijo več, kadar se ne dolgočasijo.

Zdaj vprašam nekoga, recimo Elizabeto, koliko otrok ima. Pove, da tri. Potem jo vprašam, koliko vnukov ima. Tega ne ve, vendar se znajde in vpraša svoje otroke, koliko otrok imajo.

V tem trenutku jim pokažem slovar, v katerem je zapisana rodbina

rodbina = {
    "Adam": ["Matjaz", "Cilka", "Daniel", "Erik"],
    "Cilka": [],
    "Daniel": ["Elizabeta", "Hans"],
    "Erik": [],
    "Elizabeta": ["Ludvik", "Jurij", "Barbara", "Herman"],
... in tako naprej

Sprogramiramo

def otroci(oseba):
    return rodbina[oseba]

def n_otrok(oseba):
    return len(otroci(oseba))

def n_vnukov(oseba):
    vnukov = 0
    for otrok in otroci(oseba):
        vnukov += n_otrok(otrok)
    return vnukov

Tu se navadno izognem bližnjicam, kot je

def n_vnukov(oseba):
    return sum(n_otrok(otrok) for otrok in otroci(oseba))

ker imajo študenti dovolj težav z rekurzijo in ni treba, da jim hkrati obremenjujem misli še z generatorji.

Naslednje vprašanje pa je: Elizabeta, ki je stara 67, bo praznovala 68 rojstni dan in bo povabila vse svoje otroke, vnuke, pravnuke in tako naprej, pa še sebe zraven, na kosilo. Koliko krožnikov bo potrebovala?

Študenti tu še ne vidijo celega rodbinskega drevesa. Navadno najprej nekaj poskušajo s "koliko vnukov imaš", ne znajo pa oblikovati pametnega, splošnega vprašanja in strategije spraševanja. Zato je tu pravi trenutek, da se zmenimo za pravila - ko te nekaj vprašajo, odgovoriš tistemu, ki te sprašuje, in tisti, ki sprašuje, sliši le tebe. (Po naše: ni globalnih spremenljivk, vsi podatki se prenašajo le kot argumenti funkcij in kot rezultat. Da je rodbina globalna spremenljivka, ni tako pomembno in zamolčimo. Če bi jo prenašali kot argument, bi zapletli funkcije, ne da bi bilo to posebej poučno.) - če moraš za to, da boš odgovoril, koga kaj vprašati, ga vprašaš ... vendar poveš koga, tako da pokličeš njegovo ime, predvsem pa sprašuješ le enega naenkrat. (Po naše: ni paralelnosti. To ni map-reduce. :))

Lani smo uvedli še eno dodatno pravilo: ko te kdo kdaj vpraša, vstaneš in stojiš, dokler ne odgovoriš.

• Če koga kaj vprašaš, kažeš s prstom nanj, dokler ti ne odgovori. (Po naše: v predavalnici vidimo celoten sklad, le da prsti kažejo v napačno smer.)

Moje prvotno vprašanje, koliko krožnikov potrebujete, je neuporabno, ker Elizabeta ne more zastaviti istega vprašanja svojim otrokom. Zato ga navadno ponovim, a v drugi obliki: kako velika je vaša rodbina. To je veliko boljše, saj lahko Elizabeta postavi natančno enako vprašanje otrokeom in ti svojim otrokom.

Ko odkrijemo velikost rodbine, sprogramiramo recept, ki se dogaja v glavi.

def velikost_rodbine(oseba):
    n = 0
    for otrok in otroci[oseba]:
        n += velikost_rodbine(otrok)
    return n + 1

Vem, enico bi lahko prišteli že v začetku. Vendar jo študenti, ko se gredo to v predavalnici, šele na koncu, zato tako tudi sprogramiramo.

Nadaljujemo z iskanjem osebe v rodbini: Adam, je v tvoji rodbini kak Jožef?

def obstaja(oseba, ime):
    if oseba == ime:
        return True
    for otrok in otroci(oseba):
        if obstaja(otrok, ime):
            return True
    return False

Kakšno je največje število potomcev?

Zanimivo je, da je naloga "sestavi množico imen članov svoje rodbine" za študente bistveno težja od preštevanja rodbine, čeprav gre za isti problem.

def rodbina(oseba):
    s = {oseba}
    for otrok in otroci[oseba]:
        s |= rodbina(otrok)
    return s

Takšnih nalog si lahko izmislim(o), kolikor si hočem(o). Poskusimo lahko tudi težje različice, na primer, kakšno je ime osebe z največ potomci.

Vse to je jako zabavno. Vsaj bilo je, do letos. Študentom je bilo morda tudi letos še čisto zabavno, meni pa ne, ker se mi spet porajajo dvomi. :) Tole je res rekurzija, ki je naravna, tako kot pri hitrem urejanju. Drevo je rekurzivna zadeva in rodbinsko drevo je drevo, ki smo ga vajeni. Brez rekurzije bi bilo vse tole -- za razliko od vsote -- bistveno težje sprogramirati. Vsaj brucom. Ampak...

Kaj o tem pravi teorija? Andrej (Brodnik) vedno in povsem pravilno ponavlja, da govorimo o algoritmih in podatkovnih strukturah zato, ker je najprej algoritem in šele potem podatkovna struktura. Ko vem, s kakšnim postopkom bom nekaj rešil, razmislim o tem, kakšno podatkovno strukturo potrebujem. Tole je po svoje ekvivalentno, samo na drug način: vem, da hočem učiti rekurzijo in razmislim, na kakšni podatkovni strukturi bi to počel. No, nekateri, ki razmišljajo o poučevanju rekruzije, pravijo, da bi jo bilo najboljše učiti na rekurzivnih podatkovnih strukturah. Tule je to očitno (in z vidika učenca nasprotno od prej citiranega Andreja): tu jih podatkovna struktura prisili v rekurzijo.

Tole je sinteza vsega, kar je bilo doslej dobro: Rodbino Novakovih lahko odigramo, je domača, je po naravi rekurzivna... Vse je odlično, le...

Vračanje rezultata

... ali si učence naučil, najbolj vidiš po tem, ali ti po tem, ko si jih učil kaj znajo. :) Žal bi velikost rodbine (oziroma kako podobno nalogo, ki jim jo dam kasneje) tipično sprogramirali tako

def velikost_rodbine(oseba):
    velikost += 1
    for otrok in otroci(oseba):
        velikost_rodbine(otrok)
    return velikost

Ker to ne dela (velikost ni definirana), poskusijo

def velikost_rodbine(oseba):
    velikost = 0
    velikost += 1
    for otrok in otroci(oseba):
        velikost_rodbine(otrok)
    return velikost

in se čudijo, zakaj jim vrne 1. Ko to odkrijejo, poskusijo

velikost = 0

def velikost_rodbine(oseba):
    velikost += 1
    for otrok in otroci(oseba):
        velikost_rodbine(otrok)
    return velikost

Pythonovi imenski prostori delujejo tako, da funkcija vsako spremenljivko, ki ji prireja vrednost, obravnava kot lokalno, razen če jo eksplicitno deklariramo kot globalno. Zato to spet javi, da velikost ni definirana. Ker so študenti iznajdljivi, kadar ni treba, odkrijejo

velikost = 0

def velikost_rodbine(oseba):
    global velikost
    velikost += 1
    for otrok in otroci(oseba):
        velikost_rodbine(otrok)
    return velikost

in se čudijo, zakaj ta funkcija preživi njihov poskusni klic, ne pa mojih testov, ki to funkcijo pokličejo večkrat.

Ker nisem več sam svoj asistent, tega miselnega procesa ne vidim na vajah, pač pa po mailih. Prepričati jih poskušam, da njihova funkcija kliče funkcijo velikost_rodbine, vendar rezultat tega klica vrže stran. In to najbrž ni dobro.

Tole kaže na globji problem. In splošnejši. Ko študenti programirajo rekurzijo, ne uporabijo rezultata rekurzivnega klica. Lahko potem res rečemo, da vedo, kaj delajo? Mar ni bistvo rekurzivne definicije prav v tem, da je vrednost funkcije definirana z vrednostjo taiste funkcije pri nekih drugih argumentih? To, kar počnejo tule, pa je uporaba rekurzije za to, da prehodijo celotno drevo. To je rekurzija v smislu klicanja, ne pa v smislu rekurzivne formule.

Rekurzivne definicije

Obstaja domneva, po kateri se študenti rekurzije bojijo, ker ne vejo, kako bo računalnik to v resnici izračunal. Zato si preprosto ne upajo napisati rekurzivnega klica.

Morda, nekateri. Vendar to, da jim pokažeš sklad - to sem počel predvsem v drugem letniku na PeF, pri čemer smo si par predavanj prej dejansko ogledali, kako deluje Pythonov sklad - ne pomaga.

Zanimivo je, recimo, da so mi povedali, da jih moti, če funkcija kliče samo sebe, ne moti pa jih, če se dve funkciji kličeta med sabo (kot sodi in lihi). To že kaže na to, da jih begajo "tehnikalije". Na PeF smo letos delali nekaj takega

def vsota(s):
    if s == []:
        return 0
    else:
        return s[0] + vsota1(s)

def vsota1(s):
    if s == []:
        return 0
    else:
        return s[0] + vsota2(s)

def vsota2(s):
    if s == []:
        return 0
    else:
        return s[0] + vsota3(s)

def vsota3(s):
    if s == []:
        return 0
    else:
        return s[0] + vsota4(s)

In potem sem jim obljubil, da je Python dovolj pameten, da to naredi tudi sam od sebe. Percepcija rekurzije kot klicev kopij funkcij je operativno veljavna, čeprav praktično ne deluje tako.

(Ko sem pisal tole, sem v resnici celo že vedel nekaj o teoriji. Obstajajo različne zmotne mentalne predstave rekurzije, in ena, ki je zmotna, vendar uporabna in deluje, namreč ta, da imamo več kopij funkcije.)

So torej problem tehnikalije? Strah, kako bo to delovalo? Imam protiprimer. Medtem ko sem na FRI pridno delal z Novakovimi, sem se na PeF iz neznanega razloga igral tudi z rekurzivnimi definicijami. Rekli smo, na primer, da je palindrom beseda, ki je dolga kvečjemu en znak, ali pa je pri kateri je prva črka enaka zadnji, vse vmes pa je palindrom. Če to definicijo prevedemo v Python, dobimo

def palindrom(s):
    return len(s) <= 1 or s[0] == s[-1] and palindrom(s[1:-1])

Kadarkoli sem dal takšno nalogo na izpit - in zraven napisal rekurzivno definicijo v slovenščini - so jo študenti brez težav rešili. Če jim povem, da je seznam brez ničel, če je prazen ali pa prvi element ni nič in ostanek ne vsebuje ničel, bodo brez težav napisali

def ni_nicel(s):
    return s == [] or s[0] != 0 and ni_nicel(s[1:])

Če bi se študenti v resnici bali rekurzije, češ, kako bo računalnik to zmogel, ne bi tako suvereno reševali teh nalog.

Morda pa je problem v tem, da študenti v resnici ne znajo oblikovati rekurzivne definicije? Učiti na Pedagoški fakulteti je zelo drugačna izkušnja kot na FRI. Eno je, da -- v nasprotju s tem, kar menijo nekateri na FRI -- ni isto, če predavaš 200 ali 20 študentom. Poleg tega pa so na PeF vseeno prihodnji učitelji in znajo opazovati in reči stvari, ki jih FRIjevci ne znajo.

Tako so mi enkrat čisto lepo povedali, da vidijo, da včasih dam v izpit rekurzivno definicijo, ki jo morajo samo prevesti v Python, in to znajo. Če besedilo naloge ni dovolj "rekurzivno", pa tega ne bodo znali sprogramirati.

Sami so mi torej povedali, da problem ni programerski, temveč konceptualni? Hm, vendar, niso otroci razumeli koncepta rekurzije (samo ponoviš oboje), ne bi pa znali sprogramirati?

Gotovo poenostavljam, saj gre za različno težke in predvsem različno vsakdanje probleme. Urejanje plastenk po velikosti je bolj vsakdanji in manj za lase priblečen problem kot iskanje ničel v seznamu. A vseeno: reč je očitno bolj zapletena in ima več kamnov spotike.

Leni študent

Tale pristop sem prvič poskusil lani na Pedagoški in se je tako dobro obnesel, da sem letos tako začel tudi na FRI.

Uvod v rekurzijo sem začel tako, da sem povedal, da je moral nek len študent napisati funkcijo, ki izračuna vsoto števil v seznamu. Ker je bil len, je napisal kar

def vsota(s):
    return s[0]

To je delovalo za nekatere sezname. Že pri seznamu dolžine 0 je imel težavo, zato je funkcijo dopolnil

def vsota(s):
    if s == []:
        return 0
    else:
        return s[0]

Profesor, ga je spodbujal, da bi tole izboljšal tako, da bi delovalo tudi za sezname, ki imajo več kot en element. Študent, len kot fuks, je naumil, da vsoto elementov v seznamu dobimo tako, da k prvemu elementu prištejemo vsoto ostalih.

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

Tole sem napisal, ne pa pognal. Vprašal sem študente, ali bo delovalo in nekdo je suvereno povedal, da ne. Ko sem vprašal, zakaj ne, je povedal, da zato, ker je to predobro, da bi delovalo. In sem rekel, da bi ga kar objel. (To je bil running joke tistega leta, ker sem dva tedna prej isto rekel eni študentki, ki je zinila nekaj pametnega, pa je tako zafarbala, da me je bilo kar strah zanjo.)

Skratka, rekurzija je predobra, da bi delovala. Potem sem pokazal, da je predobra, ampak ne toliko, da ne bi delovala.

Ta izjava mi je dala navdih za način, kako razlagati rekurzijo. Za malo drugačen pogled na to, kaj rekurzija pravzaprav je. Vsaj s tega vidika, kaj hočem prodati študentom. Rekurzija je nekaj, s čimer se lahko izogibaš delu. Narediš en sam korak, ostale korake pa prepustiš nadaljevanju.

To v resnici sploh ni prav nič daleč od neke bolj teoretične - matematične ali računalniške - definicije rekurzije. Namesto da bi rešili problem, ga prevedemo na enega ali več istovrstnih, a preprostejših (v smislu razdalje od rešitve) problemov. "Novost" je samo, da sem to predstavil z vabljivo zgodbo o študentu, ki se izogiba delu.

In potem smo pisali vse mogoče naloge z repno (ali kvazi-repno) rekurzijo, pri čemer smo vedno uporabljali metaforo lenega študenta. Leni študent preverja "palindromskost" tako, da primerja prvi in zadnji element, tisto vmes pa mora biti palindrom.

Vem, da gre le za igro besed. A če uvedemo lenega študenta so rekurzivne definicije naenkrat

• zabavne, ker je pač zabavno peniti čez lenega študenta,
• nekako motivirane, in to čisto smiselno, saj je ideja lenega študenta prav v tem, da bi naredil tisti minimalni korak, ki ga mora, ostanek (malenkost zmanjšanega problema), pa se bo rešil sam,
• in, najpomembneje, rešijo problem vračanja rezultata, saj rekurzivna definicija, ki jo izusti leni študent, operira z rezultatom.

Do sem sem torej prišel letos. Tudi na FRI sem najprej govoril o lenem študentu, v naslednjem predavanju pa smo se šli Novakove. In tudi pri Novakovih lahko govorimo o leni Elizabeti. Namesto da bi sama ugotavljala, koliko potomcev ima, prepusti delo svojim otrokom. Ti pa podedujejo njeno lenobo in prepustijo delo svojim otrokom.

Stvar razsvetljenja

Enkrat sem se na Pedagoški fakulteti zaplezal v neko drevje. Kaj, točno, sem razlagal, ne vem, ampak končalo se je tako, da sem na tablo risal drevo in se šel rekurzijo po njem, ne da bi po tem obstajala resna potreba, saj tema predavanj sploh ni bila rekurzija. Ker je Churchill rekel "Ko hodiš skozi pekel, pojdi naprej", sem pač šel naprej in se spraševal, kaj delam tem študentom. Ampak potem me je en študent naenkrat prekinil in rekel "Ah, zdaj pa razumem rekurzijo."

Mogoče je vsa teorija odveč in moramo študentom pač povedati eno in isto na sto in en način. Vsak bo doživel razsvetljenje - ali pa tudi ne - ob čem drugem.