Tapaaminen 04.02.2010
Aiheina:
- monikko
- rekursio
- virheenkäsittely
- poikkeus
Linkkejä:
- Kirjan kappale 18 (Rekursio)
- Kirjan kappele 19 (Poikkeukset)
Monikko ja muutettavuus
Aiemmin tutustuimme merkkijonoihin ja listoihin, joista merkkijonot olivat muuttumattomia ja listat muutettavia. Monikko on monella tapaa listan kaltainen, mutta muuttumaton tietorakenne. Monikko on pilkuilla eroteltu luettelo (jakso) alkioita, kuten listakin.
>>> mon = 2, 4, 6, 8
Sulkeet monikon ympärillä eivät ole pakolliset, mutta niitä käytetään usein selkeyden vuoksi.
>>> mon = (2, 4, 6, 8)
Jos monikossa on vain yksi alkio, pitää tämän jälkeen olla pilkku.
>>> mon = (5,)
>>> type(mon)
<type 'tuple'>
>>> mon = (5)
>>> type(mon)
<type 'int'>
Jälkimmäisessä tapauksessa (5) tulkittiin vain kokonaisluvuksi sulkeissa. Monikolle olennaista ovat siis pilkut, eivät sulkeet.
Monikko toimii indeksien kanssa ja viipaloitaessa aivan, kuten lista ja merkkijono.
>>> mon = (2, 4, 6, 8)
>>> mon[1]
4
>>> mon[1:3]
(4, 6)
Koska monikko on muuttumaton, ei sen alkioida voida vaihtaa.
>>> mon[1] = 'a'
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
Uusia monikoita voidaan kuitenkin luoda vanhoista.
>>> mon = mon[:1] + ('a',) + mon[2:]
>>> mon
(2, 'a', 6, 8)
Monikko voidaan myös muuntaa listaksi, joka on muutettava.
>>> l = list(mon)
>>> l
[2, 'a', 6, 8]
Monikkoja voidaan käyttää hyväksi myös sijoituslauseessa. Useisiin muuttujiin voidaan sijoittaa arvoja seuraavasti:
>>> a, b = 3, 6
>>> a
3
>>> b
6
Python käsittelee siis sijoituslausekkeen molempia puolia monikkoina ja oikea puoli sijoitetaan vasempaan. Tämä merkintä on näppärä myös vaihdettaessa kahden (tai useamman muuttujan) arvoja keskenään. Monissa ohjelmointikielissä muuttujien a ja b arvot pitäisi vaihtaa käyttämällä apumuuttujaa.
>>> tmp = a
>>> a = b
>>> b = tmp
Monikon avulla voimme kuitenkin tehdä sijoutuksen suoraan:
>>> a, b = b, a
Rekursiiviset rakenteet
Tapaamiamme tietorakenteita voidaan laittaa listoihin ja monikkoihin monin tavoin. Listoihin ja monikkoihin voi laittaa myös toisia monikkoja ja listoja. Määritellään lukulistat seuraavasti. Lukulistan alkiot voivat olla:
- lukuja
- sisällytettyjä lukulistoja
Esimerkiksi:
>>> ll = [2, 6, [3, 7, 4], 5, [3, [1, 2], 4], 8, 2]
Nyt lukulista on määritelty itsensä (lukulistojen) avulla. Tällainen määritelmä on rekursiivinen ja puhumme rekursiivisesta tietorakenteesta.
Seuraavaksi haluamme laskea lukulistan lukujen summan. Pythonissa on valmiiksi funktio sum(), joka laskee sille annetun jakson lukujen summan, mutta se ei osaa käsitellä sisäkkäisiä listoja.
>>> sum([1,2,3])
6
>>> sum([1,[2,3]])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'int' and 'list'
Summan lasku ei onnistu, joska osa listan alkioista on kokonaislukuja ja osa listoja ja Python ei osaa laskea niitä yhteen.
Meidän täytyy siis kirjoittaa oma summafunktio.
Rekursio
Jotta saamme laskettua summan, meidän täytyy jollain tavalla käydä läpi kaikki listan alkiot ja mahdollisten sisäkkäisten listojen alkiot. Rekursiivisten rakenteiden käsittelyyn on luonnollista käyttää rekursiivisia funktiokutsuja. Rekursiivisilla funktiokutsuilla tarkoitetaan tilanteita, joissa funktio omassa vartalossaan kutsuu itseään. Rekursiolla haluttu summafunktio voidaan kirjoittaa varsin lyhyesti:
def recursive_sum(nested_num_list):
sum = 0
for element in nested_num_list:
if type(element) == type([]):
sum = sum + recursive_sum(element)
else:
sum = sum + element
return sum
Funktion recursive_sum() toimintaperiaate on seuraava: Se käy listan alkiot läpi for silmukalla yksi kerrallaan ja jos listan alkio on luku, se lisää luvun summaan. Jos taas listan alkiona on sisempi lista, selvitetään sen sisältämien lukujen summan uudella recursive_sum()-funktion kutsulla ja lisätään se summaan. Listan
[2, 6, [3, 7, 4], 5, [3, [1, 2], 4], 8, 2]
summa muodostuu siis seuraavasti:
recursive_sum([2, 6, [3, 7, 4], 5, [3, [1, 2], 4], 8, 2])
= 2 + 6 + recursive_sum([3, 7, 4]) + 5 + recursive_sum([3, [1, 2], 4]) + 8 + 2
= 2 + 6 + (3 + 7 + 4) + 5 + (3 + recursive_sum([1, 2]) + 4) + 8 + 2
= 2 + 6 + (3 + 7 + 4) + 5 + (3 + (1 + 2) + 4) + 8 + 2
= 2 + 6 + 14 + 5 + (3 + 3 + 4) + 8 + 2
= 2 + 6 + 14 + 5 + 10 + 8 + 2
= 47
Toinen, hieman monimutkaisempi tilanne, jossa käytetään rekursiota, on esitetty seuraavassa ohjelmassa. Sillä etsitään sisäkkäisiä listoja sisältävästä lukulistasta suurin luku.
def recursive_max(nested_num_list):
"""
>>> recursive_max([2, 9, [1, 13], 8, 6])
13
>>> recursive_max([2, [[100, 7], 90], [1, 13], 8, 6])
100
>>> recursive_max([2, [[13, 7], 90], [1, 100], 8, 6])
100
>>> recursive_max([[[13, 7], 90], 2, [1, 100], 8, 6])
100
"""
largest = nested_num_list[0]
while type(largest) == type([]):
largest = largest[0]
for element in nested_num_list:
if type(element) == type([]):
max_of_elem = recursive_max(element)
if largest < max_of_elem:
largest = max_of_elem
else: # element is not a list
if largest < element:
largest = element
return largest
Kuten while-silmukan kanssa, pitää myös rekursion kanssa olla varovainen, ettei jouduta päättymättömään rekursioon, jolloin kutsuttaisiin aina vain uusia sisäkkäisiä funktiokutsuja. Tällaisten tapausten varalta Pythonissa on yläraja rekursiotasoille. Ylärajan näkee sys-modulin funktiolla sys.getrecursionlimit().
Jotta päättymättömään rekursioon ei päädytä, pitäisi ongelman ratkaisussa aina päätyä lopulta perustapaukseen, jonka ratkaisemiseen ei tarvita rekursiivista funktiokutsua. Edellisissä esimerkeissä perustapauksia olivat kohdat, joissa listan alkio oli luku. Päättymättömään rekursioon ei näiden ongelmien kohdalla jouduta, sillä listoja ei ole sisäkkäin äärettömiä tasoja.
Esimerkki päättymättömästä rekursiosta:
#
# infinite_recursion.py
#
def recursion_depth(number):
print "Recursion depth number %d." % number
recursion_depth(number + 1)
recursion_depth(0)