A lap 2015. február 11., 12:28-kori változata

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.

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:

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

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ő.

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.
• 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.