Programozás alapjai - második felében 08-09; Mikhalkovich a
alapvető meghatározások
Ez az úgynevezett rekurzív definíció a tárgy keresztül ugyanazt a tárgyat.
Ebben a példában a rekurzív része a meghatározás "<Список> „” <Число> ”.
Megjegyzés: 1. A rekurzív definíció, hogy véges, meghatározza végtelen számú tárgyakat.
Megjegyezzük továbbá, hogy <Список> Úgy határozható meg másképp:
A meghatározás (1) bal rekurzív hívást. és (2) - Jobb rekurziót.
Megjegyzés 2. rekurzív definíció van szükség (.) Is jelen kell lennie, nem rekurzív rész.
Rekurzív definíció lehet közvetett.
az egyik ág a rekurzív definíciók említett tárgy, a meghatározása, amely viszont, az egyik ága határozza meg a forrás objektum.
Ebben a példában a közvetlen és közvetett rekurzív definíció.
A programozás rekurzív jelenti:
- az alprogramot is (közvetlen rekurzió)
- hívás egy másik alprogramot az alprogram ami a forrás (közvetett rekurzió)
Egyszerű példák segítségével rekurzió
Ha telefonál ez az eljárás rekurzív hurok. mert rekurzív hívás történik feltétel nélkül.
Következtetés. A rekurzív hurok még nem fordult elő, a rekurzív hívás kell megtörténnie nem feltétlenül, de néhány feltétel, hogy megváltozik minden, és néhány rekurzív hívás lesz hamis (ún folytatása feltétele rekurzió).
Mi kijavítjuk eljárások összhangban megállapította:
Amikor az úgynevezett p (0) jelenik:
Grafikailag rekurzív hívások képviseletében a következő:
Process egymást rekurzív hívások az alprogram maga az úgynevezett rekurzív származású.
A folyamat a visszatérés a rekurzív hívások hívják rekurzív vissza.
Ebben a példában a szám megjelenik a rekurzív származású (vagyis előre sorrendben).
Ugyanakkor a végzett tevékenységek fordított sorrendben, meg kell hívni a rekurzív vissza.
2. példa. visszavonul
A maximális mélysége rekurzív hívások hívják rekurzió mélységét.
Aktuális mélység az úgynevezett jelenlegi szintje rekurziót.
Megjegyzés. Minél nagyobb a mélység a rekurzió, annál több memóriát fölött.
Graphics rekurzív hívások
Egy kép már volt. Emlékezzünk arra, hogy:
Tekintsük részletesebben a hívás p (0) Eljárások
- Szoftververem - egy folyamatos területen rendelt memória a program, különösen a fogadó a hívott alprogramok.
- Mert minden egyes hívása a szubrutin köteget behelyezzük az aktivációs rekord (FOR), és amikor visszatér - eltávolítjuk a verem.
így a verem tulajdonképpen minden, a változó értékét i.
Megjegyzés: 1. Mivel minden rekurzív hívás verem mögé, a nagy mélység a rekurzió szoftvercsomag túlcsordulhat. és a program nem fog működni.
Ez fog történni gyorsabban, annál több a teljes összeg a formális paraméterek és a helyi változókat.
Ezért a következő kódot - nagyon rossz.
2. megjegyzés: Felső kihelyezési egy köteg költségek a lövés a köteget, valamint értéket rendelni a hivatalos paraméterek a stack elég nagyok.
Ezért, ha van egy egyszerű megoldás, hogy egy nem-rekurzív (ismétlődő), meg kell használni.
3. megjegyzés: Minden rekurzív helyettesíthető iteráció.
Példák a rekurzió
1. példa: Find n! = N (n - 1) (n - 2). 2 * 1
Nyilvánvaló, hogy meghatározzák n! lehet az alábbiak szerint:
Ezután az oldatot a következő:
Mindazonáltal megjegyezzük, hogy a visszatérési érték nincs definiálva n <0.
Legalább akkor cserélje ki a feltétel n = 0 és n <= 0. но, в таком случае, мы получим неверный результат, т.к. факториал вообще не определен для отрицательных чисел.
Nyilvánvaló, hogy szükség van, hogy ellenőrizze a helyességét jóváhagyási keresztül a bemeneti paraméter (Assert (n> = 0)). Hanem annak minden rekurzív hívás drága. Ezért, akkor „wrap” rekurzív rutin, valahogy így:
Rekurzió mélysége Ez az algoritmus egyenlő n-nel.
2. példa keresésben. Adunk egy rekurzív definíció:
A rekurzió mélysége:
- - a legjobb esetben
- - a legrosszabb
3. példa meghatározása a minimális elem a tömbben. meghatározhatja ezt az elemet, mint a minimális (egyik eleme egy sor minimális nélkül ez az elem). azaz rekurzív definíciója a következő:
Ezzel összhangban van a megoldás:
Rekurzió mélység n - 1.
Egyértelmű, hogy ez nem egy nagyon jó eredmény.
Jelentősen csökkenti a mélység, ha megnézzük a minimum körülbelül egyenlő részre között a tömbben. Ie meg kell osztani a tömb félbe, a megállapítás mindkét felében a minimális elemeket, és hasonlítsa össze őket. Keresés félig kész hasonlóképpen, és a megosztás történik, amíg nem lesz egy subarray elemet.
Ez lehet egy kicsit optimalizálni az algoritmus - ha subarray két elem, elég, hogy visszatérjen a minimális őket.
Most, hogy tudja az elemek száma nem elég: meg kell tudni keresni közül néhány esetében a tömbben. Ezért át paraméterként balra (L) és jobb (r) almátrixszá határt.
Adunk egy új rekurzív definíció:
A rekurzió mélységét egy ilyen algoritmus már nagyjából megegyezik (osztások száma).
Példa 4. Következtetés egyszerűen csatlakoztatva lineáris lista a képernyőn.
Emlékezzünk, hogy a lista így néz ki:
megoldás:
Mélység rekurzió egy lista hossza - 1
A rekurzió az úgynevezett terminál. ha a rekurzív hívás az utolsó egy alprogramban.
A végén a rekurzió leginkább könnyen átalakul egy iteratív algoritmus:
Proof zavershimosti rekurzió
Rekurzív eljárás, amellyel egy paraméter n.
Ha az átvizsgálás során rekurzív hívás n paraméter csökken hívásokat fogadni
Ha a rekurzió befejeződött ha n <= 0. то это служит доказательством завершимости рекурсии.
Valóban, minden következő szint a rekurzió n kisebb lesz.
Mivel n <= 0 рекурсивных вызовов нет, то число рекурсивных вызовов конечно.
Azzal érvelt, hogy a rekurzió zavershima, ez nem mindig lehetséges.
Példa.
Forma rekurzív rutinok
1. A művelet végrehajtása rekurzív származású
2. A művelet végrehajtása a rekurzív visszatérés
3. A művelet végrehajtása rekurzív származású és rekurzív visszatérés
4. Cascade rekurzió
Ez a rekurzió nevezzük kaszkád. mert Minden szubrutinhívás képes több rekurzív hívások (kaszkád).
5. Távoli rekurziót.
Egy példa a rekurzió a funkciója a távoli Ackerman.
Példák a jó és rossz rekurzió
Példa szegény rekurzió - Fibonacci
Fibonacci-számok által meghatározott rekurzív sorozat:
Mi már kiszámított őket használó ciklus. Talán rekurzív (rossz!) Megoldás:
Ez történik, ha hívja Fib (7).
fa rekurzív hívások
Mint látható, az azonos számok számított hányszor:
Javíthatja az algoritmus segítségével egy sor kezdetben nullákkal töltjük fel.
Amikor először kiszámítjuk FIB (n) töltse ki a megfelelő elem, és minden ezt követő - egyszerűen hozzáférünk az értékét. Ez a technika az úgynevezett memoization. azaz memorizálása részeredmények, hogy elkerüljék újraszámításuk.
Nyilvánvaló, hogy ez a módszer rendkívül hatástalan képest iteratív algoritmus mind a memóriában, és a munkaidő. Különösen, a számítás a rekurzió mélységét az n-Fibonacci száma n-1.
A rekurzív számítási módszere Fibonacci által épített egy iteratív algoritmussal
Emlékezzünk az iteratív keresési algoritmust n rendű Fibonacci számok:
Készítünk belőle egy rekurzív algoritmust, továbbítása minden rekurzív szubrutin a változók a, b, c, a változó minden egyes iteráció. Tény, hogy minden rekurzív hívás, mi teszi a cserét:
Rekurzív algoritmus által megvalósított ez a helyettesítés lesz:
Rekurzió ebben a példában - vége. Mint már említettük, ez könnyen pótolható iterációval, csak kapott az előző iterációs megoldás. Jó optimalizálása fordítóprogramok ezt automatikusan megteszi.
Egy példa a jó hasznát rekurzió - Hanoi tornyai
A feladat a következő:
Mivel három rúd. A földön n lemezek különböző sugarú, azzal a feltétellel, hogy nincs lemez nem nagyobb, mint a sugár a lemezen kisebb sugarú.
Szükséges kerekek mozgatni az első, hogy a harmadik rúd, egy második, feltéve, hogy:
- Egy lépés, akkor csak folytatni egy lemezre
- kisebb lemez kell maradnia nagyobb
Az ötlet az algoritmus a következő:
így Van egy egyszerű rekurzív megoldás:
quicksort
Quicksort algoritmus (fajta algoritmus „oszd meg és vlavstvuy”) két szakaszból áll:
1. kiválasztása egy elem a tömb és X szétválasztása tömb két részre úgy, hogy az első kapcsolja minden elemét <= x, а в о второй —>= X
2. Rekurzív alkalmazása bizonyos algoritmus a kapott részek
Nyilvánvaló, hogy az algoritmus gyorsabban fejti mint több egyenlő részre fogjuk osztani az array (ideális esetben - a felére minden alkalommal).
Ezért arra kell törekednünk, hogy válasszon ki egy elemet x olyan, hogy körülbelül a fele a tömb volt <= его, и, соответственно, вторая половина —>=. Másrészt, a kiválasztás a X kell egy sok időt és, legalábbis, nem függ a N - a tömb méretét).
Fogjuk használni a legegyszerűbb módja annak, hogy válassza ki az x - ahogy megteszi az első elem.
Következő animáció mutat példát alkalmazó algoritmus a tömb quicksort
Tekintsük az 1. fázis további részletek:
- A szétválasztás a tömb az említett fejrész 2 az index i és j.
- Az elején én fog mutatni az első elemet és mozgassa jobbra, és j - az utolsó, és mozgassa balra.
1. lépés.
Majd tolja előre, amíg az A [i] nem lesz> = x.
Tovább fog előre vissza j, amíg az A [j] nem <= x .
Jött a elemek A [i] és A [j]. akik „nincsenek a helyükön” (ne feledjük, hogy azt akarjuk, hogy szétszórja minden kisebb vagy egyenlő x balra elemeket, és nagyobb vagy egyenlő, - a jobb oldalon)
2. lépés.
Cserélni őket, és én is továbblapozáshoz egy elemet, és j - hátra, mint egy elem.
Megismételjük ezeket a lépéseket, amíg nem leszek> = j.
Az eredmény egy tömb A. van osztva 2 részből áll:
programkód
Aszimptotikus becslés az összetettsége
Tételezzük fel, hogy a tömb minden egyes alkalommal van osztva 2 egyenlő részre. Ez a legjobb megoldás.
A mélysége rekurzió ebben az esetben = log 2 n.
így kettéosztva megközelítően a fele. aszimptotikus bonyolultsága az általános algoritmus = Θ (n log n).
Elméletileg, ha bebizonyosodik, hogy átlagosan, ha nem pontosan osztható a felére, az aszimptotikus összetettsége megtartja képletű Θ (n log n).
Kérdés: Mi a bonyolultsága a legrosszabb esetben? Legrosszabb - amikor X választjuk a minimális (vagy maximális) elem. Ez történik (a mi esetünkben, mivel úgy döntünk, az első elem), ha a tömb már rendezve.
Ebben az esetben, ennek eredményeként a bomlási darabokra nagy részét fogják csökkent az 1. és a rekurzió mélységét rendezése eljárás egyenlő lesz.
Ezért a legrosszabb esetben = aszimptotikus bonyolultságát.
Jóváhagyása. Véletlen adatok, nincs algoritmus aszimptotikus összetettsége jobb, mint Θ (n log n) az átlagos.
Generálása permutációk
Az alapötlet a generáló permutációk az algoritmus a következő. A tömb hossza n, amely egy permutáció, akkor változtatni a utolsó eleme, és aztán rekurzívan ugyanezt a hossza a tömb n-1, majd vissza az átrendeződött elem a régi helyére. Ha a hossza a tömb elérésekor n = 1, akkor a csere nem kell semmit, és meg kell adni azokat a teljes tartalmát a tömb permutációs a képernyőn. Ilyen algoritmus lehetővé teszi, hogy létrehozzuk az összes permutációt, ami következik verbális rekurzív definíció: az utolsó látogatás minden eleme a jelen tömb, ami után a fennmaradó rész a tömb azonos algoritmus ismételhető.
Könnyen belátható, hogy a rekurzió mélysége n-1, és a szám a Eljáráshívásokat Perm n.
Generation összes részhalmazainak
Generation összes részhalmazok robin algoritmus. A rendezési algoritmusok mozognak az összes lehetőséget megfelelő lehetőség bizonyos műveleteket. Ebben az esetben egyszerűen megjeleníti az összes részhalmazát.