Et mitte kirjutada ühte tohutut artiklit, kus on arvukalt näiteid rekursiooni kohta C++ keeles, kirjutan siia veel ühe näite rekursioonist. Üldiselt võivad need, kes mõistavad otsese rekursiooni põhitõdesid ja kasutamist oma funktsioonides, selle materjali vahele jätta. Siin on näide rekursiooni kasutamisest, nagu artiklis Funktsioonid C++ keeles algajatele. Rekursioon

Ülesanne 1 – kasutades rekursiooni, kuvage arvu faktoriaal vahemikus 1 kuni N
Koodi kirjutamine
=============================
ETAPP nr 1 kirjutada tühi programm
=============================

#kaasa

#kaasa

#kaasa

int main()
{
system("cls");

getch();
tagasi 0 ;
}

Tühi programm on loodud, arvan, et pole vaja kommenteerida
STAGE nr 2 kirjutame kirjutame rekursiivse funktsiooni enda
=========================================

#kaasa

#kaasa

#kaasa

//Meie rekursiivne funktsioon
tegelikult (int N)
{

//0! = 1, 1!=1, 2!=2, 3!=6... Sest esimesed 2 numbrit on ühed ja ei ole ranges järjestuses, sunnime seda punkti koodis

kui n<2 return 1 ;
muidu tagasta n * fakt (n–1) //siin kutsub funktsioon ise välja

}

int main()
{
system("cls");
cout<//Kõnepunkt rekursiivne funktsioon. Faktoriaali 10 trükkimine ekraanile
getch();
tagasi 0 ;
}
ddd
============

Peatükk C++ rekursiooniprogrammis
tagasi n* fakt (n–1)

Meie funktsioon arvutab eelmise väärtuse saamiseks ümber. Tegelik väärtus on parameeter, kellele edastatakse n funktsiooni kutsumise kohast. Meie funktsiooni kutsumise mõte on kutsuda see programmi põhiplokist. Meie puhul kutsume seda funktsiooni järgi int main()
Miks ma ei kirjuta mitte järgmist, vaid eelmist? Kui arvud on korrutatud, siis esimene 0 * 1 on siin meie praegune väärtus 1 ja null on eelmine arvutusväärtus. See on kogu rekursiooni olemus, praeguse väärtuse arvutame eelmise väärtuse abil, samas kui eelmine väärtus saadakse sama arvutuse abil. Kompilaator ise arvutab eelmise väärtuse ja salvestab selle väärtuse mällu. Kõik, mida me peame tegema, on anda juhiseid. . Tänu sellele kompilaatorite funktsioonile puutub funktsioon kokku enda kutsumisjuhisega (meie puhul fakt (n–1) )ei kirjuta üle antud parameetrit n funktsiooni arvutamiseks. Parameeter edastati kasutajale n see jääb mällu. Sel juhul on täiendavalt määratletud veel üks mäluala, milles meie rekursiivne funktsioon sooritab rekursiivseid arvutusi, et saada eelmine tulemus.

Andku programmeerijad mulle sellise näritud kohtuotsuse andeks. Umbes nii tajuvad algajad rekursiooni.

Loodan, et see algajatele mõeldud C++ ajaveeb oli kellelegi kasulik ja aitas kellelgi mõista C++ rekursiivse funktsiooni põhikontseptsiooni

Märkus. Selles artiklis, nagu ka eelmises, arvutasin ma mitte 1-st N-ni, vaid programmi sees sisestatud väärtuse järgi. Asi on selles, et ma ei tahtnud kirjutada täiendavat koodirida ja eeldasin, et kasutaja on andmete sisestamise ja nende ekraanil kuvamisega juba hästi kursis.

Tere Habrahabr!

Selles artiklis räägime rekursiooniprobleemidest ja nende lahendamisest.

Lühidalt rekursioonist

Rekursioon on üsna tavaline nähtus, mis ei esine mitte ainult teaduse valdkondades, vaid ka igapäevaelus. Näiteks Droste efekt, Sierpinski kolmnurk jne. Üks viis rekursiooni nägemiseks on suunata veebikaamera arvutimonitori ekraanile, loomulikult pärast selle sisselülitamist. Seega salvestab kaamera arvutiekraani pildi ja kuvab selle sellel ekraanil, see on midagi suletud ahela taolist. Selle tulemusena näeme midagi tunneliga sarnast.

Programmeerimises on rekursioon tihedalt seotud funktsioonidega, just tänu funktsioonidele on programmeerimises olemas selline asi nagu rekursioon ehk rekursiivne funktsioon. Lihtsamalt öeldes on rekursioon funktsiooni (meetodi) osa määratlus iseenda kaudu, see tähendab, et see on funktsioon, mis kutsub ennast otse (oma kehas) või kaudselt (teise funktsiooni kaudu).

Rekursioonist on palju räägitud. Siin on mõned head ressursid:

• Rekursioon ja rekursiivsed probleemid. Rekursiooni rakendusvaldkonnad

Eeldatakse, et lugeja on rekursiooniga teoreetiliselt tuttav ja teab, mis see on. Selles artiklis pöörame rohkem tähelepanu rekursiooniprobleemidele.

Ülesanded

Rekursiooni õppimisel on kõige tõhusam viis rekursiooni mõistmiseks probleemide lahendamine.

Kuidas lahendada rekursiooniprobleeme?

Kõigepealt peate mõistma, et rekursioon on omamoodi liialdus. Üldiselt võib öelda, et kõike iteratiivselt lahendatavat saab lahendada rekursiivselt ehk rekursiivse funktsiooni abil.

võrgust

Iga rekursiivsel kujul rakendatud algoritmi saab iteratiivsel kujul ümber kirjutada ja vastupidi. Jääb küsimus, kas see on vajalik ja kui tõhus see on.

Selle õigustamiseks võib tuua järgmised argumendid.

Alustuseks võime meenutada rekursiooni ja iteratsiooni määratlusi. Rekursioon on andmetöötluse korraldamise viis, mille käigus programm kutsub ennast otse või teiste programmide abil. Iteratsioon on andmetöötluse korraldamise viis, kus teatud toiminguid korratakse mitu korda, ilma et see tooks kaasa rekursiivseid programmikutseid.

Pärast seda võime järeldada, et need on vastastikku vahetatavad, kuid mitte alati samade kuludega ressursside ja kiiruse osas. Selle põhjenduseks võime tuua järgmise näite: on funktsioon, milles teatud algoritmi organiseerimiseks on tsükkel, mis sooritab toimingute jada sõltuvalt loenduri hetkeväärtusest (see ei pruugi sõltuda see). Kuna tsükkel on olemas, tähendab see, et keha kordab toimingute jada - tsükli iteratsioone. Saate liigutada toimingud eraldi alamprogrammi ja edastada sellele loenduri väärtuse, kui see on olemas. Alamprogrammi täitmise lõppedes kontrollime tsükli täitmise tingimusi ja kui see on tõene, jätkame alamprogrammi uue kutsega, kui see on vale, lõpetame täitmise. Sest Panime kogu tsükli sisu alamprogrammi, mis tähendab, et alamprogrammi on paigutatud ka tsükli täitmise tingimus ning selle saab kätte funktsiooni tagastusväärtuse, viitega edastatavate parameetrite või alamprogrammile pointeriga , aga ka globaalseid muutujaid. Lisaks on lihtne näidata, et tsüklist antud alamprogrammi kõne saab hõlpsasti teisendada alamprogrammi enda kõneks või mittekõneks (väärtuse tagastamine või lihtsalt töö lõpetamine), juhindudes teatud tingimustest (neist, mis olid varem tsükliseisundis). Kui nüüd vaadata meie abstraktset programmi, siis näeb see umbkaudu välja nagu väärtuste edastamine alamprogrammile ja nende kasutamine, mida alamprogramm selle lõppedes muudab, s.t. asendasime iteratiivse tsükli antud algoritmi lahendamiseks alamprogrammi rekursiivse kutsega.

Iteratiivsele lähenemisele rekursiooni toomise ülesanne on sümmeetriline.

Kokkuvõtteks võime väljendada järgmisi mõtteid: iga lähenemisviisi jaoks on oma ülesannete klass, mille määravad konkreetse ülesande konkreetsed nõuded.

Selle kohta saate lisateavet

Nii nagu loendusel (tsüklil), peab ka rekursioonil olema peatustingimus – põhijuhtum (muidu, nagu tsükkelgi, töötab rekursioon igavesti – lõpmatu). See tingimus on juhtum, milleni rekursioon läheb (rekursiooni samm). Igal etapil kutsutakse välja rekursiivne funktsioon, kuni järgmine väljakutse käivitab põhitingimuse ja rekursioon peatub (õigemini naaseb viimase funktsioonikutseni). Kogu lahendus taandub põhijuhtumi lahendamisele. Juhul, kui keerulise probleemi lahendamiseks (mitte põhijuhtumi) kutsutakse välja rekursiivne funktsioon, tehakse rida rekursiivseid väljakutseid või samme, et probleem lihtsamaks muuta. Ja nii edasi, kuni saame põhilahenduse.

Seega koosneb rekursiivne funktsioon

• Peatustingimus või põhijuhtum
• Jätkutingimus või rekursioonisamm on viis probleemi taandamiseks lihtsamatele.

Vaatame seda faktoriaali leidmise näitel:

Avalik klass Lahendus ( public static int recursion(int n) ( // väljumise tingimus // Põhijuhtum // millal lõpetada rekursiooni kordamine? if (n == 1) ( return 1; ) // Rekursiooni samm / rekursiivne tingimus tagastamine recursion(n - 1) * n ) public static void main(String args) ( System.out.println(recursion(5)); // rekursiivse funktsiooni kutsumine )

Siin on põhitingimus tingimus, kui n=1. Kuna me teame, et 1!=1 ja arvutada 1! me ei vaja midagi. Arvutage 2! saame kasutada 1!, st. 2!=1!*2. Arvutage 3! vajame 2!*3... N arvutamiseks! vajame (n-1)!*n. See on rekursiooni samm. Teisisõnu, arvu n faktoriaalväärtuse saamiseks piisab eelmise arvu faktoriaalväärtuse korrutamisest n-ga.

Sildid:

• rekursioon
• ülesandeid
• java

Lisa sildid

Rekursioon on siis, kui alamprogramm kutsub end ise. Sellise algoritmilise disainiga esimest korda silmitsi seistes kogeb enamik inimesi teatud raskusi, kuid vähese harjutamisega muutub rekursioon teie programmeerimisarsenalis arusaadavaks ja väga kasulikuks tööriistaks.

1. Rekursiooni olemus

Protseduur või funktsioon võib sisaldada väljakutseid teistele protseduuridele või funktsioonidele. Protseduur võib ka ennast nimetada. Siin pole mingit paradoksi – arvuti täidab järjestikku ainult neid käske, mida ta programmis kohtab, ja kui ta kohtab protseduurikutset, hakkab ta lihtsalt seda protseduuri täitma. Pole tähtis, milline protseduur andis selleks käsu.

Rekursiivse protseduuri näide:

Protseduur Rec(a: täisarv); alustada, kui a>

Mõelgem, mis juhtub, kui põhiprogrammis tehakse väljakutse näiteks kujul Rec(3). Allpool on vooskeem, mis näitab avalduste täitmise järjekorda.

Riis. 1. Rekursiivse protseduuri plokkskeem.

Protseduuri Rec kutsutakse välja parameetriga a = 3. See sisaldab kutset protseduurile Rec parameetriga a = 2. Eelmine väljakutse pole veel lõppenud, seega võite ette kujutada, et luuakse teine ​​protseduur ja esimene ei lõpeta oma tööd enne see lõpeb. Kutsumisprotsess lõpeb, kui parameeter a = 0. Sel hetkel käivitatakse korraga 4 protseduuri eksemplari. Nimetatakse samaaegselt sooritatud protseduuride arvu rekursiooni sügavus.

Neljas protseduur nimega (Rec(0)) prindib numbri 0 ja lõpetab töö. Pärast seda naaseb kontroll selle kutsunud protseduuri juurde (Rec(1)) ja prinditakse number 1 Ja nii edasi, kuni kõik protseduurid on lõpetatud. Algses kõnes trükitakse neli numbrit: 0, 1, 2, 3.

Veel üks visuaalne pilt toimuvast on näidatud joonisel fig. 2.

Riis. 2. Rec-protseduuri täitmine parameetriga 3 seisneb Rec-protseduuri täitmises parameetriga 2 ja numbri 3 printimises. Protseduuri Rec täitmine parameetriga 2 koosneb omakorda protseduuri Rec täitmisest parameetriga 1 ja numbri 2 printimisest. .

Iseseisva harjutusena mõelge, mis juhtub, kui helistate Rec(4). Mõelge ka sellele, mis juhtuks, kui kutsuksite välja Rec2(4) protseduuri allpool, kusjuures operaatorid on vastupidised.

Protseduur Rec2(a: täisarv); alustada writeln(a);

kui a>0, siis Rec2(a-1); lõpp;

Pange tähele, et nendes näidetes on rekursiivne kõne tingimuslause sees. See on vajalik tingimus, et rekursioon kunagi lõppeks. Pange tähele ka seda, et protseduur kutsub end välja teistsuguse parameetriga kui see, millega seda kutsuti. Kui protseduur ei kasuta globaalseid muutujaid, siis on see ka vajalik, et rekursioon ei jätkuks lõputult. Võimalik on veidi keerulisem skeem: funktsioon A kutsub funktsiooni B, mis omakorda kutsub A. Seda kutsutakse kompleksne rekursioon

Protseduur A(n: täisarv); (Esimese protseduuri kirjeldus (päis) edasi) protseduur B(n: täisarv); (Teise protseduuri kirjeldus edasi) protseduur A(n: täisarv); (Protseduuri A täielik kirjeldus) begin writeln(n);

B(n-1); lõpp; protseduur B(n: täisarv); (Protseduuri B täielik kirjeldus) begin writeln(n);

kui n

Protseduuri B edasideklaratsioon võimaldab selle välja kutsuda protseduurist A. Protseduuri A edasideklaratsioon ei ole selles näites nõutav ja see lisatakse esteetilistel põhjustel.

Kui tavalist rekursiooni võib võrrelda meieoborosega (joonis 3), siis kompleksse rekursiooni kujundi saab ammutada kuulsast lasteluuletusest, kus “Hundid kartsid ja sõid üksteist”. Kujutage ette, et kaks hunti söövad üksteist ja saate aru keerulisest rekursioonist.

Riis. 3. Ouroboros – madu, kes õgib enda saba. Joonis Theodore Pelecanose (1478) alkeemilisest traktaadist "Synosius".

Riis. 4. Kompleksne rekursioon.

3. Silmuse simuleerimine rekursiooni abil

Kui protseduur kutsub ennast ise, siis sisuliselt käivitatakse selles sisalduvad juhised uuesti sarnaselt tsükliga. Mõned programmeerimiskeeled ei sisalda üldse silmuskonstruktsioone, jättes programmeerijad korraldama kordusi rekursiooni abil (näiteks Prolog, kus rekursioon on programmeerimise põhitehnika).

Näiteks simuleerime for-tsükli toimimist. Selleks vajame sammuloenduri muutujat, mida saab realiseerida näiteks protseduuri parameetrina.

Näide 1. Protseduur LoopImitation(i, n: täisarv); (Esimene parameeter on sammuloendur, teine ​​parameeter on sammude koguarv) begin writeln("Tere N ", i); //Siin on kõik juhised, mida korratakse, kui i Kutse vormis LoopImitation(1, 10) tulemuseks on käskude täitmine kümme korda loenduri muutumisel 1-lt 10-le.

antud juhul
trükitakse:
…
Tere N1

Tere N2

Tere N10

Üldiselt ei ole raske näha, et protseduuri parameetrid on loenduri väärtuste muutmise piirid.

Saate rekursiivse kõne ja korduvaid juhiseid vahetada, nagu järgmises näites.

Sel juhul toimub enne käskude täitmist rekursiivne protseduurikutse. Protseduuri uus eksemplar kutsub ka esmalt teise eksemplari ja nii edasi, kuni jõuame loenduri maksimaalse väärtuseni. Alles pärast seda täidab viimane väljakutsutud protseduuridest oma käsud, siis eelviimane täidab oma juhiseid jne. LoopImitation2(1, 10) kutsumise tulemuseks on tervituste trükkimine vastupidises järjekorras:

Tere N10
…
Tere N1

Kui kujutame ette rekursiivselt kutsutud protseduuride ahelat, siis näites 1 läbime selle varasemalt nimetatud protseduuridest hilisemate juurde. Näites 2 vastupidi, hilisemast varasemaks.

Lõpuks saab rekursiivse kõne paigutada kahe juhiste ploki vahele. Näiteks:

Protseduur LoopImitation3(i, n: täisarv); begin writeln("Tere N ", i); (Esimene juhiste plokk võib asuda siin), kui i

Siin täidetakse esimese ploki käsud esmalt järjestikku, seejärel teise ploki käsud vastupidises järjekorras. LoopImitation3(1, 10) kutsumisel saame:

antud juhul
…
Tere N1
Tere N1
…
Tere N1

Sama asja tegemiseks ilma rekursioonita kuluks kaks silmust.

Saate ära kasutada asjaolu, et sama protseduuri osade täitmine on aja jooksul jaotatud. Näiteks:

Näide 3: arvu teisendamine kahendarvuks.

Kahendarvu numbrite saamine, nagu teada, toimub jäägiga jagamisel arvusüsteemi 2 alusega. Kui arv on olemas, siis on selle kahendarvu viimane number võrdne

Võttes täisarvu osa jagamisest 2-ga:

saame arvu, millel on sama binaarne esitus, kuid ilma viimase numbrita. Seega piisab ülaltoodud kahe toimingu kordamisest, kuni järgmine jagamisväli saab täisarvu, mis on võrdne 0-ga. Ilma rekursioonita näeb see välja järgmine:

Kuigi x>0 alustage c:=x mod 2;

x:=x div 2;

kirjuta(c); lõpp;

Siin on probleem selles, et binaarse esituse numbrid arvutatakse vastupidises järjekorras (viimased enne). Tavakujul numbri printimiseks peate meeles pidama kõik massiivi elementide numbrid ja printima need eraldi tsüklina.

Üldiselt me ​​võitu ei saanud. Binaarse esituse numbrid salvestatakse kohalikesse muutujatesse, mis on rekursiivse protseduuri iga jooksva eksemplari jaoks erinevad. See tähendab, et mälu ei olnud võimalik säästa. Vastupidi, me raiskame lisamälu paljude kohalike muutujate x salvestamiseks. See lahendus tundub mulle aga ilus.

4. Korduvad seosed. Rekursioon ja iteratsioon

Vektorite jada on antud kordusrelatsiooniga, kui on antud esialgne vektor ja järgneva vektori funktsionaalne sõltuvus eelmisest

Kordusseoste abil arvutatud suuruse lihtne näide on faktoriaal

Järgmise faktoriaali saab arvutada eelmisest järgmiselt:

Märkuse kasutuselevõtmisega saame seose:

Valemist (1) saadud vektoreid saab tõlgendada muutujate väärtuste kogumina. Seejärel koosneb jada vajaliku elemendi arvutamine nende väärtuste korduvast värskendamisest. Eelkõige faktoriaali puhul:

X: = 1; i:= 2 kuni n puhul tee x:= x * i; writeln(x);

Iga selline värskendus (x:= x * i) kutsutakse välja iteratsioon, ja iteratsioonide kordamise protsess on iteratsioon.

Pangem siiski tähele, et seos (1) on jada puhtalt rekursiivne definitsioon ja n-nda elemendi arvutamine on tegelikult funktsiooni f korduv võtmine iseendast:

Eelkõige võib faktoriaali jaoks kirjutada:

Funktsioon Faktoriaalne(n: täisarv): täisarv; algab, kui n > 1, siis Faktoriaalne:= n * Faktoriaal(n-1) else Faktoriaal:= 1; lõpp;

Tuleb mõista, et funktsioonide kutsumine toob kaasa täiendavaid üldkulusid, nii et esimene variant faktoriaali arvutamiseks on veidi kiirem. Üldiselt töötavad iteratiivsed lahendused kiiremini kui rekursiivsed.

Enne olukordade juurde asumist, kus rekursioon on kasulik, vaatame veel ühte näidet, kus seda ei tohiks kasutada.

Vaatleme korduvate suhete erijuhtu, kui jada järgmine väärtus ei sõltu mitte ühest, vaid mitmest eelmisest väärtusest korraga. Näiteks on kuulus Fibonacci jada, kus iga järgmine element on kahe eelmise summa:

"Eesmise" lähenemisviisi abil saate kirjutada:

Funktsioon Fib(n: täisarv): täisarv; alusta, kui n > 1, siis Fib:= Fib(n-1) + Fib(n-2) else Fib:= 1; lõpp;

Iga Fib-kõne loob endast kaks koopiat, iga koopia loob veel kaks ja nii edasi. Operatsioonide arv suureneb arvuga n eksponentsiaalselt, kuigi iteratiivse lahenduse puhul lineaarne sisse n operatsioonide arv.

Tegelikult õpetab ülaltoodud näide meile, et mitte MILLAL vastasel juhul ei tohiks rekursiooni kasutada KUIDAS seda ei tohiks kasutada. Lõppude lõpuks, kui on olemas kiire iteratiivne (silmuspõhine) lahendus, siis saab sama tsüklit realiseerida rekursiivse protseduuri või funktsiooni abil. Näiteks:

// x1, x2 – algtingimused (1, 1) // n – vajaliku Fibonacci arvufunktsiooni arv Fib(x1, x2, n: integer): täisarv; var x3: täisarv; alusta, kui n > 1, siis alusta x3:= x2 + x1;

x1:= x2;

x2:= x3; Fib:= Fib(x1, x2, n-1); end else Fib:= x2; lõpp; Siiski on eelistatud iteratiivsed lahendused. Küsimus on selles, millal peaks sel juhul kasutama rekursiooni?Ükskõik milline rekursiivsed protseduurid ja funktsioonid, mis sisaldavad vaid ühte rekursiivset kõnet iseendale, on kergesti asendatavad iteratiivsete tsüklitega. Et saada midagi, millel pole lihtsat mitterekursiivset vastet, peate kasutama protseduure ja funktsioone, mis kutsuvad end kaks või enam korda. Sel juhul ei moodusta kutsutud protseduuride komplekt enam ahelat, nagu joonisel fig. 1, vaid terve puu. Probleeme on laias klassis, kui

arvutusprotsess

tuleks korraldada nii. Just nende jaoks on rekursioon kõige lihtsam ja

loomulikul viisil

lahendusi. 5. Puud Ennast rohkem kui üks kord nimetavate rekursiivsete funktsioonide teoreetiline alus on puid uuriv diskreetse matemaatika haru. 5.1. Põhimääratlused. Puude kujutamise viisid
Definitsioon:
nimetame lõplikuks hulgaks T, mis koosneb ühest või mitmest sõlmest, nii et:

a) Sellel puul on üks spetsiaalne sõlm, mida nimetatakse juureks. b) Ülejäänud sõlmed (v.a juur) sisalduvad paarikaupa mitteühendatud alamhulkades, millest igaüks on omakorda puu. Puid kutsutakse alampuud

sellest puust.

Joonisel fig. Joonisel 3 on kujutatud seitsme sõlmega puu. Kuigi tavalised puud kasvavad alt üles, on kombeks neid joonistada vastupidi. Kui joonistada diagrammi käsitsi, on see meetod ilmselgelt mugavam. Selle ebakõla tõttu tekib mõnikord segadus, kui öeldakse, et üks sõlm asub teisest kõrgemal või all. Sel põhjusel on kirjeldamisel mugavam kasutada kasutatud terminoloogiat sugupuud, kutsudes juure esivanematele lähemaid sõlme ja kaugemaid sõlmi järeltulijateks.

Puu saab graafiliselt kujutada mõnel muul viisil. Mõned neist on näidatud joonisel fig. 4. Definitsiooni järgi on puu pesastatud hulkade süsteem, kus need hulgad kas ei ristu või sisalduvad täielikult üksteises. Selliseid komplekte saab kujutada piirkondadena tasapinnal (joonis 4a). Joonisel fig. 4b, pesastatud komplektid ei asu tasapinnal, vaid on piklikud üheks jooneks. Riis. 4b võib vaadelda ka mõne algebralise valemi diagrammina, mis sisaldab pesastatud sulgusid. Riis. 4b annab veel ühe populaarne viis puustruktuuri kujutised astmelise loendi kujul.

Riis. 4. Muud viisid puustruktuuride kujutamiseks: (a) pesastatud komplektid; (b) pesastatud sulud; c) kontsessiooniloend.

Ajastatud loendil on ilmseid sarnasusi vormindusmeetodiga programmi kood. Tõepoolest, struktureeritud programmeerimise paradigma raames kirjutatud programmi saab kujutada pesastatud struktuuridest koosneva puuna.

Samuti saate tuua analoogia ääriku loendi ja vahel välimus raamatute sisukorrad, kus osad sisaldavad alajaotisi, mis omakorda sisaldavad alajaotisi jne. Traditsiooniline viis Selliste jaotiste nummerdamist (jaotis 1, alajaotised 1.1 ja 1.2, alajaotis 1.1.2 jne) nimetatakse Dewey kümnendsüsteemiks. Kasutatakse joonisel fig. 3 ja 4 annab see süsteem:

1. A; 1.1B; 1,2 °C; 1.2.1 D; 1,2,2 E; 1,2,3 F; 1.2.3.1 G;

5.2. Mööduvad puud

Kõigis puustruktuuridega seotud algoritmides esineb alati sama idee, nimelt idee möödudes või puu läbimine. See on viis puusõlmede külastamiseks, kus iga sõlme läbitakse täpselt üks kord. Selle tulemuseks on puu sõlmede lineaarne paigutus. Eelkõige on kolm võimalust: saate läbida sõlmed edasi-, tagurpidi- ja lõppjärjekorras.

Edasiliikumise algoritm:

• Jõua juure juurde
• Käige läbi kõik alampuud otseses järjekorras vasakult paremale.

See algoritm on rekursiivne, kuna puu läbimine sisaldab alampuude läbimist ja need omakorda läbitakse sama algoritmi abil.

Eelkõige joonisel fig. 3 ja 4 annab otsene läbimine sõlmede jada: A, B, C, D, E, F, G.

Saadud jada vastab sõlmede järjestikusele vasakult paremale loendamisele, kui puud esitatakse pesastatud sulgude abil ja kümnendsüsteem Dewey, samuti ülalt-alla lõik, kui see esitatakse astmelise loendina.

Selle algoritmi rakendamisel programmeerimiskeeles vastab juure tabamine teatud toiminguid sooritavale protseduurile või funktsioonile ja alampuude läbimine vastab rekursiivsetele väljakutsetele iseendale. Täpsemalt, binaarpuu puhul (kus igal sõlmel on maksimaalselt kaks alampuud) näeks vastav protseduur välja järgmine:

// Preorder Traversal – otsetellimuse protseduuri ingliskeelne nimetus PreorderTraversal((Arguments)); begin //Juure DoSomething((Arguments)) edastamine;

//Vasakpoolse alampuu üleminek if (On vasakpoolne alampuu) then PreorderTransversal((Argumendid 2));

//Parema alampuu üleminek if (Seal on parempoolne alampuu) then PreorderTransversal((Argumendid 3)); lõpp;

• See tähendab, et kõigepealt teostab protseduur kõik toimingud ja alles seejärel toimuvad kõik rekursiivsed kõned.
• Jõua juure juurde
• Tagurpidi läbimise algoritm:
• Jõua juure juurde
• Mine läbi vasaku alampuu,

Minge läbi järgmise alampuu vasakule.

jne kuni parempoolseima alampuu läbimiseni.

See tähendab, et kõik alampuud läbitakse vasakult paremale ja juurte naasmine asub nende läbimiste vahel. Joonisel fig. 3 ja 4 annab see sõlmede järjestuse: B, A, D, C, E, G, F.

Vastavas rekursiivses protseduuris paiknevad toimingud rekursiivsete kõnede vahelistes ruumides. Täpsemalt kahendpuu jaoks:

• // Inorder Traversal – pöördjärjestuse protseduuri ingliskeelne nimetus InorderTraversal((Arguments)); begin //Vasakpoolse alampuu liikumine if (Seal on vasakpoolne alampuu) then InorderTraversal((Argumendid 2));
• //Juure DoSomething((Argumendid)) edastamine;

//Parempoolse alampuu läbimine if (Parempoolne alampuu on olemas) then InorderTraversal((Argumendid 3)); lõpp;

Lõpptellimuse läbimise algoritm:

// Postorder Traversal – lõputellimuse protseduuri ingliskeelne nimetus PostorderTraversal((Arguments)); begin //Vasakpoolse alampuu reisimine if (Seal on vasakpoolne alampuu) then PostorderTraversal((Argumendid 2));

//Parempoolse alampuu ületamine if (Parempoolne alampuu on olemas) then PostorderTraversal((Argumendid 3));

//Juure DoSomething((Argumendid)) edastamine; lõpp; 5.3. Puu kujutamine arvuti mälus Kui osa informatsioonist asub puusõlmedes, saab selle salvestamiseks kasutada sobivat dünaamilist andmestruktuuri. Pascalis tehakse seda kasutades

muutuv tüüp

kirje, mis sisaldab viiteid sama tüüpi alampuudele. Näiteks saab binaarpuud, kus iga sõlm sisaldab täisarvu, salvestada PTree tüüpi muutuja abil, mida kirjeldatakse allpool: Tüüp PTree = ^TTree; TTree = kirje Inf: täisarv;

LeftSubTree, RightSubTree: PTree;

lõpp;

Igal sõlmel on PTree tüüp. See on osuti, mis tähendab, et iga sõlm tuleb luua, kutsudes sellel protseduuri New. Kui sõlm on lehe sõlm, määratakse selle väljadele LeftSubTree ja RightSubTree väärtus

null Tüüp PTree = ^TTree;. Vastasel juhul luuakse protseduuri New abil ka sõlmed LeftSubTree ja RightSubTree.

Üks selline kirje on skemaatiliselt näidatud joonisel fig. 5.

Riis. 5. TTree tüüpi kirje skemaatiline esitus. Kirjel on kolm välja: Inf – arv, LeftSubTree ja RightSubTree – viitavad sama TTpuu tüüpi kirjetele.

Sellistest kirjetest koosneva puu näide on näidatud joonisel 6.

Riis. 6. TTree tüüpi kirjetest koosnev puu. Iga kirje salvestab numbri ja kaks osutit, mis võivad sisaldada kumbagi

või muude sama tüüpi kirjete aadressid.

Kui te pole varem töötanud struktuuridega, mis koosnevad kirjetest, mis sisaldavad linke sama tüüpi kirjetele, soovitame tutvuda selle materjaliga.

Sellise protseduuri näide, mis on kirjutatud Delphis, on toodud allpool:

Procedure Tree(Canvas: TCanvas; //Lõuend, millele puu joonistatakse x,y: laiendatud; //Juurkoordinaadid Nurk: laiendatud; //Nurk, mille juures puu kasvab TrunkLength: extended; //Tüve pikkus n: täisarv / /harude arv (mitu //rekursiivset kõnet veel jääb)); var x2, y2: laiendatud; //Tüve lõpp (harupunkt) begin x2:= x + TrunkLength * cos(Angle);

y2:= y - pagasiruumi pikkus * sin(nurk);

Canvas.MoveTo(ring(x), round(y));

Canvas.LineTo(ring(x2), round(y2));

kui n > 1, siis alusta puu(lõuend, x2, y2, nurk+Pi/4, 0,55*tüve pikkus, n-1);

Puu (lõuend, x2, y2, nurk-Pi/4, 0,55* tüvepikkus, n-1);
lõpp; lõpp; Et saada joonis fig. 6 see protseduur kutsuti välja järgmiste parameetritega: Puu (Pilt1. Lõuend, 175, 325, Pi/2, 120, 15);

Pange tähele, et joonistamine toimub enne rekursiivseid kõnesid, see tähendab, et puu joonistatakse otseses järjekorras.

6.2. Hanoi tornid

Legendi järgi on Banarase suures templis maailma keskpaika tähistava katedraali all pronksketas, millele on kinnitatud 3 teemantvarrast, ühe küünra kõrgused ja jämedad nagu mesilane. Kaua aega tagasi, aegade alguses, panid selle kloostri mungad jumal Brahma ees solvama. Raevunud Brahma püstitas kolm kõrget varrast ja asetas ühele neist 64 puhtast kullast ketast, nii et iga väiksem ketas toetus suuremale. Niipea kui kõik 64 ketast kantakse vardalt, millele Jumal Brahma need maailma loomisel asetas, teisele vardale, muutub torn koos templiga tolmuks ja maailm hukkub äikeselöögi all. n Protsess nõuab seda n suurem ketas

pole kunagi leidnud end millestki vähemast kõrgemal. Mungad on kitsikuses: millises järjekorras peaksid nad vahetusi tegema? Selle järjestuse arvutamiseks on vaja neid varustada tarkvaraga. n Sõltumata Brahmast pakkus selle mõistatuse 19. sajandi lõpus välja prantsuse matemaatik Edouard Lucas. Müüdud versioonis kasutati tavaliselt 7-8 ketast (joon. 7).
Riis. 7. Pusle “Hanoi tornid”. n Oletame, et sellele on lahendus
-1 ketas. Siis käiguvahetuseks n kettad, toimige järgmiselt: n 1) Vaheta

- 1 ketas. n 2) Vaheta

Loome rekursiivse protseduuri, mis prindib kogu ümberkorralduste jada teatud arvu ketaste jaoks. Iga kord, kui selline protseduur välja kutsutakse, peab see printima info ühe nihke kohta (algoritmi punktist 2). Punktides (1) ja (3) tehtud ümberkorraldamisel kutsub protseduur end välja, kui ketaste arvu vähendatakse ühe võrra.

//n – ketaste arv //a, b, c – pin numbrid. Nihutamine toimub tihvtilt a, //tihvti b abitihvtiga c. protseduur Hanoi(n, a, b, c: täisarv); alusta, kui n > 1, siis alusta Hanoi(n-1, a, c, b);

writeln(a, " -> ", b);

Hanoi(n-1, c, b, a);

end else writeln(a, " -> ", b);

lõpp;

Pange tähele, et rekursiivselt kutsutud protseduuride komplekt moodustab sel juhul puu, mida läbitakse vastupidises järjekorras. 6.3. Aritmeetiliste avaldiste sõelumine (6).

Parsimise ülesanne on arvutada avaldise väärtus olemasoleva aritmeetilist avaldist sisaldava stringi ja selles sisalduvate muutujate teadaolevate väärtuste abil. Aritmeetiliste avaldiste arvutamise protsessi saab esitada kahendpuuna. Tõepoolest, iga aritmeetiline operaator (+, –, *, /) nõuab kahte operandi, mis on ühtlasi aritmeetilised avaldised ja vastavalt sellele võib neid pidada alampuudeks. Riis. Joonisel 8 on näide avaldisele vastavast puust: Riis. 8. Vastav süntaksipuu aritmeetiline avaldis Sellises puus on lõppsõlmed alati muutujad (siin

x ) või arvkonstandid ja kõik sisemised sõlmed sisaldavad aritmeetilised operaatorid . Operaatori käivitamiseks peate esmalt hindama selle operandid. Seega tuleks joonisel olev puu läbida terminali järjekorras. Vastav sõlmede jada

helistas vastupidine Poola märge

aritmeetiline avaldis.

Süntaksipuu ehitamisel peaksite tähelepanu pöörama

järgmine funktsioon . Kui on näiteks väljend – ja loeme liitmise ja lahutamise tehteid vasakult paremale, siis õige süntaksipuu sisaldab plussi asemel miinust (joon. 9a). Sisuliselt vastab see puu avaldisele Puu loomist on võimalik lihtsustada, kui analüüsida avaldist (8) tagurpidi, paremalt vasakule. Sel juhul on tulemuseks puu, millel on joon. 9b, samaväärne puuga 8a, kuid ei nõua märkide asendamist. + Samamoodi tuleb paremalt vasakule analüüsida korrutamise ja jagamise operaatoreid sisaldavaid avaldisi. lugedes vasakult paremale (a) ja paremalt vasakule (b).

Selline lähenemine ei välista täielikult rekursiooni. Kuid see võimaldab teil piirduda ainult ühe rekursiivse protseduuri kutsega, mis võib olla piisav, kui motiiv on jõudluse maksimeerimine.

7.3. Puu sõlme määramine selle numbri järgi

Idee see lähenemine on asendada rekursiivsed kõned lihtsa tsükliga, mida täidetakse nii mitu korda, kui palju on rekursiivsete protseduuride abil moodustatud puus sõlmi. See, mida igal etapil täpselt tehakse, tuleks määrata sammu numbri järgi. Sobitage sammu number ja vajalikud toimingud– ülesanne ei ole triviaalne ja see tuleb igal juhul eraldi lahendada.

Oletame näiteks, et soovite seda teha k pesastatud silmused n sammud igas:

Kui i1:= 0 kuni n-1, tee i2:= 0 kuni n-1 puhul tee i3:= 0 kuni n-1 tee …

Kui k on ette teadmata, on võimatu neid selgesõnaliselt kirjutada, nagu ülal näidatud. Kasutades jaotises 6.5 näidatud tehnikat, saate rekursiivse protseduuri abil hankida vajaliku arvu pesastatud silmuseid:

Protseduur NestedCycles(Indeksid: täisarvu massiiv; n, k, sügavus: täisarv); var i: täisarv; alustada, kui sügavus

Rekursioonist vabanemiseks ja kõige taandamiseks üheks tsükliks pidage meeles, et kui nummerdate sammud radikaalarvude süsteemis n, siis on igal sammul number, mis koosneb numbritest i1, i2, i3, ... või vastavatest väärtustest massiivist Indeksid. See tähendab, et numbrid vastavad tsükliloendurite väärtustele. Sammu number tavalises kümnendkohas:

Kokku tuleb samme n k. Läbides nende arvud kümnendarvusüsteemis ja teisendades igaüks neist radikssüsteemi n, saame indeksi väärtused:

M:= round(IntPower(n, k)); i:= 0 kuni M-1 puhul alusta Number:= i;

p:= 0 kuni k-1 puhul alustage Indeksid := Number mod n;

Number:= Arv div n;

lõpp;

DoSomething (indeksid); lõpp;

Märgime veel kord, et meetod ei ole universaalne ja iga ülesande jaoks peate välja pakkuma midagi erinevat.

Turvaküsimused

1. Tehke kindlaks, mida järgmised rekursiivsed protseduurid ja funktsioonid teevad.

(a) Mida prindib järgmine protseduur Rec(4) kutsumisel?

Protseduur A(n: täisarv); protseduur B(n: täisarv); protseduur A(n: täisarv); alustada writeln(n);

B(n-1); lõpp; protseduur B(n: täisarv); alustada writeln(n);

kui n

(d) Mida prindib alltoodud protseduur BT(0, 1, 3) kutsumisel? Protseduur BT(x: tegelik; D, MaxD: täisarv); alustada, kui D = MaxD, siis writeln(x) muidu algab BT(x – 1, D + 1, MaxD); BT(x + 1, D + 1, MaxD); lõpp; lõpp; 2. Ouroboros – lahtivolditud saba õgiv madu (joon. 14) on pikkusega L, läbimõõt ümber pea

D

, kõhu seina paksus

d

. Tehke kindlaks, kui palju saba suudab ta endasse pigistada ja mitu kihti pärast seda saba asetatakse?

Riis. 14. Laiendatud ouroboros.

3. Joonisel fig. 10a näitavad külastavate sõlmede järjestust edasi-, tagurpidi- ja lõpuläbimise järjekorras.

4. Kujutage graafiliselt pesastatud sulgudes määratletud puud: (A(B(C, D), E), F, G).

5. Kujutage graafiliselt süntaksipuud järgmise aritmeetilise avaldise jaoks: Kirjutage see avaldis vastupidises poola keeles. 6. Alloleva graafiku jaoks (joonis 15) kirjutage üles naabrusmaatriks ja esinemismaatriks.

Ülesanded 1. Olles faktoriaali piisavalt arvutanud suur hulk

korda (miljon või rohkem), võrrelge rekursiivsete ja iteratiivsete algoritmide efektiivsust. Kui palju erineb täitmisaeg ja kuidas see suhe sõltub arvust, mille faktoriaali arvutatakse?
2. Kirjutage rekursiivne funktsioon, mis kontrollib sulgude õiget paigutust stringis. Kell

õige paigutus

tingimused on täidetud: a) avavate ja sulgevate sulgude arv on võrdne.(b) mis tahes paari sees on ava - vastav sulgemisklamber, sulgud on õigesti paigutatud.

Näited vale paigutuse kohta:)(, ())(, ())(() jne.

3. Rida võib sisaldada nii ümar- kui nurksulge. Igal avasulul on vastav sama tüüpi sulg (ümmargune - ümmargune,
ruut - ruut n.

). Kirjutage rekursiivne funktsioon, mis kontrollib, kas sulud on antud juhul õigesti paigutatud. Vale paigutuse näide: ([)].

4. Tavaliste sulgstruktuuride arv pikkusega 6 on 5: ()()(), (())(), ()(()), ((())), (()()).
Kirjutage rekursiivne programm, mis genereerib kõik tavalised sulgstruktuurid pikkusega 2

5. Loo protseduur, mis prindib kõik võimalikud permutatsioonid täisarvudele vahemikus 1 kuni N.

6. Loo protseduur, mis prindib kõik komplekti alamhulgad (1, 2, ..., N).

7. Koostage protseduur, mis prindib naturaalarvu N kõik võimalikud esitused teiste naturaalarvude summana.

8. Loo funktsioon, mis arvutab massiivi elementide summa järgmisele algoritmile: massiiv jagatakse pooleks, arvutatakse ja liidetakse iga poole elementide summad. Poole massiivi elementide summa arvutatakse sama algoritmi abil, st jälle pooleks jagades. Jagamised toimuvad seni, kuni saadud massiivi tükid sisaldavad igaüks ühte elementi ja vastavalt sellele summa arvutamine muutub triviaalseks.

Kommenteeri: see algoritm on alternatiiv. Reaalväärtuslike massiivide puhul võimaldab see tavaliselt väiksemaid ümardamisvigu.

10. Loo protseduur, mis joonistab Kochi kõvera (joonis 12).

11. Reprodutseerige joonis. 16. Joonisel on igal järgmisel iteratsioonil ring 2,5 korda väiksem (selle koefitsiendi saab teha parameetriks).

Kirjandus

1. D. Knuth. Arvuti programmeerimise kunst. v. 1. (jaotis 2.3. “Puud”).
2. N. Wirth. Algoritmid ja andmestruktuurid.

Varg ütleb:

Tere pärastlõunast, ma tõesti ei saa aru, kuidas see funktsioon arvutusi teeb.

{
kui (n==1) tagastab 1; //kui uus väärtus on 1, siis lisame selle 1-ga, mitte eelmisega. sest eelmine on null. ja liitmine 1+0 on lõpmatu.
else return summa(n-1)+n; //aga kui n>1, siis lisa see eelmise väärtusega, mis on võrdne kõigi elementide summaga kuni n
}

Minu arusaamist mööda on n-s 5, tingimus ei sobi siis on täidetud see kood summa(n-1)+n ehk siis 5-le liidetakse midagi, mis saadi sulgudes lahutamise teel, aga mis on (5 - 1)+5 ja kui jah, siis mis selle aritmeetilise tehte peatab:?: :?: :?: Mis on eelmine väärtus, kust see tuleb, millega see võrdub:?: :?: :?:

Jah, peaaegu kõik on nii, nagu ma aru sain (viimases lõigus näitasite rekursiooni))), kuid jääb küsimus: kuidas saadakse summa, mis seejärel ekraanil kuvatakse?
Töötan enda jaoks Dev C++-ga see näide kuvab summa ==15, kui lugeda nii nagu näites kirjas, siis tuleb summa erinevaks.
Kirjutasin eespool, võtame (5-1)+5=4+5=9

:
1+2+3+4+5 = 15. Näide väljastab õigesti.

(5) //Andsime funktsioonile 5, kontrollisime selle võrdsust ühega. ei ole võrdne, kutsus funktsiooni uuesti, edastades sellesse 5-1
(5-1+(5)) //...
(4-1+(5-1+(5)))
(3-1+(4-1+(5-1+(5))))
(2-1+(3-1+(4-1+(5-1+(5)))))

2-1 == 1, funktsiooni kutsumine on lõpetatud.
(2-1+(3-1+(4-1+(5-1+(5))))) == 15
see on tulemus.
Siin on funktsiooni tulemuseks kahe esimese arvu erinevus ja n on ülejäänud parempoolne osa
__________________________________
Peate lihtsalt funktsioonist õigesti aru saama ja aktsepteerima seda arvutatud väärtusena, mitte mõistma seda muutujana. See on sarnane muutujale, kuid lähemal arvutuslikule konstandile, kuigi see pole konstant, on seda lihtsalt niimoodi mugavam tajuda.

Jah, jah, jah, mul ei olnud aega kirjutada, et sain aru, kõik on õige, midagi ei saanud kohe läbi. Aitäh hea sait))

Ja see ei ole 8. real ikkagi täiesti loogiline, kui muudate tagastatud numbri 1-st 2-ks, muutub summa 16-ks. Kuidas on see tingimus seotud 9. reaga?
Ka sellega on kõik selge, lihtsalt return 2 lisab oma ilmajäämise niiöelda summale juurde.

:
mitte lisatäht, vaid see kaks ja kui kirjutada -3, siis ühekordse liitmisel lahutab see kolm jne.
Kogu loogika seisneb selles, et iga rekursiivne funktsioon vajab tagastuspunkti.
Seos üheksanda reaga seisneb selles, et rekursiivsete kõnede ajal edastatakse summa funktsioonile number, seda arvu vähendatakse iga kord ühe (n-1) võrra, seda tulemust n-1 kontrollitakse võrdsuse suhtes; üks ja kui võrdsus on tõene, liidetakse kogu saadud summa selle deklaratsiooni numbriga. vastasel juhul liidetakse kogu summa selle uue n-1-ga