Informatika2-2015/Eloadas 2 Python-2 Rekurzio es Ciklus

Függvényhívás példa

Múlt órán volt részletesen szó függvényhívásról. Itt egy példa:

link

Amit érdemes megfigyelni, hogy amikor a negyzetel() függvény meghívja a negyzet() függvényt (pl. Step 8-nál), amíg a negyzet() fut, a negyzetel() még nem ért véget, csak fel lett függesztve azon a ponton, ahol vár a negyzet() visszatérési értékére, majd onnan folytatódik.

Ciklus vagy rekurzió

A mai órán két programozási módszerről lesz szó, amik már előző félévben is szerepeltek valamennyire. Megvizsgáljuk a különbségeket és hasonlóságokat, így talán jobban megértjük mindkettőt.

Először nézzünk egy nagyon egyszerű példát hogy felfrissítsük is hogy hogy működnek a cilusok és a rekurzív függvények:

Faktoriális kiszámolása

Ciklus:

link

A ciklus kódjának végére érve bizonyos feltétel mellett visszaugrunk a ciklus kódjának elejére, de bizonyos elérhető változók értéke megváltozott.

Rekurzió:

link

Ebben az esetben a függvény végén bizonyos feltétel mellett visszaugrom a függvény kódjának elejére (meghívom a függvényt), de bizonyos elérhető változók (a függvény paraméterei) értéke megváltozott.

Ennél a példánál láthatóak a hasonlóságok a kettő között, de mik a különbségek?

Ciklus előnyei

A ciklus fontos előnye, hogy nem hoz egy új névteret létre: minden változó amit a függvényben használtunk, elérhető a cikluson belül is. Ezzel ellenben ha egy függvényt, akár önmagát, hívjuk, akkor ott csak azok a változók érhetőek el, amiket paraméterként átadunk.

Emiatt, ha pl. egy táblázatot akarunk kitölteni, akkor azt ciklussal nagyon egyszerű:

link

Ha ennek próbáljuk az analógiáját megcsinálni rekurzívan, meg lehet, de bonyolult kódot kapunk:

link

Látható, hogy az i és j változókat is a függvény paraméterévé kellett tenni, hogy elérhetőek legyenek a belső kódban.

Egy másik hátrány amit valamennyire mutat az előző kódrészlet, ha megnézzük a Python Tutor-on a futását, hogy ilyenkor a végére a függvény összes változata egyszerre fut. Ez nem minden programozási nyelven, és nem mindig, igaz, de ha igen, akkor jelentősen több memóriát foglal ez a változat, mint a ciklussal megírt változat.

Mivel rekurziónál a régebben kiszámolt értékek lehet hogy nem elérhetőek, ezért a gondtalanul megírt rekurzív kód lehet hogy fölöslegesen sokat számol. Példának itt van ez a rosszul megírt változata a fibonacci számok kiszámolásának:

link

Végigléptetve, a fibonacci_rekurziv(3) meg van hívva a 11-es és a 34-es lépésnél is, és mindkétszer újra ki van számolva. A matematikai gondolkodásmód szerint ugyan igaz hogy mindkét esetben a 3. fibonacci szám értékére van szükség, de programozásnál azt is végig kell gondolni hogy ez milyen lépésekkel fog járni.

Összességében a ciklus mindenképp könnyebben használható ha:

• sok változóra van szükség a kód belsejében
• egy táblázatot töltünk fel
• a ciklus sok egymástól független elemmel dolgozik

Olyan esetben is érdemesebb ciklust használni mint rekurziót, amikor a rekurzió mélysége (hány példánya fut a függvénynek egyszerre) nagyon megnőhetne, mert az a hatékonyságot csökkenti nagy memóriaigényével.

Rekurzió előnyei

Tekintsük a következő feladatot:

Egy k szám osztósora egy olyan pozitív egészekből álló számsor, ami k-val kezdődik, 1-el végződik, és a következő szám mindig az előző osztója. Pl. a 24, 12, 3, 1 az a 24 egy osztósora. Írjunk egy függvényt ami kiírja egy szám összes osztósorát.

Egy lehetséges megoldás rekurzióval:

link

Próbáljuk meg ugyanezt a megoldást reprodukálni ciklussal. Itt egy ilyen megoldás:

link

Ez a legegyszerűbb kód amit sikerült írnom, és még így is a kommentekkel együtt sem vagyok benne teljesen biztos hogy jól érthető. Itt van kommentek nélkül is, hogy látható legyen hogy mennyivel hosszabb és bonyolultabb:

def osztosor_ciklus(k):
    l = [k, 1]
    while 1:
        print l
        while len(l) > 1:
            l[-1] = l[-1] + 1
            if l[-1] == l[-2]:
                del l[-1]
            elif l[-2] % l[-1] == 0:
                l.append(1)
                break
        else:
            return

Ez egy olyan feladat, amire a rekurzió alkalmasabb. Amikor ciklussal csináljuk meg ugyanazt, akkor is vigyáznunk kell, hogy a lista hányadik eleménél éppen hol tartunk, mikor kell előre illetve visszalépnünk a listában. Ezek a rekurzív változatban a függvény hívásának és visszatérésének felelnek meg, így bizonyos mértékig "automatikusan" vannak kezelve.

De amit igazán fontos megérteni, hogy továbbra is a ciklusos kód a hatékonyabb. A rekurzív kód ugyan rövidebb, és a Python Tutor szerint kevesebb lépésből áll, de:

• Egyszerre a félig kész listának több másolata létezik a függvény több futó példányában.
• Maga a függvény több egyszerre futó példánya is memóriát fogyaszt, csökkenti a hatékonyságot.

Azonban ebben az esetben ez a felesleges munka nem lesz sokszorosa a szükséges munkának nagyobb esetekre se. Például úgyis a lista minden példányát ki kellett írni, azoknak mind létezni kell a függvény futása után, tehát az hogy menet közben több példány is létezik, az nem sokszorozza a memória igényt.

Viszont, a rekurzív kód könnyebben olvasható, és a működése könnyebben megérthető. Ez nem elvetendő szempont, mindenki a programozóként dolgozik, több időt tölt kód olvasásával, mint írásával.

Milyen esetben érdemes tehát rekurziót használni? Amikor érthetőbb kódot ad, és a hatékonyság vesztés nem jelentős, vagy nem számít. Néhány példa:

• Gráfok bejárása.
• Más olyan feladat, ahol a rekurzív változat egy ciklusban hívja önmagát.
• Olyan táblázatok kitöltése, ahol a táblázatnak végül csak néhány eleme számít. Ilyenkor úgynevezett letárolásos rekurziót használunk.
• Olyan problémáknál, ahol a kimenet maga rekurzív jellegű. Ilyen példa az osztósoros feladat, vagy fraktálok kirajzolása, különféle természetes folyamatok szimulációja.

Nézünk majd példákat a gyakorlaton.