Moderne forståelse af rekursion: definition af funktionalitet og adgang til den udefra og fra denne funktionalitet. Det menes, at rekursion blev født af matematikere: faktorberegning, uendelige rækker, fraktaler, fortsatte brøker … Dog kan rekursion findes over alt. Objektive naturlove "betragter" rekursion som deres hovedalgoritme og udtryksform (eksistens) ikke så meget af den materielle verdens objekter, men generelt hovedalgoritmen for bevægelse.
Folk med forskellige specialer inden for forskellige områder af videnskab og teknologi bruger den rekursive algoritme f (x), hvor "x ~/=f (x)". En funktion, der kalder sig selv, er en stærk løsning, men at danne og forstå denne løsning er i de fleste tilfælde en meget vanskelig opgave.
I oldtiden blev rekursion brugt til at øge paladspladsen. Gennem et system af spejle rettet mod hinanden kan du skabe fantastiske tredimensionelle rumlige effekter. Men er det så nemt at forstå hvordanjustere disse spejle? Det er endnu sværere at bestemme, hvor et punkt i rummet er, reflekteret gennem flere spejle.
Rekursion, rekursive algoritmer: betydning og syntaks
Problemet, som er formuleret ved at gentage en sekvens af operationer, kan løses rekursivt. En simpel algoritme (beregning af en andengradsligning, et script til at udfylde en webside med information, læse en fil, sende en besked…) kræver ikke rekursion.
Vigtigste forskelle i algoritmen, der tillader en rekursiv løsning:
- der er en algoritme, der skal udføres flere gange;
- algoritmen har brug for data, der ændres hver gang;
- algoritmen behøver ikke at ændre sig hver gang;
- der er en endelig betingelse: Algoritmen er rekursiv - ikke uendelig.
Generelt kan det ikke argumenteres for, at engangsudførelse er en nødvendig betingelse for, at der ikke er en grund til rekursion. Du kan heller ikke kræve en obligatorisk slutbetingelse: uendelige rekursioner har deres eget omfang.
Algoritmen er rekursiv: når en sekvens af operationer udføres gentagne gange, på data, der ændres hver gang og giver et nyt resultat hver gang.
Rekursionsformel
Den matematiske forståelse af rekursion og dens analoge i programmering er anderledes. Matematik, selvom der er tegn på programmering, men programmering er matematik af en meget højere orden.
En velskrevet algoritme er som et spejl af forfatterens intellekt. Generelrekursionsformlen i programmering er "f(x)", hvor "x ~/=f(x)" har mindst to fortolkninger. Her er "~" ligheden eller fraværet af resultatet, og "=" er tilstedeværelsen af resultatet af funktionen.
Første mulighed: datadynamik.
- funktionen "f(x)" har en rekursiv og uforanderlig algoritme;
- "x" og resultatet "f(x)" har nye værdier hver gang, resultatet "f(x)" er den nye "x"-parameter for denne funktion.
Anden mulighed: kodedynamik.
- funktionen "f(x)" har flere algoritmer, der forfiner (analyserer) dataene;
- dataanalyse - en del af koden og implementering af rekursive algoritmer, der udfører den ønskede handling - den anden del af koden;
- resultatet af funktionen "f(x)" er ikke.
Intet resultat er norm alt. Programmering er ikke matematik, her behøver resultatet ikke at være eksplicit til stede. En rekursiv funktion kan simpelthen parse websteder og udfylde databasen eller instansiere objekter i henhold til det indgående input.
Data og rekursion
Programmering af rekursive algoritmer handler ikke om at beregne en faktor, hvor funktionen hver gang modtager en given værdi, der er én mere eller mindre end én - implementeringsmuligheden afhænger af udviklerens præference.
Det er lige meget, hvordan den faktorielle "8!"algoritme, der nøje følger denne formel.
Behandling af information er "matematik" af en helt anden rækkefølge. Rekursive funktioner og algoritmer her opererer på bogstaver, ord, sætninger, sætninger og afsnit. Hvert næste niveau bruger det forrige.
Inputdatastrømmen analyseres over en lang række forhold, men analyseprocessen er generelt rekursiv. Det giver ingen mening at skrive unikke algoritmer for alle varianter af inputstrømmen. Der skal være én funktionalitet. Her er rekursive algoritmer eksempler på, hvordan man danner en outputstrøm, der er tilstrækkelig til inputtet. Dette er ikke output fra den rekursive algoritme, men det er den ønskede og nødvendige løsning.
Abstraktion, rekursion og OOP
Objektorienteret programmering (OOP) og rekursion er fundament alt forskellige enheder, men de supplerer hinanden perfekt. Abstraktion har intet at gøre med rekursion, men gennem linsen af OOP skaber det mulighed for at implementere kontekstuel rekursion.
For eksempel bliver oplysninger analyseret, og bogstaver, ord, sætninger, sætninger og afsnit fremhæves separat. Udvikleren vil naturligvis sørge for oprettelse af forekomster af objekter af disse fem typer og tilbyde en løsning af rekursive algoritmer på hvert niveau.
I mellemtiden, hvis der på bogstavniveau "det ikke nytter noget at lede efter mening", så vises semantikken på ordniveau. Du kan opdele ord i verber, substantiver, adverbier, præpositioner… Du kan gå videre og definere kasus.
På sætningsniveau er semantik suppleret med tegnsætningstegn og logikordkombinationer. På sætningsniveau findes et mere perfekt niveau af semantik, og et afsnit kan betragtes som en komplet tanke.
Objektorienteret udvikling forudbestemmer arven af egenskaber og metoder og foreslår at starte hierarkiet af objekter med skabelsen af en fuldstændig abstrakt forfader. Samtidig vil analysen af hver efterkommer uden tvivl være rekursiv og vil ikke adskille sig for meget på det tekniske niveau i mange positioner (bogstaver, ord, sætninger og sætninger). Afsnit, ligesom fuldstændige tanker, kan skille sig ud fra denne liste, men de er ikke essensen.
Det er vigtigt, at den overvældende del af algoritmen kan formuleres på det abstrakte forfaderniveau, og forfine den på niveauet for hver efterkommer med data og metoder, der kaldes fra det abstrakte niveau. I denne sammenhæng åbner abstraktion nye horisonter for rekursion.
Historiske træk ved OOP
OOP er kommet til softwareverdenen to gange, selvom nogle eksperter måske fremhæver fremkomsten af cloud computing og moderne ideer om objekter og klasser som en ny runde i udviklingen af it-teknologier.
Begreberne "objekt" og "objektiv" i den moderne kontekst af OOP tilskrives norm alt 50'erne og 60'erne i det sidste århundrede, men de er forbundet med 1965 og fremkomsten af Simula, Lisp, Algol, Smalltalk.
I de dage var programmering ikke specielt udviklet og kunne ikke reagere tilstrækkeligt på revolutionære koncepter. Kampen mellem ideer og programmeringsstile (C/C ++ og Pascal - for det meste) var stadig langt væk, og databaser var stadig konceptuelt dannet.
I slutningen af 80'erne og begyndelsen af 90'erne dukkede objekter op i Pascal, og alle huskede klasser i C/C ++ - dette markerede en ny omgang interesse for OOP, og det var dengang, værktøjer, primært programmeringssprog, ikke blev understøtter kun objektorienterede ideer, men udvikler sig i overensstemmelse hermed.
Selvfølgelig, hvis tidligere rekursive algoritmer blot var funktioner, der blev brugt i programmets generelle kode, kunne rekursion nu blive en del af egenskaberne for et objekt (klasse), hvilket gav interessante muligheder i sammenhæng med arv.
Funktion af moderne OOP
Udviklingen af oprindeligt erklærede OOP-objekter (klasser) som samlinger af data og egenskaber (metoder). Faktisk handlede det om data, der har syntaks og mening. Men så var det ikke muligt at præsentere OOP som et værktøj til at styre rigtige objekter.
OOP er blevet et værktøj til at styre "computernatur"-objekter. Et script, en knap, et menupunkt, en menulinje, et tag i et browservindue er et objekt. Men ikke en maskine, et fødevareprodukt, et ord eller en sætning. Virkelige objekter er forblevet uden for objektorienteret programmering, og computerværktøjer har fået en ny inkarnation.
På grund af forskellene i populære programmeringssprog er der opstået mange dialekter af OOP. Med hensyn til semantik er de praktisk t alt ækvivalente, og deres fokus på den instrumentelle sfære, og ikke på den anvendte, gør det muligt at tage beskrivelsen af virkelige objekter ud overalgoritmer og sikre deres "eksistens" på tværs af platforme og på tværs af sprog.
Stakke og funktionsopkaldsmekanismer
Mekanismer til at kalde funktioner (procedurer, algoritmer) kræver videregivelse af data (parametre), returnering af et resultat og hukommelse af adressen på den operatør, der skal modtage kontrol efter funktionen (proceduren) er fuldført.
Norm alt bruges stakken til dette formål, selvom programmeringssprog eller udvikleren selv kan give en række muligheder for at overføre kontrol. Moderne programmering indrømmer, at navnet på en funktion ikke kun kan være en parameter: den kan dannes under udførelsen af algoritmen. En algoritme kan også oprettes, mens en anden algoritme udføres.
Konceptet med rekursive algoritmer, når deres navne og organer kan bestemmes på tidspunktet for dannelsen af opgaven (valg af den ønskede algoritme), udvider rekursiviteten ikke kun til, hvordan man gør noget, men også hvem der præcist skal gør det. At vælge en algoritme ved dets "meningsfulde" navn er lovende, men skaber vanskeligheder.
Rekursivitet på et sæt funktioner
Du kan ikke sige, at en algoritme er rekursiv, når den kalder sig selv, og det er det. Programmering er ikke et dogme, og begrebet rekursivitet er ikke et eksklusivt krav for at kalde dig selv fra kroppen af din egen algoritme.
Praktiske applikationer giver ikke altid en ren løsning. Ofte skal de indledende data forberedes, og resultatet af det rekursive kald skal analyseres i sammenhæng med hele problemet (hele algoritmen) isamlet.
Faktisk, ikke kun før en rekursiv funktion kaldes, men også efter at den er afsluttet, kan eller bør et andet program kaldes. Hvis der ikke er særlige problemer med kaldet: den rekursive funktion A() kalder funktionen B(), som gør noget og kalder A(), så er der straks et problem med returnering af kontrol. Efter at have gennemført det rekursive kald, skal funktion A() modtage kontrol for at genkalde B(), som vil kalde den igen. At returnere kontrollen som den skal være i orden på stakken tilbage til B() er den forkerte løsning.
Programmøren er ikke begrænset i valget af parametre og kan supplere dem med funktionsnavne. Med andre ord er den ideelle løsning at videregive navnet på B() til A() og lade A() selv kalde B(). I dette tilfælde vil der ikke være problemer med at returnere kontrol, og implementeringen af den rekursive algoritme vil være mere gennemsigtig.
Forståelse og niveau af rekursion
Problemet med at udvikle rekursive algoritmer er, at du skal forstå dynamikken i processen. Når du bruger rekursion i objektmetoder, især på niveau med en abstrakt forfader, er der et problem med at forstå din egen algoritme i sammenhæng med dens udførelsestid.
I øjeblikket er der ingen begrænsninger på indlejringsniveauet for funktioner og stakkapacitet i opkaldsmekanismer, men der er et problem med at forstå: på hvilket tidspunkt hvilket dataniveau eller hvilket sted i den generelle algoritme kaldet det rekursive funktion og på hvilket antal opkald hun selv er.
Eksisterende fejlfindingsværktøjer er ofte magtesløsefortæl programmøren den rigtige løsning.
løkker og rekursion
Det anses for, at cyklisk udførelse svarer til rekursion. I nogle tilfælde kan den rekursive algoritme faktisk implementeres i syntaksen af betingede og cykliske konstruktioner.
Men hvis der er en klar forståelse af, at en bestemt funktion skal implementeres gennem en rekursiv algoritme, bør enhver ekstern brug af en loop eller betingede sætninger opgives.
Betydningen her er, at en rekursiv løsning i form af en funktion, der bruger sig selv, vil være en komplet, funktionelt komplet algoritme. Denne algoritme vil kræve, at programmøren skaber den med indsats og forstår dynamikken i algoritmen, men det vil være den endelige løsning, der ikke kræver ekstern kontrol.
Enhver kombination af eksterne betingede og cykliske operatorer vil ikke tillade os at repræsentere den rekursive algoritme som en komplet funktion.
Rekursionskonsensus og OOP
I næsten alle varianter af udvikling af en rekursiv algoritme opstår der en plan om at udvikle to algoritmer. Den første algoritme genererer en liste over fremtidige objekter (instanser), og den anden algoritme er faktisk en rekursiv funktion.
Den bedste løsning ville være at arrangere rekursion som en enkelt egenskab (metode), der faktisk indeholder den rekursive algoritme, og lægge alt det forberedende arbejde ind i objektkonstruktøren.
En rekursiv algoritme vil kun være den rigtige løsning, når den virkerkun af ham selv, uden ekstern kontrol og styring. En ekstern algoritme kan kun give et signal om at virke. Resultatet af dette arbejde skulle være den forventede løsning uden ekstern support.
Rekursion bør altid være en komplet selvstændig løsning.
Intuitiv forståelse og funktionel fuldstændighed
Da objektorienteret programmering blev de facto-standarden, blev det indlysende, at for at kode effektivt, skal du ændre din egen tankegang. Programmøren skal bevæge sig fra sprogets syntaks og semantik til dynamikken i semantikken under udførelsen af algoritmen.
Karakteristisk for rekursion: det kan anvendes på alt:
- webskrabning;
- søgeoperationer;
- parsing tekstinformation;
- læse eller oprette MS Word-dokumenter;
- prøvetagning eller analyse af tags…
Karakteristisk for OOP: det gør det muligt at beskrive en rekursiv algoritme på niveau med en abstrakt forfader, men sørge for, at den refererer til unikke efterkommere, som hver har sin egen palet af data og egenskaber.
Rekursion er ideel, fordi den kræver den funktionelle fuldstændighed af dens algoritme. OOP forbedrer ydeevnen af en rekursiv algoritme ved at give den adgang til alle unikke børn.
