1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
|
<!DOCTYPE html>
<html lang="sl">
<head>
<meta charset="utf-8" />
<title></title>
<link rel="stylesheet" type="text/css" href="/css/codeq.css" />
<link rel="stylesheet" type="text/css" href="../../style.css" />
</head>
<body>
<h1>Rekurzija na primeru družinskega drevesa </h1>
<p>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 namreč preselil v predmestje Graza, kjer ima
manjše podjetje), Cilka in Erik pa nimata otrok. In tako naprej. Vse skupaj je
nabrano v spodnjem slovarju.</p>
<pre>
otroci = {
"Adam": ["Matjaž", "Cilka", "Daniel", "Erik"],
"Aleksander": [],
"Alenka": [],
"Barbara": [],
"Cilka": [],
"Daniel": ["Elizabeta", "Hans"],
"Erik": [],
"Elizabeta": ["Ludvik", "Jurij", "Barbara", "Herman", "Mihael"],
"Franc": [],
"Herman": ["Margareta"],
"Hans": [],
"Jožef": ["Alenka", "Aleksander", "Petra"],
"Jurij": ["Franc", "Jožef"],
"Ludvik": [],
"Margareta": [],
"Matjaž": ["Viljem"],
"Mihael": [],
"Petra": [],
"Tadeja": [],
"Viljem": ["Tadeja"],
}
</pre>
<p>Znane so tudi starosti vseh teh ljudi.</p>
<pre>
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}
</pre>
<p>Napišimo, takole, za preprosto vajo, funkcijo, ki ji podamo osebo in pove,
koliko otrok ima.</p>
<pre>
def stevilo_otrok(oseba):
return len(otroci[oseba])
</pre>
<p>Če pokličemo, recimo, `stevilo_otrok("Adam")`, dobimo 4.</p>
<p>Kako pa bi izvemo število vnukov posamezne osebe? Tako da gremo prek vseh
otrok in seštevamo število njihovih otrok, recimo z</p>
<pre>
def stevilo_vnukov(oseba):
v = 0
for otrok in otroci[oseba]:
v += len(otroci[otrok])
return v
</pre>
<p>ali, brez velike razlike,</p>
<pre>
def stevilo_vnukov(oseba):
v = 0
for otrok in otroci[oseba]:
v += stevilo_otrok(otrok)
return v
</pre>
<p>Uh, kaj kompliciramo, saj že znamo</p>
<pre>
def stevilo_vnukov(oseba):
return sum(stevilo_otrok(otrok) for otrok in otroci[oseba])
</pre>
<h2> Velikost rodbine </h2>
<p>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. </p>
<p> 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. </p>
<p>Spremenimo to v funkcijo. Velikost rodbine dobimo tako, da gremo prek otrok
in seštevamo velikosti njihovih rodbin.</p>
<pre>
def velikost_rodbine(oseba):
v = 0
for otrok in otroci[oseba]:
v += velikost_rodbine(otrok)
return v + 1
</pre>
<p>Za tiste, ki so se dobro naučili prejšnjo snov:</p>
<pre>
def velikost_rodbine(oseba):
return sum(velikost_rodbine(otrok) for otrok in otroci[oseba]) + 1
</pre>
<h2> Poišči osebo </h2>
<p>Potem nas je zanimalo, 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 <code>True</code>. Sicer bo enega za drugim spraševala
otroke, dokler prvi ne odgovori <code>True</code>; tedaj vrnemo
<code>True</code>. Če noben otrok nima takšnega potomca - in torej noben otrok
ne odgovori <code>True</code>, odgovorimo <code>False</code>. Z drugimi
besedami,</p>
<pre>
def obstaja_ime(oseba, ime):
if oseba == ime:
return True
for otrok in otroci[oseba]:
if obstaja_ime(otrok, ime):
return True
return False
</pre>
<p>S snovjo izpred dveh tednov:</p>
<pre>
def obstaja_ime(oseba, ime):
return oseba == ime or any(obstaja_ime(otrok, ime) for otrok in otroci[oseba])
</pre>
<h2> Največja družina </h2>
<p>Kako velika je največja družina v rodbini neke osebe - s temi 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.</p>
<pre>
def najvec_otrok(oseba):
najvec = len(otroci[oseba])
for otrok in otroci[oseba]:
koliko = najvec_otrok(otrok)
if koliko > najvec:
najvec = koliko
return najvec
</pre>
<p>Kdor zna, zna takole:</p>
<pre>
def najvec_otrok(oseba):
return max([len(otroci[oseba])] + [najvec_otrok(otrok) for otrok in otroci[oseba]])
</pre>
<p>Študenti pogosto zagrešijo tole precej napačno rešitev:</p>
<pre>
def najvec_otrok(oseba):
najvec = len(otroci[oseba])
for otrok in otroci[oseba]:
if najvec_otrok(otrok) > najvec:
najvec = najvec_otrok(otrok)
return najvec
</pre>
<p>Tu vsaka oseba večkrat vpraša svoje otroke, kako velike so največje družine.
Vsaj tistega z največjo družino vpraša dvakrat. Doslej smo takšno programiranje
tolerirali (in le občasno postokali, da to ni najlepše). Tu ga ne moremo več.
Vsak od teh, ki so bili po nepotrebnem vprašani dvakrat, spet dvakrat vpraša
svoje otroke vpraša po dvakrat, torej se v bistvu vprašajo po štirikrat. Oni
spodaj so vprašani že po osemkrat. Pri tako majhnih drevesih to ni tako hudo.
Pri velikih pa si tega ne bi mogli privoščiti.</p>
<h2> Najdaljše ime v rodbini </h2>
<p>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.</p>
<pre>
def najdaljse_ime(oseba):
najdaljse = oseba
for otrok in otroci[oseba]:
naj_pod = najdaljse_ime(otrok)
if len(naj_pod) > len(najdaljse):
najdaljse = naj_pod
return najdaljse
</pre>
<h2> Globina rodbine </h2>
<p>Kako globoka je rodbina določene osebe? Torej, nekdo, ki nima otrok, ima
rodbino globinee 1. Če ima otroke, nima pa vnukov, ima rodbino globine
2. Če ima tudi kakega vnuka, vendar nobenega pravnuka, ima rodbino globine 3.</p>
<p>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.</p>
<pre>
def globina(oseba):
najvecja = 0
for otrok in otroci[oseba]:
g = globina(otrok)
if g > najvecja:
najvecja = g
return najvecja + 1
</pre>
<p>Ali, krajše</p>
<pre>
def globina(oseba):
return max(globina(otrok) for otrok in otroci[oseba]) + 1
</pre>
<h2> Velikost potomstva </h2>
<p>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).</p>
<p>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.</p>
<pre>
def velikost_rodbine(oseba):
v = 0
for otrok in otroci[oseba]:
v += velikost_rodbine(otrok)
return v
</pre>
<p>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š. </p>
<p>Ena rešitev je, da vsak vrne število svojih otrok, ki čemur morajo otroci
prišteti število svojih otrok, in vnuki število svojih...</p>
<pre>
def stevilo_potomcev(oseba):
potomcev = len(otroci[otroci])
for otrok in otroci[oseba]:
potomcev += stevilo_potomcev(otrok)
return potomcev
</pre>
<p>Ali isto, le na drug način:</p>
<pre>
def stevilo_potomcev(oseba):
potomcev = 0
for otrok in otroci[oseba]:
potomcev += 1 + stevilo_potomcev(otrok)
return potomcev
</pre>
<p>Lahko pa si pomagamo tudi z rodbino:</p>
<pre>
def stevilo_potomcev(oseba):
return velikost_rodbine(oseba) - 1
</pre>
<h1> Rekurzivne funkcije na seznamih </h1>
<h2>Palindrom</h2>
<p>Niz je palindrom, če se naprej in nazaj bere enako.</p>
<p>Pisati funkcijo, ki pove, ali je podani niz palindrom, je sicer železni
repertoar pouka programiranja - v Pythonu pa je nekoliko trivialen. Če imamo
niz <code>s</code>, bomo z <code>s[1:-1]</code> dobili obrnjen niz, niz
"prebran" nazaj. Če sta tadva enaka, je funkcija palindrom.</p>
<p>Ker vem, da ste pametni ljudje, ne boste pisali</p>
<pre>def palindrom(s):
if s == s[::-1]:
return True
else:
return False</pre>
<p>temveč, kratko in jedrnato</p>
<pre>def palindrom(s):
return s == s[::-1]</pre>
<p>Zdaj pa recimo, da za tole obračanje nizov ne vemo (ali pa, da programiramo
v jeziku, ki česa takšnega nima. V tem primeru potrebujemo zanko: rekli bomo,
da je <code>s</code> palindrom, če je ničti znak enak zadnjemu, prvi
predzadnjemu in tako naprej do konca. Po vzorcu, ki nam je že čisto domač,
bomo ob prvem neujemanju zatulili <code>Falsch!</code>; če pridemo do konca
brez težav, vrnemo <code>True</code>.</p>
<pre>def palindrom(s):
for i in range(len(s)):
if s[i] != s[-i - 1]:
return False
return True</pre>
<p>(Pravzaprav ni potrebno, da gremo "tako naprej do konca", saj bi zadoščalo
"tako naprej do sredine". A to tule ni pomembno.)</p>
<p>Palindrome lahko definiramo na drug način, ki ne zahteva štetja: rečemo
lahko, da je <code>s</code> palindrom, če je ničti znak enak zadnjemu in je
palindrom tudi vse med njima. Poskrbeti je le potrebno za nize, ki nimajo
dveh znakov: če je niz krajši od dveh znakov, bomo rekli, da je palindrom.</p>
<p>Z enim stavkom: <code>s</code> je palindrom, če je krajši od dveh znakov ALI
pa je ničti znak enak zadnjemu IN so vsi znaki od prvega do predzadnjega
palindrom.</p>
<pre>def palindrom(s):
return len(s) < 2 or s[0] == s[-1] and palindrom(s[1:-1])</pre>
<p>Študente tole pogosto zbega. Funkcija <code>palindrom</code> je definirana
s funkcijo <code>palindrom</code>. Sama s sabo. Je to sploh dovoljeno? Deluje?
</p>
<p>Razlog, da deluje, je v tem, da je niz vedno krajši. Ko se vprašamo, ali je
"abcdcba" palindrom, funkcija ugotovi, da to sicer ni manj kot dva znaka,
vendar je palindrom, če je ničti znak enak zadnjemu (kar je) in če je "bcdcb"
palindrom. Ko preverja, ali je "bcdcb" palindrom, ugotovi, da je daljši od dveh
znakov, zato bo palindrom, če je ničti enak zadnjemu (kar je) in če je "cdc"
palindrom. Ta je daljši od dveh znakov, zato bo palindrom, če je ničti znak
enak zadnjemu in je "d" palindrom. Niz "d" je krajši od dveh znakov, torej je
palindrom. Zato je torej tudi "cdc" palindrom. Zato je "bcdcb" palindrom.
Zato je "abcdcba" palindrom.</p>
<h2>Vsota elementov seznama</h2>
<p>Kako bi izračunali vsoto elementov seznama. Z zanko seveda znamo. Pa
poskusimo še s trikom, kakršnega smo uporabili zgoraj. Za to potrebujemo
rekurzivno definicijo vsote seznama - definicijo, ki se nanaša sama nase.</p>
<p>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.</p>
<pre>def vsota(s):
if not s:
return 0
return s[0] + vsota(s[1:])</pre>
<h2>Ima seznam sama soda števila</h2>
<p>Seznam ima sama soda števila, če je prazen ali pa je prvi element sod in
ima preostanek sama soda števila.</p>
<pre>def soda(s):
return not s or s[0] % 2 == 0 and soda(s[1:])</pre>
<h2>Vsota sodih števil v seznamu</h2>
<p>Napisati želimo funkcijo, ki vrne vsoto vseh sodih elementov v podanem
seznamu.</p>
<p>Če je seznam prazen, je vsota enaka 0. Sicer pa naredimo tole: če je ničti
element sod, vrnemo vsoto ničtega elementa in vsote ostalih. Če ni sod, vrnemo
le vsoto ostalih.</p>
<pre>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:])</pre>
<h2>Prvi sodi element seznama</h2>
<p>Napisali bomo funkcijo, ki vrne prvi sodi element.</p>
<p>Če je ničti element sod, vrnemo tega. Sicer vrnemo prvega sodega med
ostalimi.</p>
<pre>def prvi_sodi(s):
if s[0] % 2 == 0:
return s[0]
else:
return prvi_sodi(s[1:])</pre>
<p>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,
<code>s[0]</code> in Python bo javil napako, <code>Index out of range</code>.
</p>
<p>Recimo, da bo funkcija v takšnem primeru vrnila <code>None</code>.</p>
<pre>def prvi_sodi(s):
if not s:
return None
if s[0] % 2 == 0:
return s[0]
else:
return prvi_sodi(s[1:])</pre>
</body>
</html>
|
