Tole je običajen način poučevanja rekurzije. Strinjam se z argumenti, zakaj je zgrešen. Vendar sem pogosto naletel na študente, ki jim je bilo tole lažje kot karkoli drugega. Zategadelj poskušam tudi tako; nekateri doživijo razsvetljenje po tej poti.
Niz je palindrom, če se naprej in nazaj bere enako.
Očitno obstaja kup načinov, da preverimo, ali je niz palindrom.
Najlažji v Pythonu je, da ga pač obrnemo in pogledamo, ali ostane pri
tem enak, s[::-1] == s
.
Vendar nas danes zanima rekurzivna rešitev. Zato se moramo najprej domisliti rekurzivne definicije palindroma: niz je palindrom, če sta prvi in zadnji znak enaka, vse, kar je vmes, pa je palindrom. Obenem moramo pristaviti, da so tudi prazni nizi palindromi.
Kar smo napisali, "niz je palindrom, če je prazen ali pa je prvi znak enak zadnjemu in je vse, kar je vmes palindrom" dobesedno prevedemo v Python.
def palindrom(s):
return s == "" or s[0] == s[-1] and palindrom(s[1:-1])
"pericarežeracirep") palindrom(
True
"abcba") palindrom(
True
"abccba") palindrom(
True
"abcdba") palindrom(
False
Študente tole pogosto zbega. Funkcija palindrom
je
definirana s funkcijo palindrom
. Sama s sabo. Je to sploh
dovoljeno? Deluje?
Če bi napisali
def palindrom(s):
return palindrom(s)
to seveda ne bi delovalo. Razlog, da gornje deluje, pa je v tem da je niz vedno krajši.
"abccba"
palindrom, funkcija
ugotovi, da sta prvi in zadnji znak enaka in pokliče neko funkcijo, ki
bo preverila, ali je "bccb"
palindrom. Ta "neka funkcija"
je slučajno ravno taista funkcija, a s tem ni nič narobe."bccb
palindrom, ugotovi, da sta prvi in zadnji znak enaka, nato pa pokliče
neko funkcijo, ki bo preverila, ali je "cc"
palindrom."cc"
palindrom, ugotovi, da sta prvi in zadnji znak enaka, nato pa pokliče
neko funkcijo, ki bo preverila, ali je ""
palindrom.""
palindrom, odgovori, da je.Kako Python zmore slediti temu? Kako se ne zgubi v tem, do kje je prišel, kaj preverja, kaj bo rezultat tega preverjanja? To naj vas ne skrbi. Zna pač. Da bi razložili, moramo vedeti več, kot bomo izvedeli pri tem predmetu.
Funkcijam, ki kličejo same sebe, rečemo "rekurzivne funkcije".
Kako bi izračunali vsoto elementov seznama. Z zanko seveda znamo. Pa poskusimo še s trikom, kakršnega smo uporabili zgoraj. Za to spet potrebujemo rekurzivno definicijo vsote seznama - definicijo, ki se nanaša sama nase.
Takole lahko rečemo: vsoto elementov seznama dobimo tako, da k prvemu elementu prištejemo vsoto ostalih. Če je seznam prazen, pa je vsota 0.
def vsota(s):
if not s:
return 0
return s[0] + vsota(s[1:])
5, 8, 2]) vsota([
15
Seznam vsebuje sama soda števila, če je prazen ali pa je prvi element sod in vsebuje preostanek seznama sama soda števila.
def soda(s):
return not s or s[0] % 2 == 0 and soda(s[1:])
4, 8, 6, 1, 2, 4]) soda([
False
4, 8, 6, 2, 4]) soda([
True
Napisati želimo funkcijo, ki vrne vsoto vseh sodih elementov v podanem seznamu.
Recimo tako:
def vsota_sodih(s):
if not s:
return 0
if s[0] % 2 == 0:
return s[0] + vsota_sodih(s[1:])
else:
return vsota_sodih(s[1:])
4, 2, 5, 11, 6]) vsota_sodih([
12
Napisati želimo funkcijo, ki vrne prvi sodi element seznama.
Če je ničti element sod, vrnemo tega. Sicer vrnemo prvega sodega med ostalimi.
def prvi_sodi(s):
if s[0] % 2 == 0:
return s[0]
else:
return prvi_sodi(s[1:])
5, 11, 3, 4, 8, 7, 12]) prvi_sodi([
4
Ta funkcija ima manjšo težavo, kadar v seznamu ni nobenega sodega
elementa. Ker prvi ni sod, išče sodega v preostanku. Ker prvi iz
preostanka ni sod, išče sodega v preostanku. Ker prvi v tem preostanku
ni sod ... in tako naprej, dokler ne pride do praznega seznama. Takrat
bomo v prvi vrstici funkcije spraševali po prvem (no, ničtem) elementu,
s[0]
in Python bo javil napako,
Index out of range
.
Recimo, da naj funkcija v takšnem primeru vrne None
.
def prvi_sodi(s):
if not s:
return None
if s[0] % 2 == 0:
return s[0]
else:
return prvi_sodi(s[1:])
Bolj zanimiva naloga je poiskati zadnji sodi element seznama. (Seveda, če se dogovorimo, da bomo spet gledali prvi element in ostanek; če smemo iti od zadnjega elementa proti začetku, je to seveda natančno enaka naloga kot prejšnja, spremené se le indeksi.)
Tako razmišljamo.
None
, itak.None
,
je to pač zadnji element seznama.None
, pa v ostanku ni sodih
elementov. Preverimo, ali je prvi element sod; če je tako, je to tudi
zadnji sodi element in ga moramo vrniti.None
.def zadnji_sodi(s):
if s == []:
return None
= zadnji_sodi(s[1:])
zadnji if zadnji is not None:
return zadnji
if s[0] % 2 == 0:
return s[0]
return None
1, 3, 5, 4, 7, 3, 12, 8, 1, 3]) zadnji_sodi([
8
Funkcija, ki vrne vse sode elemente seznama je železna klasika napačnih rešitev. Tipični prvi poskus je
def vsi_sodi(s):
if s == []:
return []
= []
t if s[0] % 2 == 0:
0])
t.append(s[1:])
vsi_sodi(s[return t
4, 2, 5, 11, 6]) vsi_sodi([
[4]
To ne deluje, ker vsaka funkcija naredi svoj seznam t
,
vanj doda en sem element in ga vrne. Na koncu dobimo le seznam, ki ga
ustvari najbolj zunanja funkcija.
V drugem poskusu poskusimo zagotoviti, da bodo vse funkcije
uporabljale isti t
tako, da ga postavimo pred funkcijo -
tako da postane globalna spremenljivka.
= []
t
def vsi_sodi(s):
if s == []:
return []
if s[0] % 2 == 0:
0])
t.append(s[1:])
vsi_sodi(s[return t
To deluje - vendar le enkrat. Če tole poskusimo poklicati večkrat, bo funkcija vedno dodajale elemente v ta seznam - in to ne bo dobro.
4, 2, 5, 11, 6]) vsi_sodi([
[4, 2, 6]
4, 2, 5, 11, 6]) vsi_sodi([
[4, 2, 6, 4, 2, 6]
4, 2, 5, 11, 6]) vsi_sodi([
[4, 2, 6, 4, 2, 6, 4, 2, 6]
To lahko poskušamo rešiti na vse žive načine. Recimo tako, da seznam praznimo na začetku funkcije.
= []
t
def vsi_sodi(s):
t.clear()
if s == []:
return t
if s[0] % 2 == 0:
0])
t.append(s[1:])
vsi_sodi(s[return t
4, 2, 5, 11, 6]) vsi_sodi([
[]
To ne deluje, ker se seznam sprazni ob vsakem klicu. Obupani študenti potem pišejo maile, kako narediti, da se bo seznam spraznil samo prvič.
Ne gre. Tu ni problem v tem, da ne znamo prav sprogramirati, temveč v tem, da narobe razmišljamo. Kakšna je rekurzivna definicija vseh sodih elementov seznama? To je seznam, ki vsebuje prvi element, če je le-ta sod, poleg tega pa vse sode elemente iz ostanka. Recimo tako:
def vsi_sodi(s): if s == []: return []
if s[0] % 2 == 0:
return [s[0]] + vsi_sodi(s[1:])
else:
return vsi_sodi(s[1:])
Obstajajo tudi elegantnejši načini, obstajajo tudi hitrejši načini. A za nas je tale dovolj dober.
Seznam je sodolih, če se v njem izmenjujejo sodi in lihi elementi, začenši s sodim.
Seznam je lihosod, če se v njem izmenjujejo lihi in sodi elementi, začenši z lihim.
Napisati moramo funkciji sodolih
in
lihosod
, ki preverita, ali je seznam tak, kot pravi ime
funkcije.
def sodolih(s):
return s == [] or s[0] % 2 == 0 and lihosod(s[1:])
def lihosod(s):
return s == [] or s[0] % 2 == 1 and sodolih(s[1:])
4, 5, 8, 13, 2, 7, 0]) sodolih([
True
Tu vidimo primer, ko se dve funkciji kličeta med sabo. Tudi to je rekurzija in tudi za takšno obliko ni razloga, da ne bi delovala.