Pritisnite F11

Iz varnostnih razlogov je mogoče celozaslonski način vključiti samo s pritiskom na gumb F11 na tipkovnici.

Ko ste enkrat v celozaslonskem načinu, ga izključite spet s pritiskom na F11.

Rekurzija

Avtor: Karmen Perko

Učni cilji: Spoznati rekurzijo, uporabiti rekurzijo na različnih primerih (matematika, seznami, risanje).

Hvala za ogled gradiva!

Veseli bomo vaših komentarjev. Obiščite nas na www.nauk.si.

IZZIV

Koliko ogledal je na sliki?

Ogledala znotraj ogledala

Kolikokrat se pogovarjam s samim seboj, če imam v roki dva telefona in z enim kličem samega sebe?

Pogovor s samim seboj

Kako pa je z vsoto ploščin vseh kvadratov, ki jih dobimo, če svetlemu kvadratu včrtamo temnejšega, temu spet svetlega in tako naprej? Kvadrati imajo oglišča v razpoloviščih stranic prejšnjih kvadratov.

Včrtani kvadrati kvadratu s stranico a

Vsi trije primeri so povezani z rekurzijo. Kaj je rekurzija?

Na prejšnjo stran Rekurzija?

Kaj je rekurzija?

Beseda rekurzivno izhaja iz latiske besede recurrere (pomeni teči nazaj) in pomeni nanašajoče na samega sebe.

Rekurzija v matematiki pomeni podajanje funkcije na tak način, da se v definiciji sklicujemo na to isto funkcijo, a pri drugačnem argumentu.

S primerom rekurzije se v resnici srečujemo vsak dan. Definicija prednika neke osebe je lahko:

- prednik osebe je eden od roditeljev osebe (osnovni primer)

- prednik pa je tudi roditelj katerega koli prednika (rekurzivni primer).

Po računalniško pa bi rekli, da je rekurzija funkcija, ki je definirana sama s seboj.

Najprej se lotimo problema z vsoto včrtanih kvadratov.

Na prejšnjo stran Včrtani kvadrati

Ploščina včrtanih kvadratov

Včrtani kvadrati

Ploščina osnovnega kvadrata s stranico je . Sedaj moramo določiti stranico osnovnemu kvadratu včrtanega kvadrata. Ker njegovo oglišče leži v razpolovišču strance , bo za stranico novega kvadrata veljalo

Dolžino nove stranice izračunamo

Naslednjo stranico izračunamo . Nadaljujemo podobno.

Čemu je enaka vsota ploščin vseh štirikotnikov?

Opazujmo zaporedne ploščine kvadratov. Kaj imajo skupnega?

Velja

za vsa naravna števila .

Seštejemo lahko končno število ploščin

ali pa neskončno. Tu gre za vsoto neskončnega geometrijskega zaporedja, katerega količnik je po absolutni vrednosti manjši od . Zato lahko vsoto izračunamo kar po splošni formuli za vsoto neskončnega geometrijskega zaporedja

Parameter je količnik danega geometrijskega zaporedja.

Za naš primer je količnik enak . Dobimo

Kako bi se danega primera lotili s programiranjem?

Na prejšnjo stran Naprej

Programiranje

Definirali bomo novo funkcijo, ki bo seštela ploščine kvadratov, včrtanih enega v drugega.

Po klicu se rekurzivna funkcija zaradi njene definicije nikoli ne konča, saj v vsakem koraku zopet pokliče samo sebe. A če želimo priti do rešitve, se mora postopek nekje končati. Zato je potreben ustavitveni pogoj. Kdaj ga bomo uporabili? Običajno takrat, ko je problem dovolj majhen /enostaven, da za njegov izračun ne potrebujemo več rekurzivnega klica.

Poglejmo, kako vstavimo ustavitveni pogoj v našo funkcijo.

Koda:

def vsotaPloscin (a,n):
        import math
        if n == 1: # Ustavitveni pogoj.
            return a*a
        else:
            return a*a + vsotaPloscin(a*math.sqrt(2)/2) # Rekurzivni klic.

Ne glede na področje, kjer srečamo rekurzijo, rekurzivni algoritem vedno vsebuje naslednja pravila:

- Definiran mora biti najmanjši/najenostavnejši problem, ki se ga da preprosto rešiti. Če je problem majhen, funkcija vrne kar rešitev zanj. V nasprotnem primeru funkcija razdeli problem na manjše podprobleme iste vrste, jih reši in rešitve združi.

- Funkcija mora klicati samo sebe.

- Funkcija mora prehajati preko vseh manjših podproblemov k enostavnemu problemu, s katerim se funkcija konča. Le-ta je tudi ustavitveni pogoj naše rekurzivne funkcije.

Na prejšnjo stran Naprej

Vsota števil v seznamu

Poglejmo si še eno nalogo, pri kateri nastopa rekurzija.

Izračunaj vsoto vseh števil v danem seznamu.

Recimo, da je dan seznam sez = [2,3,5,6,1] . Radi bi sešteli vse njegove elemente.

Problema ne bo težko rešiti brez rekurzije.

def vsota(sez):
    vsota = 0
    for i in sez:
        vsota = vsota + i
    return vsota

>>> vsota([2,3,5,6,1])
17
>>>

Kako pa bi se zadeve lotili z rekurzijo?

Vsoto vseh danih števil iz seznama lahko dobimo tako, da najprej seštejemo prvi dve števili z enega konca seznama, tej vsoti prištejemo naslednje število v seznamu in tako naprej. Tako k skupni vsoti prištejemo števila celotnega seznama. Vsaka naslednja vsota predstavlja seštevanje dveh sosednjih števil kot smo to naredili na začetku.

Algoritem lahko ponazorimo z oklepaji

Vidimo, da je notranji oklepaj oz. enostavna operacija, rešljiva brez zanke. Prvotni korak, ki nas privede do rešitve enostavnega problema, ponavljamo vse do konca seznama, dokler nam ne ostane ena sama vrednost, ki predstavlja vsoto vseh števil. To je naš zaustavitveni pogoj.

Kakšno kodo nam narekuje dani algoritem?

Ideja: Vsota števil v seznamu je vsota prvega števila in seštevka števil v preostanku seznama.

Rekurzija:

vsota(seznam) = prvoStevilo(seznam) + vsota(preostanek(seznam))

Koda:

def vsota(seznam):
    if len(seznam) == 1:
        return seznam[0]
    else:
        return seznam[0] + vsota(seznam[1:])

Na prejšnjo stran Naprej

Fibinaccijevo zaporedje

Zagotovo poznaš Fibonaccijevo zaporedje. Njegova definicija je:

Zapiši rekurzivno funkcijo, ki za podano naravno število vrne -ti člen Fibonaccijevega zaporedja.

Razmisli še, kako bi funkcijo napisal brez uporabe rekurzije?

Na prejšnjo stran Fibinaccijevo zaporedje

Koda za Fibonaccijevo zaporedje

Rešitev z rekurzijo je precej enostavna, saj moramo le definicijo zaporedja pretvoriti v programski jezik.

def fibinacci(n):
'''Rekurzivna koda'''
    for n==1 or n==2:
           return 1
    else:
            return fibomacci(n-1) + fibonacci(n-2) #rekurzivni korak

Za rešite brez rekurzije pa potrebujemo nekaj več dela. Tu si bomo pomagali s seznamom. Vanj si bomo shranjevali posamezne člene zaporedja.

def fibonacci(n):
    '''Nerekurzivna funkcija'''
    if n==1 or n==2:
            return 1
    cleni = [1,1]
    for i in range(2,n): #Seznam členov Fibonaccijevega zaporedja
            noviClen = cleni[i-1] + cleni[i-2]
            cleni.append(noviClen)
    return noviClen

Na prejšnjo stran Nekaj vprašanj za vajo

Naloga 1

Rekurzij lahko uporabimo za problem,:

ki ga lahko razstavimo na podprobleme različne vrste.

ki ga lahko razstavimo na podprobleme iste vrste.

ki ga ne moremo razstaviti na podprobleme.

Nazaj Naprej

Odgovor je pravilen.

Naprej

Odgovor je napačen. Pomoč: Rekurzivna funkcija se sklicuje na samo sebe.

Poskusite ponovno.

Naloga 2