Informatika2-2015/Eloadas 2 Python-2 Rekurzio es Ciklus
1. sor: | 1. sor: | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==Függvényhívás példa== | ==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: | |
<wikiframe width="800" height="500" frameborder="1" src="http://pythontutor.com/iframe-embed.html#code=def+negyzet(k)%3A%0A++++return+k*k%0A%0Adef+negyzetel(l)%3A%0A++++for+i+in+range(len(l))%3A%0A++++++++l%5Bi%5D+%3D+negyzet(l%5Bi%5D)%0A++++return+l%0A++++%0Aszamok+%3D+%5B2,+3,+4%5D%0Aprint+negyzetel(szamok)&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&drawParentPointers=false&textReferences=false&showOnlyOutputs=false&py=2&rawInputLstJSON=%5B%5D&curInstr=0&codeDivWidth=350&codeDivHeight=400"/> | <wikiframe width="800" height="500" frameborder="1" src="http://pythontutor.com/iframe-embed.html#code=def+negyzet(k)%3A%0A++++return+k*k%0A%0Adef+negyzetel(l)%3A%0A++++for+i+in+range(len(l))%3A%0A++++++++l%5Bi%5D+%3D+negyzet(l%5Bi%5D)%0A++++return+l%0A++++%0Aszamok+%3D+%5B2,+3,+4%5D%0Aprint+negyzetel(szamok)&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&drawParentPointers=false&textReferences=false&showOnlyOutputs=false&py=2&rawInputLstJSON=%5B%5D&curInstr=0&codeDivWidth=350&codeDivHeight=400"/> | ||
24. sor: | 10. sor: | ||
=Ciklus vagy rekurzió= | =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== | ==Faktoriális kiszámolása== | ||
56. sor: | 46. sor: | ||
[http://pythontutor.com/visualize.html#code=def+szorzotabla_rekurziv_belso(i,+j,+a,+b)%3A%0A++++print+i*j,%0A++++if+j+%3C+b%3A%0A++++++++szorzotabla_rekurziv_belso(i,+j%2B1,+a,+b)%0A++++elif+i+%3C+a%3A%0A++++++++print%0A++++++++szorzotabla_rekurziv_belso(i%2B1,+1,+a,+b)%0A%0Adef+szorzotabla_rekurziv(a,+b)%3A%0A++++szorzotabla_rekurziv_belso(1,+1,+a,+b)%0A++++++++%0Aszorzotabla_rekurziv(3,+4)&mode=display&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&textReferences=false&py=2&rawInputLstJSON=%5B%5D&curInstr=0 link] | [http://pythontutor.com/visualize.html#code=def+szorzotabla_rekurziv_belso(i,+j,+a,+b)%3A%0A++++print+i*j,%0A++++if+j+%3C+b%3A%0A++++++++szorzotabla_rekurziv_belso(i,+j%2B1,+a,+b)%0A++++elif+i+%3C+a%3A%0A++++++++print%0A++++++++szorzotabla_rekurziv_belso(i%2B1,+1,+a,+b)%0A%0Adef+szorzotabla_rekurziv(a,+b)%3A%0A++++szorzotabla_rekurziv_belso(1,+1,+a,+b)%0A++++++++%0Aszorzotabla_rekurziv(3,+4)&mode=display&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&textReferences=false&py=2&rawInputLstJSON=%5B%5D&curInstr=0 link] | ||
− | 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. | + | 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: | 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: | ||
65. sor: | 57. sor: | ||
Végigléptetve, a <code>fibonacci_rekurziv(3)</code> 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. | Végigléptetve, a <code>fibonacci_rekurziv(3)</code> 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 | + | Ö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== | ==Rekurzió előnyei== | ||
83. sor: | 79. sor: | ||
[http://pythontutor.com/visualize.html#code=def+osztosor_ciklus(k)%3A%0A++++l+%3D+%5Bk,+1%5D%0A++++while+1%3A%0A++++++++%23+Kiirjuk+az+uj+osztosort%0A++++++++print+l%0A++++++++while+len(l)+%3E+1%3A%0A++++++++++++%23+Noveljuk+az+utolso+elemet%0A++++++++++++l%5B-1%5D+%3D+l%5B-1%5D+%2B+1%0A++++++++++++%23+Ha+az+utolso+elem+megegyezik+az%0A++++++++++++%23+utolso+elottivel,+vissza+kell+lepnunk,%0A++++++++++++%23+roviditeni+a+listat%0A++++++++++++if+l%5B-1%5D+%3D%3D+l%5B-2%5D%3A%0A++++++++++++++++del+l%5B-1%5D%0A++++++++++++%23+Ha+az+utolso+elem+az+utolso+elotti%0A++++++++++++%23+osztoja,+a+vegere+1-est+teve+uj%0A++++++++++++%23+osztosort+talaltunk%0A++++++++++++elif+l%5B-2%5D+%25+l%5B-1%5D+%3D%3D+0%3A%0A++++++++++++++++l.append(1)%0A++++++++++++++++break%0A++++++++%23+Amikor+a+lista+1+elemure+rovidult,+mindent%0A++++++++%23+megtalaltunk.%0A++++++++else%3A%0A++++++++++++return%0A%0Aosztosor_ciklus(12)&mode=display&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&textReferences=false&py=2&rawInputLstJSON=%5B%5D&curInstr=0 link] | [http://pythontutor.com/visualize.html#code=def+osztosor_ciklus(k)%3A%0A++++l+%3D+%5Bk,+1%5D%0A++++while+1%3A%0A++++++++%23+Kiirjuk+az+uj+osztosort%0A++++++++print+l%0A++++++++while+len(l)+%3E+1%3A%0A++++++++++++%23+Noveljuk+az+utolso+elemet%0A++++++++++++l%5B-1%5D+%3D+l%5B-1%5D+%2B+1%0A++++++++++++%23+Ha+az+utolso+elem+megegyezik+az%0A++++++++++++%23+utolso+elottivel,+vissza+kell+lepnunk,%0A++++++++++++%23+roviditeni+a+listat%0A++++++++++++if+l%5B-1%5D+%3D%3D+l%5B-2%5D%3A%0A++++++++++++++++del+l%5B-1%5D%0A++++++++++++%23+Ha+az+utolso+elem+az+utolso+elotti%0A++++++++++++%23+osztoja,+a+vegere+1-est+teve+uj%0A++++++++++++%23+osztosort+talaltunk%0A++++++++++++elif+l%5B-2%5D+%25+l%5B-1%5D+%3D%3D+0%3A%0A++++++++++++++++l.append(1)%0A++++++++++++++++break%0A++++++++%23+Amikor+a+lista+1+elemure+rovidult,+mindent%0A++++++++%23+megtalaltunk.%0A++++++++else%3A%0A++++++++++++return%0A%0Aosztosor_ciklus(12)&mode=display&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&textReferences=false&py=2&rawInputLstJSON=%5B%5D&curInstr=0 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ő. | + | 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: |
+ | |||
+ | <python>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</python> | ||
+ | |||
+ | 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: | 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: | ||
96. sor: | 108. sor: | ||
* Gráfok bejárása. | * Gráfok bejárása. | ||
* Más olyan feladat, ahol a rekurzív változat egy ciklusban hívja önmagát. | * 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 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. | * 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. | Nézünk majd példákat a gyakorlaton. |
A lap 2015. február 17., 22:41-kori változata
Tartalomjegyzék |
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:
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:
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:
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:
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:
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ő. 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.