Kapcsolódó sorozat: Programozzunk Pascalban (109)

(75)

(30)

• 

  Programozás Pascalban: Eljárások használata - 14. rész, Rekurzív alprogramok - 1

  2010. május 18. 12:28:15 |

  Készítette: FlamingClaw

  Ebben a tippben a rekurzió fogalmát tisztázzuk, illetve azt, hogy milyen elvárásoknak kell megfelelnie egy rekurzív rutinnak. Rekurzív eljárásokat készítünk, és megfigyeljük hogyan működnek.

  

• Amire szükségünk lesz

  Pascal

• Rekurzív alprogramok - 1

  Az alprogramokat rutinnak is szokás nevezni. Egy alprogramot rekurzívnak nevezzük, ha saját magát hívja meg. Kétféle rekurzió létezik: közvetett és közvetlen. A közvetlen az, amikor a rutin közvetlenül saját magát hívja meg, tehát önrekurzió. Ilyenkor az eljárás deklarációs részében az eljárás a saját azonosítójára hivatkozik és újból betöltődik a verembe.
  A közvetett rekurziónál a rutin közvetve hívja meg saját magát egy másik rutinon keresztül (kölcsönös rekurzió).
  Egy feladat akkor rekurzív, ha a feladat megoldásához vezető lépések során találunk egy egyszerűbb esetet, melynek során a megoldás magától értetődik. Vagy ha találunk egy olyan ismételt egyszerűsítési folyamatot, amelynek alapján eljuthatunk a legegyszerűbb esethez. Minden egyes lépésnél felfételezzük, hogy a következő lépésnek megvan a megoldása.
  Egy rekurzív feladathoz szükséges valami, ami a hívások során állandóan változik és elvileg elérhet egy küszöböt. Be kell állítanunk egy leállító (bázis) feltételt, ha ezt elérte, nem történik több rekurzív hívás. Végtelen rekurziót nem lehet előállítani, mert előbb-utóbb megtelik a verem. Kell még egy olyan utasítás, ami ezt a „valamit” a küszöb felé viszi. Minden rekurzív feladatnak létezik iteratív megoldása is.
  

Statisztika