Rekursioon (Recursion)

Mis on rekursioon?

• Rekursioon on funktsiooni defineerimine iseenda kaudu.
• Programmeerimises tähendab see seda, et funktsioon kutsub iseennast välja.
• See on meetod probleemide lahendamiseks, kus lahendus sõltub sama probleemi väiksematest osadest.

Kaks peamist osa

Iga korrektne rekursiivne funktsioon peab koosnema kahest osast:

1. Baasjuht (Base case): Tingimus, mille puhul rekursioon lõpetatakse ja funktsioon tagastab väärtuse ilma iseennast uuesti välja kutsumata. See väldib lõpmatut kordust.
2. Rekursiivne samm: Funktsioon kutsub end välja uute parameetritega, mis on "lähemal" baasjuhule.

Näide: Faktoriaal

Matemaatiline definitsioon: n! = n * (n - 1)! ja 0! = 1.

def factorial(n):
    if n == 0:  # Baasjuht
        return 1
    return n * factorial(n - 1)  # Rekursiivne samm
        

Näide: Fibonacci jadad

Jada, kus järgmine arv on kahe eelmise summa: 0, 1, 1, 2, 3, 5, 8, 13...

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)
        

Miks kasutada rekursiooni?

• Mõned probleemid on rekursiivselt esitatuna palju loetavamad ja lihtsamad (nt puu-struktuuride läbimine, fraktalid).
• See võimaldab kirjutada koodi, mis vastab otseselt matemaatilistele definitsioonidele.

Ohud ja piirangud

• RecursionError: Kui baasjuht puudub või selleni ei jõuta, tekib lõpmatu rekursioon (Stack Overflow).
• Mälukasutus: Iga funktsiooni väljakutse võtab arvuti mälus ruumi (call stack).
• Efektiivsus: Ilma optimiseerimata (nt memoization) võib rekursioon olla väga aeglane (nt Fibonacci näide).

Pythonis on rekursiooni sügavuse limiit tavaliselt 1000 väljakutset.

Rekursioon vs Iteratsioon

• Kõiki rekursiivseid ülesandeid on võimalik lahendada ka tsüklitega (iteratsioon).
• Tsükkel on sageli mälu säästvam, kuid rekursioon võib olla elegantsem keeruliste andmestruktuuride puhul.

Kokkuvõte

• Funktsioon kutsub end ise välja.
• Vajalik on selge lõpetamise tingimus (baasjuht).
• Probleem jagatakse järjest väiksemateks sarnasteks tükkideks.