Close menu
Close menu

Tunnistaudu

Kirjaudu

Etkö ole vielä jäsen?

Liity jäseneksi

5.1 Listojen käsittely rekursiivisesti

Listojen käsittely rekursiivisesti

Rekursiivisia funktioita käsiteltiin aiemmin kohdassa 2.2. Rekursiiviset funktiot ja lukujonot. Myös listoja voidaan käsitellä rekursiivisesti. Toteutettaessa alkion etsintää listasta, voidaan lähteä liikkeelle listan alusta, ja tutkia onko etsittävä alkio listan ensimmäinen. Jos etsittävä alkio löytyi, lopetetaan listan läpikäynti ja palautetaan tosi. Mikäli etsittävää alkiota ei löytynyt, jatketaan listan loppuosan tutkimista rekursiivisesti. Jos tutkittava lista menee tyhjäksi, palautetaan epätosi (alkiota ei siis löynyt listasta ja päädyttiin lopetusehtoon).
Slide2.PNG
Toteutettaessa monimutkaisempia algoritmeja listoille tarvitaan usein apumuuttujia sekä apufunktioita. Tarkastellaan listan pituuden laskevan algoritmin pituus toteuttamista. Listan pituus voidaan laskea samalla, kun lista käydään läpi alusta loppuun rekursiivisesti. Jotta listan pituus saadaan talteen, tarvitaan apumuuttujaa jonka avulla voidaan kuljettaa rekursion mukana tietoa listan pituudesta. Tätä varten on toteutettu apufunktio pituus_apu. Funktio saa argumentteina tutkittavan listan sekä apumuuttujan. Laskettaessa listan pituutta rekursiivisesti, kasvatetaan jokaisella rekursiivisella funktiokutsulla apumuuttujan arvoa yhdellä. Rekursion loputtua apumuuttujan arvona on listan pituus.
Slide5.PNG
Kuten edellisessä esimerkissä, voidaan vastaavasti laskea rekursiivisesti myös listan alkioiden summa. Funktio summaa saa argumenttina listan, jonka alkioiden summa pitää laskea. Apufunktio summaa_apu saa argumentteina listan luvut ja apumuuttujan tulos. Luvut-listaa käydään alkupäästä läpi rekursiivisesti, ja samalla tulos-muuttujan arvoa kasvatetaan. Tulos-muuttujan arvo välitetään rekursiokutsujen mukana. Kun listan kaikki luvut on käyty läpi, on muuttujaan tulos laskettu listan alkioiden summa.
Slide6.PNG

Tehtäväsarja 1: Listojen käsittelyä rekursiivisesti
Tehtäväsarja 2: Apufunktion käyttö
5.2 Lajittelu