Rekursioon

Vajalikud teadmised:

  1. Funktsioonid
  1. Tsüklid
  1. Sõne

Mõiste

Kõige paremini rekursiooni kirjeldab selline väike lause:

Rekursioon on rekursioon.

Kui rääkida tõsiselt, siis rekursiooniks võiks kutsuda objekti, mis leibub ise endast.

Äkki olete näinud niisuguseid pilte internetis.

Kui ei näe, otsi internetist pilte teemal *Recursion*.

Mõte on selles, et mingi asi kordub lõpmatult palju.

Rekursioon matemaatikas ning Rekurrentsed arvujadad

Matemaatikas kasutatakse rekutsiooni rekurrentsetes arvujadades. Arvujada on rekurrentne siis, kui jada mingi väärtus sõltub eelmisest väärtusest.

Näited:

Aritmeetiline jada: Iga järgmine väärtus on eelmisest d võrra suurem.

[d] näitab, et d on alamindeks.

Üldvalem: A[n] = A[n-1] + d

Olgu A[0] = 1, d = 3, siis jada näeb välja selline:
1 4 7 10 13 16 ...

Geomeetriline jada: Iga järgmine väärtus on eelmisest q korda suurem.

Üldvalem: A[n] = A[n-1] * q

Olgu A[0] = 1, q = 2, siis jada näeb välja nii:
1 2 4 8 16 32 ...

Fibonacci arvud: Iga järgnev liige on kahe eelneva liikme summa. (F[1] = 1, F[2] = 1)

Üldvalem: F[n] = F[n-1] + F[n-2]

F[1] = 0
F[2] = 1
F[3] = F[2] + F[1] = 1 + 0 = 1
F[4] = F[3] + F[2] = 1 + 1 = 2
F[5] = F[4] + F[3] = 1 + 2 = 3
...

Kus siin on rekursioon? See üldvalem on ju funktsioon. Et leida viiendat väärtust, tuli meil funktsiooni uuesti kasutada, aga seekord eelmiste väärtustega. Ja nii tegimegi, kuni saime valemi, kus on ainult meile teadaolevad väärtused (F[1], F[0]). Kui neid ei oleks, siis me ei saaks väärtust arvutada, sest oleks vaja lõpmatult palju eelmisi väärtusi otsida. Seda juhtumit võib julgelt rekursiooniks kutsuda.

Rekursioon programmeerimises

Programmeerimises on ka olemas funktsioonid. Funktsioonid programmeerimises võimaldavad teha sama palju asju nagu matemaatikas ja isegi rohkem. Keegi ei keela funktsioonis seda sama funktsiooni uuesti välja kutsuda. See ongi rekursioon programmeerimises: funktsioon kutsub ise ennast välja.

def foo():
    ...
    ... foo() ...
    ...

Kui meil oli juttu Fibonacci arvudest, siis seal meile anti kaks liiget ja me kasutasime neid järgmiste liikmete arvutamiseks. Kui neid liikmeid ei oleks, siis me ei saaks ühtegi liiget arvutada, sest eelmiste liikmete otsimine võtaks lõpmatult palju aega. Programmeerimises on sama lugu. On vaja määrata tingimusi, kui ei pea rekursiooni kasutama, muidu funktsioon hakkab kutsuma ise ennast välja lõpmatult palju. Kuid see ei tähenda, et programm jääb lõpmatult töötama. Kui funktsioon kutsub ise ennast välja liiga palju kordi, siis tekib erind RecursionError.

Miks programm ei jää lõpmatult töötama nagu while True tsükkel ja tekib RecursionError? Rekursioon tähendab, et meetodit kutsutakse välja veel kord. Iga funktsiooni käivitamise jaoks on vaja mälu, mida arvutis on piiratud hulk. Kui ei ole piisavalt mälu, siis ei saa funktsiooni käivitada. Seega RecursionError tähendab seda, et programmitöö jaoks eraldatud mälu sai otsa.

Lisaks tuleb aru saada, et kui funktsioon kutsub ise ennast välja, siis see ei tähenda, et see käivitub uuesti! Situatsioon on põhimõtteliselt sama kui teise funktsiooni poole pöördumine, ainuke asi et peafunktsioon ja alamfunktsioon on samad! Kui funktsioon kutsub ise ennast välja, siis see alamfunktsioon käivitub paralleelselt. Peafunktsioon ootab kuni alamfunktsioon lõpetab oma töö ära ja siis jätkab oma tööd.

Sabarekursioon

Funktsioonis on sabarekursioon siis, kui selle sama funktsiooni väljakutse on viimane tegevus.

def foo():
    ...
    foo()
    # no more actions

Näide 1. Faktoriaali arvutamine

Kirjutame funktsiooni, mis arvutab arvu faktoriaali.

Faktoriaal n! on kõikide eelnevate arvude korrutis.

n! = n * (n-1) * (n-2) * (n-3) * ... * 3 * 2 * 1
5! = 5 * 4 * 3 * 2 * 1 = 120
3! = 3 * 2 * 1 = 6

Kus siin võiks olla rekursioon? On vaja leida seos faktoriaalide jadast nii, et iga järgmine liige sõltuks eelmisest liikmest.

5! = 5 * 4 * 3 * 2 * 1
4! =     4 * 3 * 2 * 1

Näeme, et nendel kahel avaldisel on ühisosa. Võime kirjutada nii: 5! = 4! * 5 ehk n! = n * (n-1)!

Vaatame, kas see ikkagi kehtib üldjuhul:

n!     = n * (n-1) * (n-2) * (n-3) * ... * 3 * 2 * 1
(n-1)! =     (n-1) * (n-2) * (n-3) * ... * 3 * 2 * 1

n! = n * (n-1)!

Ikka kehtib. Nüüd on meil valem olemas.

n! = n * (n-1)!

Praegu on vaja tingimust, mil saame anda vastuse ilma rekursioonita. Matemaatikas on tõestatud, et 0! = 1. Seda meil ongi vaja!

Nüüd kirjutame funktsiooni. On selge, et funktsioonil peab olema üks sisendargument. See on mingi arv n, mille jaoks me faktoriaali arvutame.

def factorial(n):

Praegu tasub kohe kirja panna tingimus, et kui n võrdub 0-ga, siis funktsioon tagastab 1.

def factorial(n):
    if n == 0:
        return 1

Kui n ei võrdu 0-ga, siis me leidsime, et n! = n * (n-1)!

def factorial(n):
    if n == 0:
        return 1 # get here if only n equals 0

    return n * factorial(n - 1)

Kuidas funktsioon töötab:

Nt. factorial(3)

factorial(3):
1. 3 = 0? => False
2. return 3 * factorial(2)
    Nüüd on vaja arvutada factorial(2)
    factorial(2):
    2.1. 2 = 0? => False
    2.2. return 2 * factorial(1)
        Nüüd on vaja arvutada factorial(1)
        factorial(1):
        2.2.1. 1 = 0? => False
        2.2.2. return 1 * factorial(0)
            Nüüd on vaja arvutada factorial(0)
            factorial(0):
            2.2.2.1. 0 = 0? True => return 1
            factorial(0) = 1
        2.2.3. return 1 * 1
        factorial(1) = 1
    2.3. return 2 * 1
    factorial(2) = 2
3. return 3 * 2
factorial(3) = 6

Kokkuvõte

  1. Leia seos eelmise ja järgmise väärtuste vahel.
  2. Määra tingimus(t/i), mille korral võib vastust kohe anda.

Iteratiivne meetod

Iteratiivne meetod tähendab, et kasutatakse tsükleid. Rekursiivset funktsiooni on alati võimalik ümber kirjutada nii, et see oleks iteratiivne.

Faktoriaali iteratiivne arvutamine

def factorial_iter(n):
    if n == 0:
        return 1

    answer = 1
    for i in range(1, n + 1): # range(1, n + 1) => [1, 2, 3, 4, 5, 6, ..., n - 1, n]
        answer = answer * i

    return answer

Sellel juhul on see meetod efektiivsem, kuna see suudab suurte arvude faktoriaali arvutada. Rekursiivne meetod viskab aga suurte arvude korral RecursionError, sest on liiga palju rekursiivseid väljakutseid.

Näide 2. Fibonacci arvud.

Meil on piisavalt teadmisi Fibobacci arvudest.

F[n] = F[n-1] + F[n-2]
F[0] = 0, F[1] = 1, F[2] = 1

Kirjutame funktsiooni.

Sisend: n - indeks Fibonacci arvujadas. Väljund: Fibonacci arv, mis vastab indeksile n.

def fib(n):
     if n == 0:
         return 0

     if n == 1 or n == 2:
         return 1

     return fib(n - 1) + fib(n - 2)

Iteratiivne funktsioon

Siin kasutame kahte muutujat, et hoida mälus kaks viimast liiget. Iga kord, kui arvutame uut väärtust cur, paneme prev2 väärtuse muutujasse prev1 ja cur väärtuse paneme muutujasse prev2. Võiks ka kasutada list-i, aga see võtab rohkem mälu.

def fib_iter(n):
    if n == 0:
        return 0

    if n == 1:
        return 1

    prev1 = 0 # num0
    prev2 = 1 # num1

    # if n < 2 answer is already given
    for i in range(2, n + 1):
        cur = prev1 + prev2 # new value (num2)
        prev1 = prev2 # num1 becomes num0
        prev2 = cur   # num2 becomes num1

    return prev2

Efektiivsus

Iteratiivne meetod töötab kiiremini kui rekursiivne, sest rekursiivne ei jäta meelde kaks viimast väärtust ja arvutab neid kogu aeg uuesti. Nüüd meil on idee, kuidas teha rekursiivset lahendust kiiremaks: jätame meelde vanu väärtusi ja anname need väljakutsel lisaargumendina.

def fib(n, cache={0: 0, 1: 1, 2: 1}): # cache already contains 3 known values
    if n in cache: # if value is in the cache, return it
        return cache[n]

    # if the value is not in the cache, add and return it
    # notice that we add new value to the cache and give it as the additional argument
    cache[n] = fib(n - 1, cache) + fib(n - 2, cache)
    return cache[n]

Parem kood:

def fib(n, cache=None):
    if cache is None:
        cache = {0: 0, 1: 1, 2: 1} # cache already contains 3 known values

    if n in cache: # if value is in the cache, return it
        return cache[n]

    # if the value is not in the cache, add and return it
    # notice that we add new value to the cache and give it as the additional argument
    cache[n] = fib(n - 1, cache) + fib(n - 2, cache)
    return cache[n]

Võrdleme kiirust. Selleks arvutame 500 väärtust ja vaatame, kui palju aega see võtab mõlemal meetodil.

Kood võrdlemiseks:

    import time

if __name__ == '__main__':
    print("test for recursive method")
    started = time.time()
    for i in range(500):
        fib(i)

    print("Total: " + str(time.time() - started) + " secs")

    print("test for iterative method")
    started = time.time()
    for i in range(500):
        fib_iter(i)

    print("Total: " + str(time.time() - started) + " secs")
test for recursive method
Total: 0.0004994869232177734 secs
test for iterative method
Total: 0.021016836166381836 secs

Rekursiivne meetod, mis jätab väärtusi meelde, osutus kiiremaks kui iteratiivne. Kuid on arusaadav, et rekursiivne meetod kasutab ka palju mälu. Kui mälu ei kasuta, siis on arvutil juba raske 30. väärtust arvutada. Võite proovida sama asja faktoriaali lahenduse jaoks.

Näide 3. Rekursiivne otsing.

See ülesanne on juba sõnedele. Ülesandeks on realiseerida meetod find(where, what), mis otsib sõnes where sõne what ja tagastab esimest positsiooni (index), kus sõne what paikneb. Juhul kui sõnes where ei ole sõne what, siis tagastada -1. Kui otsitav sõne on tühi, siis tagastada 0. Lahendus peab olema rekursiivne, mis tähendab, et meie meetod peab kutsuma ise ennast välja! Tsükleid kasutada ei tohi!

Vihjed:

  1. Sõne on tühi, kui tema pikkus on 0. (len(word) = 0)
  2. Sõnes on igal sümbolil oma indeks. Indeksi lugemine algab 0-ga.
"Tere!"
"01234"

" Hello "
"0123456"
Näited:
find("abc", "ab") => 0
find("abc", "bc") => 1
find("   tere   ", "e") => 4
find("i'm empty", "HM") => -1
find("aba", "a") => 0

Enne proovime määrata tingimusi, kui rekursiooni ei pea kasutama. Vaatame korraga võimalikud olukorrad läbi:

1. Kui otsitav sõne (what) on tühi. Siis pole vaja midagi muud teha, kui lihtsalt tagastada 0. (Ülesande eelduse järgi)
2. Kui otsitav sõne pole tühi:
2.1. Kui where on tühi. (nt. where => “”, what => “a”) Sel juhul on arusaadav, et sõnest where kunagi ei leidu sõne what. Selle kohta on ülesandes öeldud, et tuleb tagastada -1.
2.2. Kui where pole tühi.
2.2.1. Kui sõne what pikkus on suurem, kui sõnel where. Siin on analoogiline situatsioon punktiga 2.1. Tagastame -1.
2.2.2. Kui sõne what pikkus ei ole suurem, kui sõnel where. Sel juhul ei saa anda täpset vastust ja tuleb edasi uurida.

Punktid nr 1, 2.1, 2.2 on lihtsad ja saame need kohe kirja panna.

def find(where, what):
    if len(what) == 0: # point 1
        return 0

    # now we are sure that *what* is not empty!

    if len(where) == 0: # point 2.1
        return -1
    if len(where) < len(what): # point 2.2.1
        return -1

NB! Kui what pole tühi (tema pikkus > 0) ja where on tühi (tema pikkus = 0), siis len(where) < len(what), mis tähendab, et pole vaja kontrollida eraldi, kas where pikkus võrdub 0-ga, sest punkt 2.2.1 teeb sama.

def find(where, what):
    if len(what) == 0: # point 1
        return 0

    # now we are sure that *what* is not empty!

    if len(where) < len(what): # point 2.2.1
        return -1

Nüüd oleme jõudnud punkti 2.2.2. juurde ja oleme kindel, et:

1. what ei ole tühi.
2. where ei ole tühi.
3. what on lühem kui where.

Selles ja sarnastes ülesannetes võiks kasutada sellist algoritmi:

1. Jaga sõne kaheks osaks. (Osa suurus sõltub ülesandest.)
2. Vaata, kas esimene osa täidab vajalikku nõuet.
Kui jah, siis tagasta tulemus.
Kui ei, siis uuri teist osa selle algoritmi järgi veel kord (rekursioon).
Esimene osa jäta muutmata.

Jagame sõne kaheks osaks. Millised peavad need osad olema? Sõne what võib olla sõne where alguses. Seega on mõistlik jagada nii, et esimene osa on sama pikkusega nagu otsitav sõne what. Siis vaatame, kui esimene osa ja what on sisuliselt võrdsed, siis tagastame 0.

def find(where, what):
    if len(what) == 0: # point 1
        return 0

    # now we are sure that *what* is not empty!

    if len(where) < len(what): # point 2.2.1
        return -1

    if where[0:len(what)] == what: # [0:len(what)] means that we take *len(what)* first symbols from the word *where*
        return 0

Aga kui what pole where alguses? (nt. where => “hello”, what => “el”)

Iteratiivse koodi mõte oleks selline:

  1. Vaata positsiooni 0.
  2. Vaata, kas what on where alguses. Kui jah, siis tagasta see positsioon, kui ei, siis mine edasi.
  3. Suurenda positiooni ühe võrra.
  4. Goto 2
  5. Kui ikka ei leidu, siis tagasta -1.

Siiamaani teame, et what pole where alguses. Siis on vaja suurendada positiooni ühe võrra ja kontrollida uuesti. Aga see kord, sõnest on vaja esimene sümbol välja visata, muidu ta hakkab kontrollima sama sõnet lõpmatult.

Ehk siis võtame esimese sümboli ära niikaua kuni sõne leidub või sümbolid saavad otsa. Iga alamsõne jaoks tuleb uuesti kutsuda välja meie meetodit. Iga järgmisel kutsumisel suurendame positsiooni.

find("hello", "o") = 1 + find("ello", "o") = 1 + 1 + find("llo", "o") = 1 + 1 + 1 + find("lo", "o") = 1 + 1 + 1 + 1 + find("o", "o") = 1 + 1 + 1 + 1 + 0 = 4

Kuidas esimene sümbol ära visata? Pythonis seda tehakse nii:

word1[1:] # word1 is a string type variable
"abc"[1:] => "bc"
"hello"[1:] => "ello"

Nüüd suurendame positsiooni ja otsime rekursiivselt teisest osast.

1 + find(where[1:], what)

find(where[1:], what) kunagi jõuab selleni, et what on where alguses VÕI what on pikem kui where. Nii saabki ta rekursioonist välja.

Aga mis siis, kui funktsioon kunagi rekursioonis tagastab -1?

find(w, w2) => 1 + 1 + 1 + ..... + -1
find(w, w2) peab olema siis -1, kuid on hästi näha, et nii ei tule välja.

Siin on mõistlik lisada tungimust, et kui alamsõnes otsitav sõnu ei leidu, siis tagastada -1, muul juhul tagastada 1 + find(alamsõne, otsitav_sõne).

Seepärast tuleb find(alamsõne, otsitav_sõne) panna muutujasse ja kontrollida.

index_in_subword = find(where[1:], what);

if index_in_subword == -1:
    return -1
else:
    return 1 + index_in_subword

Tuli välja selline kood:

def find(where, what):
    if len(what) == 0: # point 1
        return 0

    # now we are sure that *what* is not empty!

    if len(where) < len(what): # point 2.2.1
        return -1

    if where[0:len(what)] == what: # [0:len(what)] means that we take len(what) first symbols from the word where
        return 0

    index_in_subword = find(where[1:], what);

    if index_in_subword == -1:
        return -1
    # here the word else is not necessary
    # else:
    return 1 + index_in_subword

Näide 1:

find("hey", "s") => ?
# Look at the code to follow the action!
1. len("s") == 0 => 1 == 0 => False
2. len("hey") < len("s") => 3 < 1 => False
3. "hey"[0:len("s")] => "h"
4. "h" == "s" => False
5. index_in_subword = find("ey", "s")
        find("ey", "s"): # start new function!
        5.1. len("s") == 0 => 1 == 0 => False
        5.2. len("ey") < len("s") => 2 < 1 => False
        5.3. "ey"[0:len("s")] => "e"
        5.4. "e" == "s" => False
        5.5. index_in_subword = find("ey", "s")
        # this *index_in_subword* is different from *index_in_subword* at point 5 since it is in another function
                find("y", "s") : # start new function!
                5.5.1. len("s") == 0 => 1 == 0 => False
                5.5.2. len("y") < len("s") => 1 < 1 => False
                5.5.3. "y"[0:len("s")] => "y"
                5.5.4. "y" == "s" => False
                5.5.5. index_in_subword = find("", "s")
                        find("", "s"): # start new function!
                        5.5.5.1. len("s") == 0 => 1 == 0 => False
                        5.5.5.2. len("") < len("s") => 0 < 1 => TRUE
                        5.5.5.3. return -1
                        find("", "s") => -1
                        # return to the previous function with the answer
                5.5.6. index_in_subword = -1
                5.5.7. index_in_subword == -1 => -1 == -1 => TRUE
                5.5.8. return -1
                find("y", "s") => -1
                # return to the previous function with the answer
        5.6. index_in_subword = -1
        5.7. index_in_subword == -1 => -1 == -1 => TRUE
        5.8. return -1
        find("ey", "s") => -1
        # return to the previous function with the answer
6. index_in_subword = -1
7. index_in_subword == -1 => -1 == -1 => TRUE
8. return -1
find("hey", "s") => -1

Näide 2:

find("code", "python") => ?
where => "code", what => "python"
# Look at the code to follow the action!
1. len(what) == 0 => len("python") == 0 => 6 == 0 => FALSE
2. len(where) < len(what) => len("code") < len("python") => 4 < 6 => TRUE
3. return -1
find("code", "python") => -1

Näide 3:

find("code", "od") => ?
where => "code", what => "od"
# Look at the code to follow the action!
1. len(what) == 0 => len("od") == 0 => 2 == 0 => FALSE
2. len(where) < len(what) => len("code") < len("od") => 4 < 2 => FALSE
3. where[0:len(what)] == what => "code"[0:2] == "od" => "co" == "od" => FALSE
4. index_in_subword = find(where[1:], what) => find("code"[1:], "od") => find("ode", "od")
        find("ode", "od"):
        # start new function which works in parallel with *find("code", "od")*
        # *find("code", "od")* waits until *find("ode", "od")* is finished and then will continue
        4.1. len(what) == 0 => len("od") == 0 => 2 == 0 => FALSE
        4.2. len(where) < len(what) => len("ode") < len("od") => 3 < 2 => FALSE
        4.3. where[0:len(what)] == what => "ode"[0:2] == "od" => "od" == "od" => TRUE
        4.4. return 0
        find("ode", "od") => 0
        # back to the *find("code", "od")*
5. index_in_subword = 0
6. index_in_subword == -1 => 0 == -1 => FALSE
7. return 1 + index_in_subword => 1 + 0 => 1
find("code", "od") => 1

Edu!