Hogyan kell rekurzív függvényt tervezni? Hogyan kell debugolni?

"De ha papíron kell csinálni (vizsga)?"

Szoftvertervezés. Állapotgép diagram...stb..

Fontos tudni, hogy minden ami leírható ciklusokkal az leírható rekurzióval is és fordítva is igaz. Van ami rekurzióval van ami ciklusokkal egyszerűbb, persze ez emberenként is eltérő lehet bizonyos esetekben. Pl a Hanoi tornyai leprogramozása egyszerűbb rekurzióval. Mindig kell biztosítani hogy ne legyen végtelen hívási láncolat. Vagyis gondolnunk kell arra hasonlóan mint ciklusok esetén ott hogy mi a kilépési feltétel, itt hogy milyen feltétel garantálja azt hogy ne folytatódjon határtalanul a hívási lánc. Rekurzió lehet önrekurzió is, de nem csak ez hogy önmagát hívja meg a függvény hanem rekurzió minden ahol kör van a hívási láncban. Vagyis tervezhetjük segéd függvények használatával is a rekurziót.

Elemek szétválogatására rekurzív példa : [link]

Hogy lehet megtervezni? Gyakorolni, gyakorolni, gyakorolni !!!

@07:37

"Egy függvény attól (és akkor) lesz rekurzív, hogy (ha) önmagát hívja meg. Semmi mástól."

Ha kizárólag a rekurziók közül az önrekurzióról beszélünk akkor igen. Egyébként már írtam is előtted, hogy rekurzió minden ahol kör van a hívási láncban.

Ha például f1,f2,f3 függvények és f1 hívja f2 ami hívja f3-at. Az f3 pedig f1-et hívja ez is rekurzió.

"A rekurziónál egy dologra kell nagyon figyelni, a stack-re. Mert az nem végtelen, és minden új függvényhívásnál a stackre kerül a hívó állapota, egészen addig, amíg a hívóhoz vissza nem tér a végrehajtás, vagy amíg a stack túl nem csordul."

Egyrészt nem mondanám, hogy csak egy dologra kell nagyon figyelni, másrészt a fokozatosság elve miatt ne erre fókuszáljon először egy kezdő aki most ismerkedik a rekurzióval, hogy egyáltalán eszik vagy isszák. Meg nem olyan példákat kell csinálni egy kezdőnek rekurzívan hogy telerakja a stack-et vele - egy mai gépen, ne vicceljünk már -, kivéve akkor ha végtelen hívási láncolatba került.

Egyébként meg nem beszéltünk konkrétan prog. nyelvről, én írtam egybe egy példát, de ez az én dolgom. Úgy univerzálisan meg nem mondhatjuk "minden új függvényhívásnál a stackre kerül a hívó állapota", ez nem igaz. Vannak olyan problémák melyeket rekurzívan sokkal egyszerűbben meg lehet oldani mint ciklusokkal. Ha ezt kell hatékonyan megoldani (órabérbe is), többek között ezért találtak ki vannak a DSL (Domain Specific Language) domén specifikus prog nyelvek-et amiben adott feladatkör problémáit egyszerűbben meg lehet oldani. Ha rekurzióra kell akkor ajánlom a Haskell-t. Tisztán funkcionális, a lambda-kalkulus formális rendszeren alapszik. Sokkal hatékonyabban kioptimalizálja futás közben a stack kérdést szemben mintha bármely másba írtuk volna meg tisztán funkcionális paradigma szerint a kódot. Az egész egy állapotmentes rendszert alkot, nincsenek benne a prog. nyelvek értelmében vett változók.

"Egyébként már írtam is előtted, hogy rekurzió minden ahol kör van a hívási láncban."

Ez téves megállapítás, mert része lehet egy vagy több szekvencia is indirekt rekurziónak, de mégsem lesz rekurzív. De még maguk a rekurzív hívó után hívott függvények sem lesznek feltétlenül rekurzívak.

"másrészt a fokozatosság elve miatt ne erre fókuszáljon először egy kezdő aki most ismerkedik a rekurzióval,"

De, pedig erre kell figyelnie, mert ezt várják el tőle első körben, hogy a függvénye terminális-e? Ez fontosabb a függvény által visszaadott érték helyességétől is. Nem véletlenül.

"Úgy univerzálisan meg nem mondhatjuk "minden új függvényhívásnál a stackre kerül a hívó állapota", ez nem igaz. "

Hát, nem tudom, hogy te hol tanultad azt amit tudsz, de hogy nem jó helyen, az biztos.

Egy függvény lokális változói, visszatérési értéke és visszatérési címe, jelen idő szerint azon a stack-en foglal helyet, amit éppen ebből a célból hoztak létre.

"Ez téves megállapítás, mert része lehet egy vagy több szekvencia is indirekt rekurziónak, de mégsem lesz rekurzív. De még maguk a rekurzív hívó után hívott függvények sem lesznek feltétlenül rekurzívak."

Itt van tessék wiki oldal róla amiről beszéltem, én máshogy fogalmaztam meg saját szavaimmal, saját kútfőből, de tessék : Rekurzió típusai : közvetett, közvetlen.

[link]

"De, pedig erre kell figyelnie, mert ezt várják el tőle első körben, hogy a függvénye terminális-e? Ez fontosabb a függvény által visszaadott érték helyességétől is. Nem véletlenül."

Igen, de arra mondtam hogy , nem azt hogy lehet ha máshogy írta volna meg rekurzióval akkor kevesebb stack-et foglal. Nem kell kiforgatni a szavaimat.

"Hát, nem tudom, hogy te hol tanultad azt amit tudsz, de hogy nem jó helyen, az biztos.

Egy függvény lokális változói, visszatérési értéke és visszatérési címe, jelen idő szerint azon a stack-en foglal helyet, amit éppen ebből a célból hoztak létre."

Kezdő lehetsz. Ajánlom megismerni a Haskell-t, tisztán funkcionális programozási nyelv. Nincsenek benne a programozási nyelvek értelmében vett változók benne, de már említettem.