Moderne begrip van rekursie: definisie van funksionaliteit en toegang daartoe van buite en van hierdie funksionaliteit. Daar word geglo dat rekursie deur wiskundiges gebore is: faktoriaalberekening, oneindige reekse, fraktale, voortgesette breuke … Rekursie kan egter oral gevind word. Objektiewe natuurwette "beskou" rekursie as hul hoofalgoritme en uitdrukkingsvorm (bestaan) nie soseer van die objekte van die materiële wêreld nie, maar oor die algemeen die hoofalgoritme van beweging.
Mense van verskeie spesialiteite in verskeie velde van wetenskap en tegnologie gebruik die rekursiewe algoritme f (x), waar "x ~/=f (x)". 'n Funksie wat homself noem, is 'n sterk oplossing, maar om hierdie oplossing te vorm en te verstaan is in die meeste gevalle 'n baie moeilike taak.
In antieke tye is rekursie gebruik om die paleisruimte te vergroot. Deur 'n stelsel van spieëls wat op mekaar gerig is, kan jy verstommende driedimensionele ruimtelike effekte skep. Maar is dit so maklik om te verstaan hoeVerstel hierdie spieëls? Dit is selfs moeiliker om te bepaal waar 'n punt in die ruimte is, wat deur verskeie spieëls weerkaats word.
Rekursie, rekursiewe algoritmes: betekenis en sintaksis
Die probleem, wat geformuleer word deur 'n reeks bewerkings te herhaal, kan rekursief opgelos word. 'n Eenvoudige algoritme (die berekening van 'n kwadratiese vergelyking, 'n skrif om 'n webbladsy met inligting te vul, 'n lêer te lees, 'n boodskap te stuur…) vereis nie rekursie nie.
Belangrikste verskille van die algoritme wat 'n rekursiewe oplossing toelaat:
- daar is 'n algoritme wat verskeie kere uitgevoer moet word;
- algoritme benodig data wat elke keer verander;
- die algoritme hoef nie elke keer te verander nie;
- daar is 'n finale voorwaarde: die algoritme is rekursief - nie oneindig nie.
Oor die algemeen kan daar nie aangevoer word dat eenmalige teregstelling 'n noodsaaklike voorwaarde is vir die afwesigheid van 'n rede vir rekursie nie. Jy kan ook nie 'n verpligte finale voorwaarde vereis nie: oneindige rekursies het hul eie omvang.
Die algoritme is rekursief: wanneer 'n reeks bewerkings herhaaldelik uitgevoer word, op data wat elke keer verander en elke keer 'n nuwe resultaat gee.
Rekursieformule
Die wiskundige begrip van rekursie en sy analoog in programmering is anders. Wiskunde, hoewel daar tekens van programmering is, maar programmering is wiskunde van 'n baie hoër orde.
'n Goedgeskrewe algoritme is soos 'n spieël van die intellek van sy outeur. Algemeendie rekursieformule in programmering is "f(x)", waar "x ~/=f(x)" ten minste twee interpretasies het. Hier is "~" die ooreenkoms of afwesigheid van die resultaat, en "=" is die teenwoordigheid van die resultaat van die funksie.
Eerste opsie: datadinamika.
- funksie "f(x)" het 'n rekursiewe en onveranderlike algoritme;
- "x" en die resultaat "f(x)" het elke keer nuwe waardes, die resultaat "f(x)" is die nuwe "x" parameter van hierdie funksie.
Tweede opsie: kodedinamika.
- funksie "f(x)" het verskeie algoritmes wat die data verfyn (ontleed);
- data-analise - een deel van die kode en die implementering van rekursiewe algoritmes wat die verlangde aksie uitvoer - die tweede deel van die kode;
- die resultaat van die funksie "f(x)" is nie.
Geen resultaat is normaal nie. Programmering is nie wiskunde nie, hier hoef die resultaat nie eksplisiet teenwoordig te wees nie. 'n Rekursiewe funksie kan bloot webwerwe ontleed en die databasis vul, of voorwerpe instansieer volgens die inkomende invoer.
Data en rekursie
Programmering van rekursiewe algoritmes gaan nie oor die berekening van 'n faktoriaal, waarin die funksie elke keer 'n gegewe waarde ontvang wat een meer of minder as een is nie - die implementering-opsie hang af van die ontwikkelaar se voorkeur.
Dit maak nie saak hoe die faktoriale "8!",algoritme wat hierdie formule streng volg.
Die verwerking van inligting is "wiskunde" van 'n heeltemal ander orde. Rekursiewe funksies en algoritmes werk hier op letters, woorde, frases, sinne en paragrawe. Elke volgende vlak gebruik die vorige een.
Die insetdatastroom word oor 'n wye reeks toestande ontleed, maar die ontledingsproses is oor die algemeen rekursief. Dit maak geen sin om unieke algoritmes vir alle variante van die invoerstroom te skryf nie. Daar moet een funksionaliteit wees. Hier is rekursiewe algoritmes voorbeelde van hoe om 'n uitsetstroom te vorm wat voldoende is vir die insette. Dit is nie die uitset van die rekursiewe algoritme nie, maar dit is die gewenste en nodige oplossing.
Abstraksie, rekursie en OOP
Objekgeoriënteerde programmering (OOP) en rekursie is fundamenteel verskillende entiteite, maar hulle vul mekaar perfek aan. Abstraksie het niks met rekursie te doen nie, maar deur die lens van OOP skep dit die moontlikheid om kontekstuele rekursie te implementeer.
Inligting word byvoorbeeld ontleed en letters, woorde, frases, sinne en paragrawe word afsonderlik uitgelig. Uiteraard sal die ontwikkelaar voorsiening maak vir die skepping van gevalle van voorwerpe van hierdie vyf tipes en 'n oplossing van rekursiewe algoritmes op elke vlak bied.
Intussen, as op die vlak van letters “daar geen sin is om betekenis te soek nie”, dan verskyn semantiek op die vlak van woorde. Jy kan woorde verdeel in werkwoorde, selfstandige naamwoorde, bywoorde, voorsetsels… Jy kan verder gaan en gevalle definieer.
Op frasevlak word semantiek aangevul met leestekens en logikawoordkombinasies. Op die vlak van sinne word 'n meer perfekte vlak van semantiek gevind, en 'n paragraaf kan as 'n volledige gedagte beskou word.
Objekgeoriënteerde ontwikkeling bepaal vooraf die oorerwing van eienskappe en metodes en stel voor om die hiërargie van objekte te begin met die skepping van 'n heeltemal abstrakte voorouer. Terselfdertyd, ongetwyfeld, sal die ontleding van elke afstammeling rekursief wees en sal dit nie op tegniese vlak in baie posisies (letters, woorde, frases en sinne) te veel verskil nie. Paragrawe, soos volledige gedagtes, mag dalk uit hierdie lys uitstaan, maar dit is nie die essensie nie.
Dit is belangrik dat die oorweldigende deel van die algoritme op die abstrakte voorouervlak geformuleer kan word, en dit verfyn op die vlak van elke afstammeling met data en metodes wat vanaf die abstrakte vlak genoem word. In hierdie konteks maak abstraksie nuwe horisonne vir rekursie oop.
Historiese kenmerke van OOP
OOP het twee keer na die wêreld van sagteware gekom, hoewel sommige kenners die opkoms van wolkrekenaarkunde en moderne idees oor voorwerpe en klasse dalk uitsonder as 'n nuwe rondte in die ontwikkeling van IT-tegnologie.
Die terme "objek" en "objektief" in die moderne konteks van OOP word gewoonlik toegeskryf aan die 50's en 60's van die vorige eeu, maar dit word geassosieer met 1965 en die opkoms van Simula, Lisp, Algol, Smalltalk.
In daardie dae was programmering nie besonder ontwikkel nie en kon dit nie voldoende op revolusionêre konsepte reageer nie. Die stryd van idees en programmeringstyle (C / C ++ en Pascal - meestal) was nog ver weg, en databasisse is steeds konseptueel gevorm.
In die laat 80's en vroeë 90's het voorwerpe in Pascal verskyn en almal het klasse in C / C ++ onthou - dit was 'n nuwe rondte van belangstelling in OOP en dit was toe dat nutsmiddels, hoofsaaklik programmeertale, nie ondersteun slegs objekgeoriënteerde idees, maar ontwikkel dienooreenkomstig.
Natuurlik, as vroeëre rekursiewe algoritmes net funksies was wat in die algemene kode van die program gebruik is, kan rekursie nou deel word van die eienskappe van 'n objek (klas), wat interessante geleenthede in die konteks van oorerwing gebied het.
Kenmerk van moderne OOP
Die ontwikkeling van OOP het aanvanklik objekte (klasse) as versamelings van data en eienskappe (metodes) verklaar. Trouens, dit het gegaan oor data wat sintaksis en betekenis het. Maar toe was dit nie moontlik om OOP as 'n instrument vir die bestuur van regte voorwerpe aan te bied nie.
OOP het 'n hulpmiddel geword vir die bestuur van "rekenaarnatuur"-voorwerpe. 'n Skrip, 'n knoppie, 'n kieslys-item, 'n kieslysbalk, 'n merker in 'n blaaiervenster is 'n voorwerp. Maar nie 'n masjien, 'n voedselproduk, 'n woord of 'n sin nie. Werklike voorwerpe het buite objekgeoriënteerde programmering gebly, en rekenaargereedskap het 'n nuwe inkarnasie aangeneem.
As gevolg van die verskille in gewilde programmeertale, het baie dialekte van OOP na vore gekom. Wat semantiek betref, is hulle feitlik ekwivalent, en hul fokus op die instrumentele sfeer, en nie op die toegepaste een nie, maak dit moontlik om die beskrywing van werklike objekte verder te neemalgoritmes en verseker hul kruisplatform- en kruistaal-"bestaan".
Stapels en funksie-oproepmeganismes
Meganismes vir die oproep van funksies (prosedures, algoritmes) vereis die deurgee van data (parameters), die terugstuur van 'n resultaat, en die onthou van die adres van die operateur wat beheer moet ontvang nadat die funksie (prosedure) voltooi is.
Gewoonlik word die stapel vir hierdie doel gebruik, hoewel programmeertale of die ontwikkelaar self 'n verskeidenheid opsies vir die oordrag van beheer kan bied. Moderne programmering gee toe dat die naam van 'n funksie nie net 'n parameter kan wees nie: dit kan gevorm word tydens die uitvoering van die algoritme. 'n Algoritme kan ook geskep word terwyl 'n ander algoritme uitgevoer word.
Die konsep van rekursiewe algoritmes, wanneer hul name en liggame bepaal kan word ten tye van die vorming van die taak (die keuse van die verlangde algoritme), brei rekursiwiteit nie net uit na hoe om iets te doen nie, maar ook wie presies moet doen dit. Die keuse van 'n algoritme met sy "betekenisvolle" naam is belowend, maar skep probleme.
Rekursiwiteit op 'n stel funksies
Jy kan nie sê dat 'n algoritme rekursief is wanneer dit homself noem en dit is dit nie. Programmering is nie 'n dogma nie, en die konsep van rekursiwiteit is nie 'n eksklusiewe vereiste om jouself uit die liggaam van jou eie algoritme te noem nie.
Praktiese toepassings gee nie altyd 'n skoon oplossing nie. Dikwels moet die aanvanklike data voorberei word, en die resultaat van die rekursiewe oproep moet ontleed word in die konteks van die hele probleem (die hele algoritme) inalgeheel.
Trouens, nie net voordat 'n rekursiewe funksie geroep word nie, maar ook nadat dit voltooi is, kan of moet 'n ander program geroep word. As daar geen spesiale probleme met die oproep is nie: die rekursiewe funksie A() roep die funksie B(), wat iets doen en roep A(), dan is daar dadelik 'n probleem met die terugkeer van beheer. Nadat die rekursiewe oproep voltooi is, moet funksie A() beheer ontvang om B() weer te roep, wat dit weer sal oproep. Om beheer soos dit in orde moet wees op die stapel terug te keer na B() is die verkeerde oplossing.
Die programmeerder is nie beperk in die keuse van parameters nie en kan dit met funksiename voltooi. Met ander woorde, die ideale oplossing is om die naam van B() na A() oor te dra en A() self B() te laat noem. In hierdie geval sal daar geen probleme met die terugkeer van beheer wees nie, en die implementering van die rekursiewe algoritme sal meer deursigtig wees.
Begrip en vlak van rekursie
Die probleem met die ontwikkeling van rekursiewe algoritmes is dat jy die dinamika van die proses moet verstaan. Wanneer rekursie in objekmetodes gebruik word, veral op die vlak van 'n abstrakte voorouer, is daar 'n probleem om jou eie algoritme te verstaan in die konteks van die uitvoering daarvan.
Daar is tans geen beperkings op die nesvlak van funksies en stapelkapasiteit in oproepmeganismes nie, maar daar is 'n probleem om te verstaan: op watter tydstip watter datavlak of watter plek in die algemene algoritme die rekursiewe genoem word funksie en op watter aantal oproepe sy self is.
Bestaande ontfoutingsnutsgoed is dikwels kragteloosvertel die programmeerder die regte oplossing.
Lusse en rekursie
Daar word beskou dat sikliese uitvoering gelykstaande is aan rekursie. Inderdaad, in sommige gevalle kan die rekursiewe algoritme geïmplementeer word in die sintaksis van voorwaardelike en sikliese konstrukte.
As daar egter 'n duidelike begrip is dat 'n spesifieke funksie deur 'n rekursiewe algoritme geïmplementeer moet word, moet enige eksterne gebruik van 'n lus of voorwaardelike stellings laat vaar word.
Die betekenis hier is dat 'n rekursiewe oplossing in die vorm van 'n funksie wat homself gebruik, 'n volledige, funksioneel volledige algoritme sal wees. Hierdie algoritme sal vereis dat die programmeerder dit met moeite skep en die dinamika van die algoritme verstaan, maar dit sal die finale oplossing wees wat nie eksterne beheer vereis nie.
Enige kombinasie van eksterne voorwaardelike en sikliese operateurs sal ons nie toelaat om die rekursiewe algoritme as 'n volledige funksie voor te stel nie.
Rekursie-konsensus en OOP
In byna alle variante van die ontwikkeling van 'n rekursiewe algoritme, ontstaan 'n plan om twee algoritmes te ontwikkel. Die eerste algoritme genereer 'n lys van toekomstige voorwerpe (gevalle), en die tweede algoritme is eintlik 'n rekursiewe funksie.
Die beste oplossing sal wees om rekursie te rangskik as 'n enkele eienskap (metode) wat eintlik die rekursiewe algoritme bevat, en al die voorbereidingswerk in die objekkonstruktor te plaas.
'n Rekursiewe algoritme sal net die regte oplossing wees wanneer dit werkslegs deur homself, sonder eksterne beheer en bestuur. 'n Eksterne algoritme kan slegs 'n sein gee om te werk. Die resultaat van hierdie werk behoort die verwagte oplossing te wees, sonder eksterne ondersteuning.
Rekursie moet altyd 'n volledige losstaande oplossing wees.
Intuïtiewe begrip en funksionele volledigheid
Toe objekgeoriënteerde programmering die de facto-standaard geword het, het dit duidelik geword dat jy jou eie denke moet verander om effektief te kodeer. Die programmeerder moet beweeg van die sintaksis en semantiek van die taal na die dinamika van die semantiek tydens die uitvoering van die algoritme.
Kenmerk van rekursie: dit kan op alles toegepas word:
- webskraap;
- soekbewerkings;
- ontleding van teksinligting;
- lees of skep van MS Word-dokumente;
- steekproefneming of ontleding van merkers…
Kenmerk van OOP: dit maak dit moontlik om 'n rekursiewe algoritme op die vlak van 'n abstrakte voorouer te beskryf, maar maak voorsiening daarvoor dat dit verwys na unieke afstammelinge, wat elkeen sy eie palet van data en eienskappe het.
Rekursie is ideaal omdat dit die funksionele volledigheid van sy algoritme vereis. OOP verbeter die werkverrigting van 'n rekursiewe algoritme deur dit toegang tot alle unieke kinders te gee.
