Rekursiivne otsing - koodinäide

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 iseennast välja kutsuma! 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

Esmalt proovime määrata tingimusi, mil 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õnes where ei leidu kunagi 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 kindlad, 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 seekord on vaja sõnest esimene sümbol välja visata, muidu ta hakkab sama sõne lõpmatult kontrollima.

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. Igal 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 tehakse seda 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) jõuab kunagi selleni, et what on where alguses VÕI what on pikem kui where. Nii saabki ta rekursioonist välja.

Aga mis siis, kui funktsioon tagastab rekursioonis kunagi -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 tingimust, et kui alamsõnes otsitavat sõne 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("y", "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