| << 1.2 Probleemi lahendamine algoritmiga | Sisukord | 1.4 Palju aega algoritmil kulub >> |
Tunni läbimisel:
- Tean mis on rekursioon
- Oskan koostada lihtsaid rekursiivseid programme
- Oskan koostada algoritmi kõikide variantide läbivaatamiseks
1.3 Rekursiivsed algoritmid
Keeruliste ülesannete lahendamiseks on kasulik nad tihti lihtsamateks ülesanneteks jagada, mida me oskame lahendada. Üheks levinud viisiks on kirjutada esmalt funktsioon, mis lahendab ülesanne kõige lihtsamal juhul. Seejärel lihtsustame ülesannet järk-järguliselt, kuni me jõuame olukorda, mida me juba oskame lahendada. Selleks tuleb meile appi rekursioon.
Rekursiooni definitsioon: Rekursioon on tegevuse sees endataolise tegevuse väljakutsumine.
Seega saame funktsiooni sees seda sama funktsiooni uuesti välja kutsuda, enamasti väiksema andmemahuga, kuni jõuame baasjuhuni, ehk olukorda, kus funktsiooni enam rekursiivselt välja ei kutsuta.
Kas sa tead, mis võiks olla rekursiooni vaste matemaatikas?
- matemaatiline induktsioon
Ülesanne 1
Matemaatika tunnist on sulle tuttav faktoriaali mõiste. Siin on see kujutatud valemina:
Sinu ülesanne on nüüd koostada faktoriaali leidmise programm, kasutades rekursiooni. Siin on esialgne programm, mõtle välja, mis peaks minema punase küsimärgi asemele, et saada rekursiooni samm.
- Siin on pea-aegu valmis funktsioon, sinu ülesandeks on nüüd välja mõelda, mis peaks olema faktoriali väljakutse argumendiks.
Nagu näha annab rekursiooni kasutamine enamasti üsna elegantse ja lühikese lahenduse. Kõige paremini sobib rekursioon ülesannete lahendamiseks, mis hargnevad palju, näiteks arvutis kaustade läbi vaatamiseks (rekursiooni sammus vaadatakse sisse kõikidesse alamkaustadesse ning korratakse seda protsessi, kuni on jõutud kataloogi, milles enam alamkatalooge pole).
Ülesanne 2
Üks ülesanne, mis ilma rekursioonita on päris keeruline lahendada, on kõikide variantide läbivaatamine. Näiteks järgnev kood genereerib kõikvõimalikud bitijadad pikkusega n. Näiteks n=2 korral on nendeks: "00", "01", "10" ja "11".
Koosta selle näite põhjal paroolimurdmise programm, mis genereerib kõikvõimalikke sõnu pikkusega n. Ehk siis n=2 korral väljastatakse kõik kahetähelised kombinatsioonid: "aa", "ab", "ac", ... , "zy", "zz". NB! Seda programmi pole soovitatav väga suure n väärtuse korral proovida, võib kaua aega kuluda!
- Erinevalt bitijadadest jaguneb paroolimurdmise programm igal sammul rohkem kui kaheks. Ehk siis kutsutakse iseennast välja kõigi tähtedega a-z.
- Selleks soovitame kasutada rekursiooni sammus for-tsüklit.
Lisaülesanded
- Kirjuta faktoriaali leidmise programm, mis ei kasuta rekursiooni.
- Kirjuta programm, mis prindib välja etteantud kataloogi kataloogipuu. Et Phythonis kataloogidele ja failidele ligi pääseda, pead kasutama moodulit os. Rohkem infot leiad siit: https://docs.python.org/2/library/os.path.html
Järgmises peatükis mõtleme, kuidas ennustada, kui palju selliste funktsioonide arvutamine aega võtab!
Mõisted:
- rekursioon - tegevuse sees endataolise tegevuse väljakutse
- baasjuhtum - rekursiooni haru, kus ülesannet enam rekursiivselt välja ei kutsuta
- rekursiooni samm - see haru, mis kutsub funkstiooni rekursiivselt välja
Viited:
| << 1.2 Probleemi lahendamine algoritmiga | Sisukord | 1.4 Palju aega algoritmil kulub? >> |