Calling rekursive prosedyrer forklaring av eksamen. Rekursjon og rekursive algoritmer. Parsing av aritmetiske uttrykk

Rekursjon er når en subrutine kaller seg selv. Når de står overfor et slikt algoritmisk design for første gang, opplever de fleste visse vanskeligheter, men med litt øvelse vil rekursjon bli et forståelig og veldig nyttig verktøy i programmeringsarsenalet ditt.

1. Essensen av rekursjon

En prosedyre eller funksjon kan inneholde kall til andre prosedyrer eller funksjoner. Prosedyren kan også kalle seg selv. Det er ikke noe paradoks her - datamaskinen utfører bare kommandoene den møter i programmet sekvensielt, og hvis den støter på et prosedyrekall, begynner den ganske enkelt å utføre denne prosedyren. Det spiller ingen rolle hvilken prosedyre som ga kommandoen for å gjøre dette.

Eksempel på en rekursiv prosedyre:

Prosedyre Rec(a: heltall); begynne hvis a>

La oss vurdere hva som skjer hvis et kall, for eksempel, av formen Rec(3) gjøres i hovedprogrammet. Nedenfor er et flytskjema som viser utførelsessekvensen til setningene.

Ris. 1. Blokkskjema over den rekursive prosedyren.

Prosedyre Rec kalles med parameter a = 3. Den inneholder et kall til prosedyre Rec med parameter a = 2. Det forrige kallet er ikke fullført ennå, så du kan tenke deg at en annen prosedyre opprettes og den første ikke fullfører arbeidet før den er ferdig. Anropsprosessen avsluttes når parameter a = 0. På dette tidspunktet utføres 4 forekomster av prosedyren samtidig. Antallet samtidig utførte prosedyrer kalles rekursjonsdybde.

Den fjerde prosedyren kalt (Rec(0)) vil skrive ut tallet 0 og fullføre arbeidet. Etter dette går kontrollen tilbake til prosedyren som kalte den (Rec(1)) og tallet 1 skrives ut og så videre til alle prosedyrer er fullført. Den opprinnelige samtalen vil skrive ut fire tall: 0, 1, 2, 3.

Et annet visuelt bilde av hva som skjer er vist i fig. 2.

Ris. 2. Utføring av Rec-prosedyren med parameter 3 består av å utføre Rec-prosedyren med parameter 2 og skrive ut nummer 3. I sin tur består å utføre Rec-prosedyren med parameter 2 av å utføre Rec-prosedyren med parameter 1 og skrive ut nummer 2. Osv. .

Som en øvelse på egen hånd, vurder hva som skjer når du ringer Rec(4). Vurder også hva som ville skje hvis du kalte Rec2(4)-prosedyren nedenfor, med operatørene omvendt.

Prosedyre Rec2(a: heltall); begynne å skriveln(a);

hvis a>0 så Rec2(a-1); slutt;

Vær oppmerksom på at i disse eksemplene er det rekursive kallet inne i en betinget setning. Dette er en nødvendig betingelse for at rekursjonen noen gang skal ta slutt. Merk også at prosedyren kaller seg selv med en annen parameter enn den den ble kalt med. Hvis prosedyren ikke bruker globale variabler, er dette også nødvendig for at rekursjonen ikke skal fortsette i det uendelige. Et litt mer komplekst opplegg er mulig: funksjon A kaller funksjon B, som igjen kaller A. Dette kalles kompleks rekursjon

. Det viser seg at prosedyren beskrevet først må kalle en prosedyre som ennå ikke er beskrevet. For at dette skal være mulig, må du bruke .

Prosedyre A(n: heltall); (Videresend beskrivelse (overskrift) av den første prosedyren) prosedyre B(n: heltall); (Viderebeskrivelse av den andre prosedyren) prosedyre A(n: heltall); (Fullstendig beskrivelse av prosedyre A) start writeln(n);

B(n-1); slutt; prosedyre B(n: heltall); (Full beskrivelse av prosedyre B) start writeln(n);

hvis n

Fremskrittserklæringen for prosedyre B lar den kalles fra prosedyre A. Fremskrittserklæringen av prosedyre A er ikke påkrevd i dette eksemplet og er lagt til av estetiske grunner.

Hvis vanlig rekursjon kan sammenlignes med en ouroboros (fig. 3), så kan bildet av kompleks rekursjon hentes fra det berømte barnediktet, der "Ulvene ble skremt og spiste hverandre." Se for deg to ulver som spiser hverandre, og du vil forstå kompleks rekursjon.

Ris. 3. Ouroboros - en slange som sluker sin egen hale. Tegning fra den alkymistiske avhandlingen "Synosius" av Theodore Pelecanos (1478).

Ris. 4. Kompleks rekursjon.

3. Simulere en sløyfe ved hjelp av rekursjon

Prosedyre LoopImitation(i, n: heltall); (Den første parameteren er trinntelleren, den andre parameteren er det totale antallet trinn) begin writeln("Hei N", i); //Her er instruksjoner som vil bli gjentatt hvis jeg

Resultatet av et kall på skjemaet LoopImitation(1, 10) vil være utførelse av instruksjoner ti ganger, og endre telleren fra 1 til 10. I dette tilfellet vil følgende bli skrevet ut:

Hei N 1
Hei N 2
…
Hei N 10

Generelt er det ikke vanskelig å se at parametrene for prosedyren er grensene for å endre tellerverdiene.

Du kan bytte det rekursive anropet og instruksjonene som skal gjentas, som i følgende eksempel.

Eksempel 2.

Prosedyre LoopImitation2(i, n: heltall); begynne hvis jeg

I dette tilfellet vil et rekursivt prosedyrekall forekomme før instruksjoner begynner å bli utført. Den nye instansen av prosedyren vil også først og fremst kalle en annen instans, og så videre, til vi når maksverdien til telleren. Først etter dette vil den siste av de kalte prosedyrene utføre sine instruksjoner, deretter vil den nest siste utføre sine instruksjoner osv. Resultatet av å ringe LoopImitation2(1, 10) vil være å skrive ut hilsener i omvendt rekkefølge:

Hei N 10
…
Hei N 1

Hvis vi ser for oss en kjede av rekursivt kalte prosedyrer, så går vi i eksempel 1 gjennom den fra tidligere kalte prosedyrer til senere. I eksempel 2, tvert imot, fra senere til tidligere.

Til slutt kan et rekursivt anrop plasseres mellom to blokker med instruksjoner. For eksempel:

Prosedyre LoopImitation3(i, n: heltall); begin writeln("Hei N", i); (Den første blokken med instruksjoner kan være plassert her) hvis jeg

Her blir instruksjonene fra den første blokken først utført sekvensielt, deretter blir instruksjonene fra den andre blokken utført i omvendt rekkefølge. Når vi ringer LoopImitation3(1, 10) får vi:

Hei N 1
…
Hei N 10
Hei N 10
…
Hei N 1

Det ville ta to løkker for å gjøre det samme uten rekursjon.

Du kan dra nytte av at utførelsen av deler av samme prosedyre er fordelt over tid. For eksempel:

Eksempel 3: Konvertering av et tall til binært.

Innhenting av sifrene til et binært tall, som kjent, skjer ved å dele med en rest på grunntallet av tallsystemet 2. Hvis det er et tall, er det siste sifferet i sin binære representasjon lik

Å ta hele delen av divisjon med 2:

vi får et tall som har samme binære representasjon, men uten siste siffer. Dermed er det nok å gjenta de to ovennevnte operasjonene til neste divisjonsfelt mottar en heltallsdel lik 0. Uten rekursjon vil det se slik ut:

Mens x>0 begynner c:=x mod 2;

Problemet her er at sifrene i den binære representasjonen beregnes i omvendt rekkefølge (siste først). For å skrive ut et tall i normal form, må du huske alle tallene i matriseelementene og skrive dem ut i en egen sløyfe.

Ved å bruke rekursjon er det ikke vanskelig å oppnå utdata i riktig rekkefølge uten en matrise og en andre sløyfe. Nemlig:

Prosedyre Binærrepresentasjon(x: heltall); var c, x: heltall; begynne (Første blokk. Utføres i rekkefølge etter prosedyrekall) c:= x mod 2;

x:= x div 2;

(Rekursivt kall) hvis x>0 så Binærrepresentasjon(x);

(Andre blokk. Utføres i omvendt rekkefølge) write(c); slutt;

Generelt sett mottok vi ingen gevinster. Sifrene i den binære representasjonen er lagret i lokale variabler, som er forskjellige for hver løpende forekomst av den rekursive prosedyren. Det vil si at det ikke var mulig å lagre minne. Tvert imot, vi kaster bort ekstra minne på å lagre mange lokale variabler x. Imidlertid virker denne løsningen vakker for meg.

4. Gjentaksforhold. Rekursjon og iterasjon

En sekvens av vektorer sies å være gitt av en gjentaksrelasjon hvis den opprinnelige vektoren og den funksjonelle avhengigheten til den påfølgende vektoren av den forrige er gitt

Et enkelt eksempel på en mengde beregnet ved bruk av gjentaksrelasjoner er faktorialet

Den neste faktoren kan beregnes fra den forrige som:

Ved å introdusere notasjonen får vi relasjonen: Vektorene fra formel (1) kan tolkes som sett med variabelverdier. Deretter vil beregningen av det nødvendige elementet i sekvensen bestå av gjentatt oppdatering av verdiene deres. Spesielt for faktoriell: X:= 1; for i:= 2 til n gjør x:= x * i; skrivln(x); Hver slik oppdatering (x:= x * i) kalles.

iterasjon

, og prosessen med å gjenta iterasjoner er

iterasjon

La oss imidlertid merke oss at relasjon (1) er en rent rekursiv definisjon av sekvensen, og beregningen av det n-te elementet er faktisk den gjentatte ta av funksjonen f fra seg selv:

Spesielt for faktoriell kan man skrive:

La oss vurdere et spesielt tilfelle av tilbakevendende relasjoner, når den neste verdien i sekvensen ikke avhenger av en, men av flere tidligere verdier samtidig. Et eksempel er den berømte Fibonacci-sekvensen, der hvert neste element er summen av de to foregående:

Med en "frontal" tilnærming kan du skrive:

Funksjon Fib(n: heltall): heltall; begynne hvis n > 1 så Fib:= Fib(n-1) + Fib(n-2) ellers Fib:= 1; slutt;

Hvert Fib-anrop lager to kopier av seg selv, hver kopi lager to til, og så videre. Antall operasjoner øker med antallet n eksponentielt, men med en iterativ løsning lineær inn n antall operasjoner.

Faktisk lærer eksemplet ovenfor oss ikke NÅR rekursjon bør ikke brukes, ellers HVORDAN den skal ikke brukes. Tross alt, hvis det er en rask iterativ (løkkebasert) løsning, kan den samme loopen implementeres ved hjelp av en rekursiv prosedyre eller funksjon. For eksempel:

// x1, x2 – startbetingelser (1, 1) // n – nummeret på den nødvendige Fibonacci-tallfunksjonen Fib(x1, x2, n: heltall): heltall; var x3: heltall; start hvis n > 1 så begynner x3:= x2 + x1;

x1:= x2;

x2:= x3;

Fib:= Fib(xl, x2, n-1);

end else Fib:= x2; slutt;

Likevel er iterative løsninger å foretrekke. Spørsmålet er, når skal rekursjon brukes i dette tilfellet?

Eventuelle rekursive prosedyrer og funksjoner som inneholder bare ett rekursivt anrop til seg selv, kan enkelt erstattes av iterative løkker. For å få noe som ikke har et enkelt ikke-rekursivt motstykke, må du ty til prosedyrer og funksjoner som kaller seg selv to eller flere ganger. I dette tilfellet danner settet med kalte prosedyrer ikke lenger en kjede, som i fig. 1, men et helt tre. Det er brede klasser av problemer når beregningsprosessen må organiseres på denne måten. For dem vil rekursjon være den enkleste og mest naturlige løsningen. 5. Trær Det teoretiske grunnlaget for rekursive funksjoner som kaller seg mer enn en gang er grenen av diskret matematikk som studerer trær. 5.1. Grunnleggende definisjoner. Måter å skildre trær på
Definisjon:
vi vil kalle den endelige mengden T, bestående av en eller flere noder slik at:

Denne definisjonen er rekursiv. Kort fortalt er et tre et sett som består av en rot og undertrær knyttet til den, som også er trær. Et tre er definert gjennom seg selv. Imidlertid gir denne definisjonen mening fordi rekursjon er begrenset. Hvert undertre inneholder færre noder enn dets tre. Til slutt kommer vi til undertrær som inneholder bare én node, og dette er allerede klart hva det er.

Ris. 3. Tre.

I fig. Figur 3 viser et tre med syv noder. Selv om vanlige trær vokser fra bunn til topp, er det vanlig å tegne dem omvendt. Når du tegner et diagram for hånd, er denne metoden åpenbart mer praktisk. På grunn av denne inkonsekvensen oppstår noen ganger forvirring når en node sies å være over eller under en annen. Av denne grunn er det mer praktisk å bruke terminologien som brukes når man beskriver familietrær, kaller noder nærmere rotforfedrene og fjernere etterkommere.

Et tre kan avbildes grafisk på andre måter. Noen av dem er vist i fig. 4. Ifølge definisjonen er et tre et system av nestede sett, der disse settene enten ikke krysser hverandre eller er fullstendig innesluttet i hverandre. Slike sett kan avbildes som områder på et plan (fig. 4a). I fig. 4b er de nestede settene ikke plassert på et plan, men er forlenget til en linje. Ris. 4b kan også sees på som et diagram over en algebraisk formel som inneholder nestede parenteser. Ris. Figur 4c gir en annen populær måte å representere en trestruktur som en forskjøvet liste.

Ris. 4. Andre måter å representere trestrukturer på: (a) nestede sett; (b) nestede parenteser; (c) konsesjonsliste.

Den forskjøvede listen har åpenbare likheter med måten programkoden er formatert på. Et program skrevet innenfor rammen av det strukturerte programmeringsparadigmet kan faktisk representeres som et tre som består av nestede strukturer.

Du kan også trekke en analogi mellom den trinnvise listen og utseendet til innholdsfortegnelser i bøker, der seksjoner inneholder underavsnitt, som igjen inneholder underavsnitt osv. Den tradisjonelle måten å nummerere slike seksjoner på (seksjon 1, underavsnitt 1.1 og 1.2, underavsnitt 1.1.2 osv.) kalles Dewey-desimalsystemet. Påført treet i fig. 3 og 4 vil dette systemet gi:

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. Passerende trær

I alle algoritmer knyttet til trestrukturer dukker alltid den samme ideen opp, nemlig ideen bestått eller kryssing av tre. Dette er en måte å besøke trenoder der hver node krysses nøyaktig én gang. Dette resulterer i et lineært arrangement av trenoder. Spesielt er det tre måter: du kan gå gjennom nodene i forover-, revers- og sluttrekkefølge.

Foroverovergangsalgoritme:

Gå til roten
Gå gjennom alle undertrær fra venstre til høyre i direkte rekkefølge.

Denne algoritmen er rekursiv, siden kryssingen av et tre inneholder kryssingen av undertrær, og de på sin side krysses ved hjelp av den samme algoritmen.

Spesielt for treet i fig. 3 og 4 gir direkte kryssing en sekvens av noder: A, B, C, D, E, F, G.

Den resulterende sekvensen tilsvarer en venstre-til-høyre-oppregning av noder når du representerer et tre ved bruk av nestede parenteser og i Dewey-desimalnotasjon, samt en ovenfra-ned passasje når du representerer det som en forskjøvet liste.

Når du implementerer denne algoritmen i et programmeringsspråk, tilsvarer det å komme til roten prosedyren eller funksjonen som utfører noen handlinger, og å gå gjennom undertrær tilsvarer rekursive anrop til seg selv. Spesielt for et binært tre (hvor hver node har maksimalt to undertrær), vil den tilsvarende prosedyren se slik ut:

// Preorder Traversal – engelsk navn for direkte bestillingsprosedyre PreorderTraversal((Argumenter)); begynne //Passer roten DoSomething((Argumenter));

//Overgang av venstre undertre hvis (Det er et venstre undertre) deretter PreorderTransversal((Argumenter 2));

//Overgang av høyre undertre hvis (Det er et høyre undertre) deretter PreorderTransversal((Argumenter 3)); slutt;

Det vil si at først utfører prosedyren alle handlinger, og først deretter oppstår alle rekursive anrop.
Gå til roten
Omvendt traversalalgoritme:
Gå til roten
Gå gjennom det venstre undertreet,

Gå gjennom neste undertre til venstre.

osv. til undertreet lengst til høyre krysses.

// Inorder Traversal – engelsk navn for prosedyre for omvendt rekkefølge InorderTraversal((Argumenter)); begin //Reise det venstre undertreet if (Det er et venstre undertre) deretter InorderTraversal((Argumenter 2));

//Passer roten DoSomething((Argumenter));

//Traverse det høyre undertreet hvis (Et høyre undertre finnes) deretter InorderTraversal((Argumenter 3)); slutt;
End-order traversal algoritme:

Gå gjennom alle undertrær fra venstre til høyre,

Gå til roten.

For treet i fig. 3 og 4 vil dette gi sekvensen av noder: B, D, E, G, F, C, A.

I en tilsvarende rekursiv prosedyre vil handlingene bli lokalisert etter de rekursive anropene. Spesielt for et binært tre:

// Postorder Traversal – engelsk navn for sluttbestillingsprosedyren PostorderTraversal((Argumenter)); begin //Reise det venstre undertreet if (Det er et venstre undertre) deretter PostorderTraversal((Argumenter 2));

//Transcendere det høyre undertreet hvis (Et høyre undertre eksisterer) deretter PostorderTraversal((Argumenter 3));

//Passer roten DoSomething((Argumenter)); slutt; 5.3. Representasjon av et tre i datamaskinens minne Hvis noe informasjon er plassert i trenoder, kan en passende dynamisk datastruktur brukes til å lagre den. I Pascal gjøres dette ved å bruke en posttypevariabel som inneholder pekere til undertrær av samme type. For eksempel kan et binært tre hvor hver node inneholder et heltall lagres ved å bruke en variabel av typen PTree, som er beskrevet nedenfor:

Skriv PTree = ^TTree;

TTree = post Inf: heltall;

LeftSubTree, RightSubTree: PTree;

slutt; 5.3. Representasjon av et tre i datamaskinens minne Hver node har en PTree-type. Dette er en peker, noe som betyr at hver node må opprettes ved å kalle den nye prosedyren på den. Hvis noden er en bladnode, blir feltene LeftSubTree og RightSubTree tildelt verdien

null

6. Eksempler på rekursive algoritmer

6.1. Tegne et tre

La oss vurdere algoritmen for å tegne treet vist i fig. 6. Hvis hver linje betraktes som en node, tilfredsstiller dette bildet fullt ut definisjonen av et tre gitt i forrige seksjon.

Ris. 6. Tre.

Den rekursive prosedyren ville åpenbart tegne en linje (stammen opp til den første grenen), og deretter kalle seg for å tegne de to undertrærne. Undertrær skiller seg fra treet som inneholder dem i koordinatene til deres startpunkt, rotasjonsvinkel, stammelengde og antall grener de inneholder (en mindre). Alle disse forskjellene bør gjøres til parametere for den rekursive prosedyren.

Et eksempel på en slik prosedyre, skrevet i Delphi, er presentert nedenfor:

Prosedyre Tre(Lerret: TCanvas; //Lerret som treet skal tegnes på x,y: utvidet; //Rotkoordinater Vinkel: utvidet; //Vinkel som treet vokser ved Stammelengde: utvidet; //Stammelengde n: heltall / /Antall grener (hvor mange flere //rekursive samtaler gjenstår)); var x2, y2: utvidet; //Trunk end (grenpunkt) begynne x2:= x + TrunkLength * cos(Angle);

y2:= y - TrunkLength * sin(Angle);

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

Canvas.LineTo(rund(x2), rund(y2));

hvis n > 1, begynn Tre(Lerret, x2, y2, Vinkel+Pi/4, 0,55*Bamlengde, n-1);

Tre(Lerret, x2, y2, Angle-Pi/4, 0,55*TrunkLength, n-1);
slutt; slutt;

Uavhengig av Brahma ble dette puslespillet foreslått på slutten av 1800-tallet av den franske matematikeren Edouard Lucas. Den solgte versjonen brukte vanligvis 7-8 disker (fig. 7).

Ris. 7. Puslespill "Towers of Hanoi".

Anta at det finnes en løsning for n-1 disk. Så for å skifte n disker, fortsett som følger:

1) Skift n-1 disk.
2) Skift n disken på den gjenværende ledige pinnen.
3) Vi skifter stabelen fra n-1 disk mottatt i punkt (1) på toppen n-te disken.

Fordi for saken n= 1 omorganiseringsalgoritmen er åpenbar, så ved induksjon, ved hjelp av handlinger (1) – (3), kan vi omorganisere et vilkårlig antall disker.

La oss lage en rekursiv prosedyre som skriver ut hele sekvensen av omorganiseringer for et gitt antall disker. Hver gang en slik prosedyre kalles, skal den skrive ut informasjon om ett skift (fra punkt 2 i algoritmen). For omorganiseringer fra punkt (1) og (3), vil prosedyren kalle seg selv med antall disker redusert med én.

//n – antall disker //a, b, c – pin-nummer. Skifting gjøres fra pinne a, //til pinne b med hjelpepinne c. prosedyre Hanoi(n, a, b, c: heltall); start hvis n > 1 så begynner Hanoi(n-1, a, c, b);

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

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

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

slutt;

Merk at settet med rekursivt kalte prosedyrer i dette tilfellet danner et tre som krysses i omvendt rekkefølge.

6.3. Parsing av aritmetiske uttrykk Oppgaven med å analysere er å beregne verdien av uttrykket ved å bruke en eksisterende streng som inneholder et aritmetisk uttrykk og de kjente verdiene til variablene som er inkludert i den. Prosessen med å beregne aritmetiske uttrykk kan representeres som et binært tre. Faktisk krever hver av de aritmetiske operatorene (+, –, *, /) to operander, som også vil være aritmetiske uttrykk og følgelig kan betraktes som undertrær. Ris. Figur 8 viser et eksempel på et tre som tilsvarer uttrykket:

Ris. 8. Syntakstreet som tilsvarer det aritmetiske uttrykket (6). I et slikt tre vil endenodene alltid være variabler (her x

Når du konstruerer et syntakstre, bør du være oppmerksom på følgende funksjon. Hvis det for eksempel er et uttrykk

og vi vil lese operasjonene for addisjon og subtraksjon fra venstre til høyre, så vil det riktige syntakstreet inneholde et minus i stedet for et pluss (fig. 9a). Faktisk tilsvarer dette treet uttrykket. Det er mulig å gjøre opprettelsen av et tre lettere hvis du analyserer uttrykk (8) omvendt, fra høyre til venstre. I dette tilfellet er resultatet et tre med fig. 9b, tilsvarende tre 8a, men krever ikke utskifting av skilt.

På samme måte, fra høyre til venstre, må du analysere uttrykk som inneholder multiplikasjons- og divisjonsoperatorer.

Ris. 9. Syntakstre for uttrykk en – b + c når du leser fra venstre til høyre (a) og fra høyre til venstre (b).

Denne tilnærmingen eliminerer ikke helt rekursjon. Det lar deg imidlertid begrense deg til kun ett kall til den rekursive prosedyren, noe som kan være tilstrekkelig hvis motivet er å maksimere ytelsen.

7.3. Bestemme en trenode etter nummeret

Ideen med denne tilnærmingen er å erstatte rekursive samtaler med en enkel sløyfe som vil bli utført så mange ganger som det er noder i treet dannet av de rekursive prosedyrene. Hva som skal gjøres på hvert trinn, bør bestemmes av trinnnummeret. Å sammenligne trinnnummeret og de nødvendige handlingene er ikke en triviell oppgave, og i hvert tilfelle må det løses separat.

La oss for eksempel si at du vil gjøre k nestede løkker n trinn i hver:

For i1:= 0 til n-1 gjør for i2:= 0 til n-1 gjør for i3:= 0 til n-1 gjør …

Hvis k er ukjent på forhånd, er det umulig å skrive dem eksplisitt, som vist ovenfor. Ved å bruke teknikken demonstrert i avsnitt 6.5, kan du få det nødvendige antallet nestede løkker ved å bruke en rekursiv prosedyre:

Prosedyre NestedCycles(Indekser: rekke av heltall; n, k, dybde: heltall); var i: heltall; begynne hvis dybde

For å bli kvitt rekursjon og redusere alt til én syklus, merk at hvis du nummererer trinnene i radix-tallsystemet n, så har hvert trinn et tall som består av tallene i1, i2, i3, ... eller de tilsvarende verdiene fra indeksene. Det vil si at tallene tilsvarer verdiene til syklustellerne. Trinnnummer i vanlig desimalnotasjon:

Det vil være totalt trinn n k. Ved å gå gjennom tallene deres i desimaltallsystemet og konvertere hvert av dem til radikssystemet n, får vi indeksverdiene:

M:= round(IntPower(n, k)); for i:= 0 til M-1 begynner Nummer:= i;

La oss merke igjen at metoden ikke er universell, og du må finne på noe forskjellig for hver oppgave.

Sikkerhetsspørsmål

1. Bestem hva følgende rekursive prosedyrer og funksjoner vil gjøre.

(a) Hva vil følgende prosedyre skrives ut når Rec(4) kalles?

Prosedyre Rec(a: heltall); begynne å skriveln(a);

hvis a>0 så Rec(a-1);

skrivln(a); slutt;

(b) Hva blir verdien av funksjonen Nod(78, 26)?

Funksjon Nod(a, b: heltall): heltall; begynne hvis a > b så Nikk:= Nikk(a – b, b) ellers hvis b > a så Nikk:= Nikk(a, b – a) annet Nikk:= a; slutt;

Prosedyre A(n: heltall); prosedyre B(n: heltall); prosedyre A(n: heltall); begynne å skriveln(n);

B(n-1); slutt; prosedyre B(n: heltall); begynne å skriveln(n); hvis n(d) Hva vil prosedyren nedenfor skrives ut når du kaller BT(0, 1, 3)? Prosedyre BT(x: reell; D, MaksD: heltall); begynne hvis D = MaksD så skrivln(x) ellers begynner BT(x – 1, D + 1, MaksD); BT(x + 1, D + 1, MaksD); slutt; slutt; 2. Ouroboros - en slange som sluker sin egen hale (fig. 14) når den er utfoldet har en lengde

, diameter rundt hodet

, bukveggtykkelse

. Bestem hvor mye hale han kan presse inn i seg selv og hvor mange lag skal halen legges i etter det?

Ris. 14. Utvidede ouroboros.

3. For treet i fig. 10a indikerer sekvensen av besøksnoder i forover-, revers- og endegjennomløpsrekkefølge.

4. Vis treet definert grafisk ved hjelp av nestede parenteser: (A(B(C, D), E), F, G).

5. Vis grafisk syntakstreet for følgende aritmetiske uttrykk:
Skriv dette uttrykket i omvendt polsk notasjon.

6. For grafen nedenfor (fig. 15), skriv ned adjacency-matrisen og insidensmatrisen.

3. Linjen kan inneholde både runde og firkantede parenteser. Hver åpningsbeslag har en tilsvarende lukkebeslag av samme type (rund - rund, firkantet - firkantet). Skriv en rekursiv funksjon som sjekker om parentesene er riktig plassert i dette tilfellet.

Eksempel på feil plassering: ([)].

4. Antall vanlige brakettstrukturer med lengde 6 er 5: ()()(), (())(), ()(()), ((())), (()()).
Skriv et rekursivt program for å generere alle vanlige brakettstrukturer med lengde 2 n.

Note: Riktig parentesstruktur med minimumslengde "()". Strukturer med lengre lengde oppnås fra strukturer med kortere lengde på to måter:

(a) hvis den mindre strukturen er tatt i parentes,
(b) hvis to mindre strukturer skrives sekvensielt.

5. Lag en prosedyre som skriver ut alle mulige permutasjoner for heltall fra 1 til N.

6. Lag en prosedyre som skriver ut alle delsett av settet (1, 2, ..., N).

7. Lag en prosedyre som skriver ut alle mulige representasjoner av det naturlige tallet N som summen av andre naturlige tall.

8. Lag en funksjon som beregner summen av matriseelementene ved hjelp av følgende algoritme: matrisen deles i to, summene av elementene i hver halvdel beregnes og legges til. Summen av elementene i halve matrisen beregnes ved hjelp av samme algoritme, det vil si igjen ved å dele i to. Divisjoner skjer til de resulterende delene av matrisen inneholder ett element hver, og beregning av summen blir derfor triviell.

Kommentar: Denne algoritmen er et alternativ. Når det gjelder matriser med reell verdi, tillater det vanligvis mindre avrundingsfeil.

10. Lag en prosedyre som tegner Koch-kurven (Figur 12).

11. Gjengi figuren. 16. På figuren, ved hver påfølgende iterasjon, er sirkelen 2,5 ganger mindre (denne koeffisienten kan gjøres til en parameter).

Litteratur

1. D. Knuth. Kunsten å programmere data. v. 1. (avsnitt 2.3. «Trær»).
2. N. Wirth. Algoritmer og datastrukturer.

En presentasjon om emnet "Rekursive algoritmer" ble opprettet for å forberede studentene til Unified State Exam i informatikk og IKT. Oppgaven undersøker definisjonen av rekursjon og gir eksempler på rekursivt definerte grafiske objekter. Presentasjonen inneholder metoder for å løse oppgave nr. 11 fra utkastet til demoversjon av Unified State Exam - 2015 i informatikk. Den første metoden innebærer å bygge et anropstre, den andre metoden løser problemet ved å bruke substitusjonsmetoden. 4 eksempler på å løse oppgaver ved bruk av begge metodene er vurdert. Følgende presentasjon inneholder 25 øvelser for trening med svar fra Konstantin Polyakovs nettside.

Last ned:

Forhåndsvisning:

For å bruke forhåndsvisninger av presentasjoner, opprett en Google-konto og logg på den: https://accounts.google.com

Lysbildetekster:

Oppgave nr. 11 Unified State Exam (grunnnivå, tid - 5 minutter) Rekursive algoritmer. Forfatter – Korotun O.V., lærer i informatikk, Kommunal utdanningsinstitusjon “Videregående skole nr. 71”

Hva du trenger å vite: Rekursjon er definisjonen, beskrivelsen, skildringen av et objekt eller en prosess innenfor dette objektet eller selve prosessen, det vil si en situasjon når et objekt er en del av seg selv. Den russiske føderasjonens våpenskjold er et rekursivt definert grafisk objekt: i høyre pote til den dobbelthodede ørnen som er avbildet på den, er et septer fastklemt, som er kronet med en mindre kopi av våpenskjoldet. Siden det på dette våpenskjoldet også er et septer i høyre pote på ørnen, oppnås en uendelig rekursjon. Rekursivt våpenskjold fra Russland

I programmering er rekursjon et kall til en funksjon fra seg selv, direkte eller gjennom andre funksjoner, for eksempel funksjon A kaller funksjon B, og funksjon B kaller funksjon A. Antall nestede kall til en funksjon eller prosedyre kalles dybden av rekursjon. eksempel på rekursjon: Hvis du har en fettflekk på kjolen din, ikke bekymre deg. Oljeflekker fjernes med bensin. Alkalien fjernes med essens. Vel, du vet allerede hvordan du fjerner oljeflekker.

Eksempeloppgave: Gitt en rekursiv algoritme: prosedyre F(n: heltall); begynne å skriveln(n); hvis n

Eksempeloppgave: Gitt en rekursiv algoritme: prosedyre F(n: heltall); begynne å skriveln(n); hvis n Lysbilde 9

Eksempeloppgave: Gitt en rekursiv algoritme: prosedyre F(n: heltall); begynne å skriveln(n); hvis n Lysbilde 10

Eksempeloppgave: Gitt en rekursiv algoritme: prosedyre F(n: heltall); begynne å skriveln(n); hvis n Lysbilde 11

15 Eksempel nr. 2: Gitt en rekursiv algoritme: prosedyre F(n: heltall); begynne å skriveln(n); hvis n

Eksempel nr. 2: Gitt en rekursiv algoritme: prosedyre F(n: heltall); begynne å skriveln(n); hvis n Lysbilde 13

Eksempel nr. 3: Gitt en rekursiv algoritme: prosedyre F(n: heltall); begynne writeln("*"); hvis n > 0 så begynner F(n-2); F(n div 2) ende ende ; Hvor mange stjerner vil bli skrevet ut på skjermen når du ringer F(7)? 7 5 3 2 3 1 1 1 1 I dette eksemplet vises symbolet * -2 div 2 1 0 -1 0 -1 0 -1 -1 -1 0 0 0 på skjermen i stedet for verdiene til parameter n .

Eksempel nr. 3: Gitt en rekursiv algoritme: prosedyre F(n: heltall); begynne writeln("*"); hvis n > 0 så begynner F(n-2); F(n div 2) ende ende ; Hvor mange stjerner vil bli skrevet ut på skjermen når du ringer F(7)? * Ved å telle antall "stjerner" får vi 21. I dette eksemplet er det ikke verdiene til parameteren n som vises på skjermen, men symbolet * * * * * * * * * * * * * * * * * * * * * *

Eksempel nr. 3: Gitt en rekursiv algoritme: prosedyre F(n: heltall); begynne writeln("*"); hvis n > 0 så begynner F(n-2); F(n div 2) ende ende ; Hvor mange stjerner vil bli skrevet ut på skjermen når du ringer F(7)? La oss løse problemet uten et tre. La S(n) være antallet "stjerner" som vil bli skrevet ut når du kaller F(n). Så 1+S(n-2)+ S(n div 2), n>0 1, n Vi trenger å vite S(7). S(7)= 1 +S(5)+ S(3) S(5)= 1 +S(3)+S(2) S(3)= 1 +S(1)+S(1) S( 2)=1+S(0)+S(1)=1+1+S(1)=2+S(1) S(1)= 1+ S(-1)+S(0)=1+ 1+1=3 Omvendt: S(2)=2+3=5 S(3)=1+3+3=7 S(5)=1+7+5=13 S(7)=1+ 13+ 7= 21 S(n)=

Eksempel nr. 4: prosedyre F(n: heltall); start if n Lysbilde 18

Eksempel nr. 4: prosedyre F(n: heltall); start if n Lysbilde 19

Eksempel nr. 4: prosedyre F(n: heltall); begynne hvis n

Opplæringsoppgaver

Oppgave 1: Gitt en rekursiv algoritme: prosedyre F(n: heltall); begynne writeln("*"); hvis n > 0 så begynner F(n-2); F(n div 2); F(n div 2); ende ende ; Hvor mange stjerner vil bli skrevet ut på skjermen når du ringer F(5)? Svar: 34

Oppgave 2: Gitt en rekursiv algoritme: prosedyre F(n: heltall); begynne writeln("*"); hvis n > 0 så begynner F(n-2); F(n-2); F(n div 2); ende ende ; Hvor mange stjerner vil bli skrevet ut på skjermen når du ringer F(6)? Svar: 58

Oppgave 3: Gitt en rekursiv algoritme: prosedyre F(n: heltall); begynne writeln("*"); hvis n > 0 så begynner F(n-3); F(n div 2); ende ende ; Hvor mange stjerner vil bli skrevet ut på skjermen når du ringer F(7)? Svar: 15

Oppgave 4: Gitt en rekursiv algoritme: prosedyre F(n: heltall); begynne writeln("*"); hvis n > 0 så begynner F(n-3); F(n-2); F(n div 2); ende ende ; Hvor mange stjerner vil bli skrevet ut på skjermen når du ringer F(7)? Svar: 55

Oppgave 5: Gitt en rekursiv algoritme: prosedyre F(n: heltall); begynne writeln("*"); hvis n > 0 så begynner F(n-3); F(n-2); F(n div 2); F(n div 2); ende ende ; Hvor mange stjerner vil bli skrevet ut på skjermen når du ringer F(6)? Svar: 97

Oppgave 6: Gitt en rekursiv algoritme: prosedyre F(n: heltall); begynne writeln("*"); hvis n > 0, begynn å skriveln("*"); F(n-2); F(n div 2); ende ende ; Hvor mange stjerner vil bli skrevet ut på skjermen når du ringer F(7)? Svar: 31

Oppgave 7: Gitt en rekursiv algoritme: prosedyre F(n: heltall); begynne writeln("*"); hvis n > 0, begynn å skriveln("*"); F(n-2); F(n div 2); F(n div 2); ende ende; Hvor mange stjerner vil bli skrevet ut på skjermen når du ringer F(7)? Svar: 81

Oppgave 8: Gitt en rekursiv algoritme: prosedyre F(n: heltall); begynne writeln("*"); hvis n > 0, begynn å skriveln("*"); F(n-2); F(n-2); F(n div 2); ende ende; Hvor mange stjerner vil bli skrevet ut på skjermen når du ringer F(6)? Svar: 77

Oppgave 9: Gitt en rekursiv algoritme: prosedyre F(n: heltall); start hvis n > 0 så begynner F(n-2); F(n-1); F(n-1); slutt; writeln("*"); slutt ; Hvor mange stjerner vil bli skrevet ut på skjermen når du ringer F(5)? Svar: 148

Oppgave 10: Gitt en rekursiv algoritme: prosedyre F(n: heltall); start hvis n > 0 så begynn writeln("*"); F(n-2); F(n-1); F(n-1); slutt; writeln("*"); slutt; Hvor mange stjerner vil bli skrevet ut på skjermen når du ringer F(5)? Svar: 197

Oppgave 11: Gitt en rekursiv algoritme: prosedyre F(n: heltall); start hvis n > 1 så begynner F(n-2); F(n-1); F(n div 2); slutt; writeln("*"); slutt ; Hvor mange stjerner vil bli skrevet ut på skjermen når du ringer F(7)? Svar: 88

Oppgave 12: Gitt en rekursiv algoritme: prosedyre F(n: heltall); start hvis n > 2 så begynn writeln("*"); F(n-2); F(n-1); F(n div 2); slutt ; writeln("*"); slutt; Hvor mange stjerner vil bli skrevet ut på skjermen når du ringer F(6)? Svar: 33

Oppgave 13: Gitt en rekursiv algoritme: prosedyre F (n: heltall); begynne å skriveln(n); hvis n

Oppgave 14: Gitt en rekursiv algoritme: prosedyre F (n: heltall); begynne å skriveln(n); hvis n

Oppgave 15: Gitt en rekursiv algoritme: prosedyre F (n: heltall); begynne å skriveln(n); hvis n

Oppgave 16: Gitt en rekursiv algoritme: prosedyre F (n: heltall); begynne å skriveln(n); hvis n

Oppgave 17: Gitt en rekursiv algoritme: prosedyre F (n: heltall); begynne å skriveln(n); hvis n

Oppgave 18: Gitt en rekursiv algoritme: prosedyre F (n: heltall); begynne å skriveln(n); hvis n

Oppgave 19: Gitt en rekursiv algoritme: prosedyre F (n: heltall); begynne å skriveln(n); hvis n

Oppgave 20: Gitt en rekursiv algoritme: prosedyre F (n: heltall); begynne å skriveln(n); hvis n

Oppgave 21: Gitt en rekursiv algoritme: prosedyre F (n: heltall); begynne å skriveln(n); hvis n

Oppgave 22: Gitt en rekursiv algoritme: prosedyre F (n: heltall); begynne å skriveln(n); hvis n

Oppgave 23: Gitt en rekursiv algoritme: prosedyre F (n: heltall); begynne å skriveln(n); hvis n

Oppgave 24: Gitt en rekursiv algoritme: prosedyre F (n: heltall); begynne å skriveln(n); hvis n

Oppgave 25: Gitt en rekursiv algoritme: prosedyre F (n: heltall); begynne å skriveln(n); hvis n