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

Bemutatkozás

• Eisenberger András
• Hívjatok Csirkének
• email: csirkeee@gmail.com

Python ismétlés

Aki nem 2014-ben hallgatta az Info1-et és úgy érzi lemaradása van, azok részére elérhetőek

• Az előző félév előadásainak anyagai: Informatika1-2014/eloadas3, Informatika1-2014/eloadas4
• Vagy akár a hivatalos (angol) Python tanító anyag: Python tutorial.

Mai órán még kb. elég az eloadas3 anyaga, ami kell az függvények definiálása, elágazások.

A Python nagyon népszerű nyelv, többek között jól átlátható szintaxisa miatt, és mivel viszonylag könnyű új platformokra is átültetni. Ennek köszönhető, hogy rengeteg eszköz és erőforrás elérhető hozzá az interneten. Csak egy példa a http://pythontutor.com, amit itt az előadás lapjain is használunk a kód részletes bemutatásához, de ti is használhatjátok saját teszteléshez.

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

Python-ban a kódban bárhol definiálható függvény a kódban, a def kulcsszóval. Egyelőre most arról az esetről beszélünk csak, amikor a fájl gyökerében van definiálva, nem másik függvényen belül.

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ó

Faktoriális kiszámolása

Ciklus:

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ó:

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ű:

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

Egy másik hátrány amit valamennyire mutat az előző kódrészlet, 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:

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, beleértve ha egy táblázatot töltünk fel, és annak a régebbi elemeiről van szó. Olyan esetben is érdemesebb használni mint a 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ódiaigényével.