Recursie in toegankelijke taal. Recursie. Opleidingstaken

Varg zegt:

Goedemiddag, ik begrijp echt niet hoe deze functie berekeningen uitvoert.

{
als (n==1) 1 retourneert; //als de nieuwe waarde 1 is, dan voegen we deze toe met 1, en niet met de vorige. omdat de vorige is nul. en de optelling 1+0 zal oneindig zijn.
anders retourneert som(n-1)+n; //maar als n>1, tel deze dan op met de vorige waarde gelijk aan de som van alle elementen tot n
}

Volgens mijn begrip, in n zijn er 5, komt de voorwaarde niet overeen en is er aan voldaan deze code som(n-1)+n dat wil zeggen, iets dat tussen haakjes door aftrekken wordt verkregen, wordt opgeteld bij 5, maar wat is (5 - 1)+5 en zo ja, wat stopt deze rekenkundige bewerking:?: :?: :?: Wat is de vorige waarde, waar komt deze vandaan, waar is deze gelijk aan:?: :?: :?:

Ja, bijna alles is zoals ik het begreep (in de laatste paragraaf liet je recursie zien))), maar de vraag blijft: hoe wordt de som verkregen, die vervolgens op het scherm wordt weergegeven?
Ik werk voor mij met Dev C++ dit voorbeeld geeft de som ==15 weer, als je deze telt zoals geschreven in het voorbeeld, dan blijkt de som anders te zijn.
Ik schreef hierboven, laten we (5-1)+5=4+5=9 nemen

:
1+2+3+4+5 = 15. Het voorbeeld wordt correct uitgevoerd.

(5) //We hebben 5 aan de functie gegeven en gecontroleerd of deze gelijk is aan één. niet gelijk, noem de functie opnieuw en geef er 5-1 aan door
(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, klaar met het aanroepen van de functie.
(2-1+(3-1+(4-1+(5-1+(5))))) == 15
dit is het resultaat.
Hier is het resultaat van de functie het verschil tussen de eerste twee getallen, en n is de rest van de rechterkant
__________________________________
U hoeft alleen maar de functie correct te begrijpen en deze als een berekende waarde te accepteren en niet als een variabele. Het lijkt op een variabele, maar dichter bij een berekende constante. Hoewel het geen constante is, is het gewoon handiger om het op deze manier waar te nemen.

Ja, ja, ja, ik had geen tijd om te schrijven dat ik het begreep, alles klopt, er kwam iets niet meteen door. Bedankt goede site))

En het is nog steeds niet helemaal logisch dat als je op de 8e regel het geretourneerde getal wijzigt van return 1 naar 2, het bedrag verandert naar 16. Hoe verhoudt deze voorwaarde zich tot de 9e regel?
Ook hiermee is alles duidelijk, alleen rendement 2 voegt als het ware zijn ontbering toe aan de som.

:
niet de extra ster, maar deze twee, en als je -3 schrijft, worden bij het optellen de drie afgetrokken, enz.
De hele logica is dat elke recursieve functie een terugkeerpunt nodig heeft.
Het verband met de negende regel is dat bij recursieve oproepen vanuit de hoofdlijn een getal wordt doorgegeven aan de somfunctie, dit getal wordt elke keer met één (n-1) verminderd, dit resultaat n-1 wordt gecontroleerd op gelijkheid met de negende regel; één en als de gelijkheid waar is, wordt het gehele ontvangen bedrag opgeteld bij het getal in dat rendement. anders wordt het gehele totaal opgeteld bij deze nieuwe n-1

Recursie is een vrij algemeen verschijnsel dat niet alleen in de wetenschap voorkomt, maar ook in de wetenschap het dagelijks leven. Bijvoorbeeld het Droste-effect, de Sierpinski-driehoek, enz. De eenvoudigste manier om recursie te zien is door de webcamera natuurlijk op het beeldscherm van de computer te richten, nadat u deze eerst hebt ingeschakeld. De camera zal dus het beeld van het computerscherm opnemen en op dit scherm weergeven, het zal zoiets als een gesloten lus zijn. Als resultaat zullen we iets zien dat lijkt op een tunnel.

Bij het programmeren is recursie nauw verwant aan functies; preciezer gezegd, het is dankzij functies bij het programmeren dat er zoiets bestaat als recursie of recursieve functie. In eenvoudige woorden, recursie is de definitie van een deel van een functie (methode) via zichzelf, dat wil zeggen, het is een functie die zichzelf aanroept, direct (in zijn lichaam) of indirect (via een andere functie). Typisch recursieve problemen zijn de taken: het vinden van n!, Fibonacci-getallen. We hebben dergelijke problemen al opgelost, maar met behulp van lussen, dat wil zeggen iteratief. Over het algemeen kan alles dat iteratief wordt opgelost, recursief worden opgelost, dat wil zeggen met behulp van een recursieve functie. De hele oplossing komt neer op het oplossen van het hoofdscenario, of, zoals het ook wel wordt genoemd, het basisscenario. Er bestaat zoiets als een recursiestap of een recursieve oproep. In het geval dat een recursieve functie wordt aangeroepen om een complex probleem op te lossen (niet het basisscenario), zal een bepaald aantal recursieve oproepen of stappen om een taak tot een eenvoudiger taak terug te brengen. En zo verder totdat we het krijgen basisoplossing. Laten we een programma ontwikkelen dat een recursieve functie declareert die n berekent!

"stdafx.h" #include << "Enter n!: "; cin >>n;<< n << "!" << "=" << factorial(n) << endl; // вызов рекурсивной функции system("pause"); return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 cout << "Step\t" << i << endl; i++; // операция инкремента шага рекурсивных вызовов cout << "Result= " << result << endl; result = f * factorial(f - 1); // функция вызывает саму себя, причём её аргумент уже на 1 меньше return result; }

uit

// code Code::Blokken

// Dev-C++-code naamruimte std gebruiken; niet-ondertekende lange int faculteit(niet-ondertekende lange int); prototype van een recursieve functie int i = 1; // initialiseren van een globale variabele om het aantal recursieve aanroepen te tellen met een niet-ondertekend lang int-resultaat; // globale variabele voor het opslaan van het geretourneerde resultaat van de recursieve functie int main(int argc, char* argv) ( int n; // lokale variabele voor het doorgeven van het ingevoerde getal via het toetsenbord cout<< "Enter n!: "; cin >>n;<< n << "!" << "=" << factorial(n) << endl; // вызов рекурсивной функции return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 cout << "Step\t" << i << endl; i++; // операция инкремента шага рекурсивных вызовов cout << "Result= " << result << endl; result = f * factorial(f - 1); // функция вызывает саму себя, причём её аргумент уже на 1 меньше return result; }

IN lijnen 7, 9, 21 Het gegevenstype wordt unsigned long int verklaard, omdat de waarde van de faculteit zeer snel toeneemt, bijvoorbeeld al 10! = 3.628.800 Als de grootte van het gegevenstype niet voldoende is, is het resultaat een volledig onjuiste waarde. De code declareert meer operatoren dan nodig zijn om n! te vinden. Dit wordt gedaan zodat het programma na uitvoering laat zien wat er bij elke stap van de recursieve aanroepen gebeurt. Let op de gemarkeerde coderegels, lijnen 23, 24, 28 is een recursieve oplossing voor n!. Lijnen 23, 24 zijn de basisoplossing voor een recursieve functie, dat wil zeggen zodra de waarde in de variabele aanwezig is F gelijk zal zijn aan 1 of 0 (aangezien we weten dat 1! = 1 en 0! = 1), zullen de recursieve oproepen stoppen en zullen de waarden voor elke recursieve oproep worden geretourneerd. Wanneer de waarde voor de eerste recursieve aanroep terugkeert, retourneert het programma de waarde van de berekende faculteit. IN lijn 28 de functie factorial() roept zichzelf aan, maar zijn argument is er één minder. Het argument wordt elke keer gereduceerd om tot een bepaalde oplossing te komen. Het resultaat van het programma (zie figuur 1).

Voer n! in: 5 Stap 1 Resultaat= 0 Stap 2 Resultaat= 0 Stap 3 Resultaat= 0 Stap 4 Resultaat= 0 5!=120

Figuur 1 - Recursie in C++

Op basis van het resultaat van het programma is elke stap duidelijk zichtbaar en is het resultaat bij elke stap nul, behalve bij de laatste recursieve aanroep. Het was noodzakelijk om vijf faculteiten te berekenen. Het programma voerde vier recursieve oproepen uit en bij de vijfde oproep werd het basisscenario gevonden. En toen het programma eenmaal een oplossing had voor het basisscenario, loste het de voorgaande stappen op en leverde het het algehele resultaat op. In Figuur 1 zijn slechts vier stappen zichtbaar omdat in de vijfde stap een deeloplossing werd gevonden, die uiteindelijk de eindoplossing opleverde, namelijk 120. Figuur 2 toont het recursieve rekenschema 5!. Het diagram laat duidelijk zien dat het eerste resultaat wordt geretourneerd wanneer een bepaalde oplossing wordt bereikt, maar niet onmiddellijk na elke recursieve aanroep.

Figuur 2 - Recursie in C++

Dus om er 5 te vinden! moet er 4 weten! en vermenigvuldig het met 5; 4! = 4 * 3! enzovoort. Volgens het diagram in figuur 2 wordt de berekening beperkt tot het vinden van een speciaal geval, dat wil zeggen 1!, waarna de waarden beurtelings worden teruggegeven aan elke recursieve oproep. De laatste recursieve aanroep retourneert de waarde 5!.

Laten we het programma voor het vinden van de faculteit herwerken, zodat we een tabel met faculteiten krijgen. Om dit te doen, zullen we een for-lus declareren waarin we de recursieve functie zullen aanroepen.

naamruimte std gebruiken; niet-ondertekende lange int faculteit(niet-ondertekende lange int); prototype van een recursieve functie int i = 1; // initialiseren van een globale variabele om het aantal recursieve aanroepen te tellen met een niet-ondertekend lang int-resultaat; // globale variabele voor het opslaan van het geretourneerde resultaat van de recursieve functie int main(int argc, char* argv) ( int n; // lokale variabele voor het doorgeven van het ingevoerde getal via het toetsenbord cout<< "Enter n!: "; cin >>n;<= n; k++) { cout << k << "!" << "=" << factorial(k) << endl; // вызов рекурсивной функции } system("pause"); return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 //cout << "Step\t"<< i <>n;<= n; k++) { cout << k << "!" << "=" << factorial(k) << endl; // вызов рекурсивной функции } return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 //cout << "Step\t"<< i <> <= entered_number; counter++) cout << setw(2) <

uit

// code Code::Blokken

// fibonacci.cpp: definieert het toegangspunt voor de consoletoepassing. #include "stdafx.h" #include // fibonacci.cpp: definieert het toegangspunt voor de consoletoepassing. #erbij betrekken // bibliotheek voor opmaakinformatie die op het scherm wordt weergegeven #include<< "Enter number from the Fibonacci series: "; cin >naamruimte std gebruiken; unsigned long fibonacci(unsigned long); // prototype van een recursieve functie voor het zoeken naar getallen uit de Fibonacci-reeks int main(int argc, char* argv) ( unsigned long enter_number; cout<= entered_number; counter++) cout << setw(2) <

Laten we zeggen dat je drie schijven van de eerste staaf naar de derde moet verplaatsen, wat betekent dat de tweede staaf een hulpschijf is. Een visuele oplossing voor dit probleem is geïmplementeerd in Flash. Klik op de startknop om de animatie te starten, op de stopknop om deze te stoppen.

Het programma moet worden geschreven voor het zoveelste aantal schijven. Omdat we dit probleem recursief oplossen, moeten we eerst speciale gevallen van de oplossing vinden. In dit probleem is er maar één speciaal geval: dit is wanneer het nodig is om slechts één schijf te verplaatsen, en in dit geval is zelfs een hulpstang niet nodig, maar daar besteden we eenvoudigweg geen aandacht aan. Nu is het nodig om een recursieve oplossing te organiseren als het aantal schijven meer dan één is. Laten we wat notatie invoeren om niet te veel te schrijven:

<Б> — de stang waarop de schijven zich aanvankelijk bevinden (basisstang);
<П> - hulp- of tussenstang;
<Ф> — laatste staaf – de staaf waarnaar de schijven moeten worden verplaatst.

Verder zullen we bij het beschrijven van het algoritme voor het oplossen van het probleem deze notaties gebruiken. Om drie schijven te verplaatsen <Б> op <Ф> we moeten eerst de twee schijven verplaatsen <Б> op <П> en verplaats vervolgens de derde schijf (de grootste) naar <Ф> , omdat <Ф> vrij

Om te bewegen N schijven mee <Б> op <Ф> we moeten eerst verhuizen n-1 schijven mee <Б> op <П> en verplaats vervolgens de zoveelste schijf (de grootste) naar <Ф> , omdat <Ф> vrij Hierna moet je verhuizen n-1 schijven mee <П> op <Ф> , terwijl u de staaf gebruikt <Б> als hulpstuk. Deze drie acties vormen het volledige recursieve algoritme. Hetzelfde algoritme in pseudocode:
n-1 verhuizen naar <П>
N verhuizen naar <Ф>
n-1 verhuizen van <П> op <Ф> , tijdens het gebruik <Б> als hulpstuk

// hanoi_tower.cpp: definieert het toegangspunt voor de consoletoepassing. // Een programma dat recursief het probleem van de Toren van Hanoi oplost #include "stdafx.h" #include #erbij betrekken naamruimte std gebruiken; lege toren(int, int, int, int); // declaratie van een prototype van een recursieve functie int count = 1; // globale variabele voor het tellen van het aantal stappen int _tmain(int argc, _TCHAR* argv) ( cout<< "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >>nummer;<< "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >uit<< "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> basis_rod;<< setw(2) << count << ") "<< baza << " " << "->" << " " << new_baza << endl; count++; } else { tower(count_disk -1, baza, new_baza, help_baza); // перемещаем все диски кроме самого последнего на вспомогательный стержень tower(1, baza, help_baza, new_baza); // перемещаем последний диск с начального стержня на финальный стержень tower(count_disk -1, help_baza, baza, new_baza); // перемещаем все диски со вспомогательного стержня на финальный } }

uit

// code Code::Blokken

uit #erbij betrekken > laatste_rod;<< "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >>nummer;<< "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >uit<< "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> laatste_rod;<< setw(2) << count << ") "<< baza << " " << "->" << " " << new_baza << endl; count++; } else { tower(count_disk -1, baza, new_baza, help_baza); // перемещаем все диски кроме самого последнего на вспомогательный стержень tower(1, baza, help_baza, new_baza); // перемещаем последний диск с начального стержня на финальный стержень tower(count_disk -1, help_baza, baza, new_baza); // перемещаем все диски со вспомогательного стержня на финальный } }

int help_rod;

// blok voor het bepalen van het nummer van de hulpstaaf, analyse van de nummers van de begin- en eindstaaf if (basic_rod != 2 && final_rod != 2) help_rod = 2;

anders als (basic_rod != 1 && final_rod != 1) help_rod = 1;

anders als (basic_rod != 3 && final_rod != 3) help_rod = 3;tower(// lancering van een recursieve functie voor het oplossen van het probleemnummer van de Towers of Hanoi, // een variabele die het aantal schijven opslaat dat verplaatst moet worden basic_rod, // een variabele die het nummer van de staaf opslaat waarop de schijven aanvankelijk zullen staan gelokaliseerde help_rod , // een variabele die het nummer van de staaf opslaat, die wordt gebruikt als een extra final_rod); // variabele die het nummer opslaat van de staaf waarnaar de schijven moeten worden verplaatst, return 0; ) void tower(int count_disk, int baza, int help_baza, int new_baza) ( if (count_disk == 1) // voorwaarde voor het beëindigen van recursieve oproepen ( cout

Figuur 5 toont een voorbeeld van het recursieve programma Tower of Hanoi. Eerst hebben we het aantal schijven ingevoerd dat gelijk is aan drie, daarna hebben we de basisstaaf ingevoerd (eerste) en de laatste staaf aangewezen (derde). Automatisch werd de tweede hengel een hulphengel. Het programma leverde een resultaat op dat volledig samenvalt met de geanimeerde oplossing voor dit probleem.

Om niet één groot artikel te schrijven, waarin talloze voorbeelden van recursie in C++ zullen voorkomen, zal ik hier nog een voorbeeld van recursie schrijven. Over het algemeen kunnen degenen die de basisprincipes en het gebruik van directe recursie in hun functies begrijpen, dit materiaal overslaan. Hier is een voorbeeld van het gebruik van recursie, zoals in het artikel Functies in C++ voor beginners. Recursie

Probleem 1 – Gebruik recursie om de faculteit van een getal van 1 tot N weer te geven
Code schrijven
=============================
FASE nr. 1 schrijf een leeg programma
=============================

#erbij betrekken

int hoofd()
{
systeem("cls");

haal();
retour 0;
}

Er is een leeg programma gemaakt, ik denk dat het niet nodig is commentaar te geven
FASE nr. 2: we schrijven, we schrijven de recursieve functie zelf
=========================================

#erbij betrekken

//Onze recursieve functie
int feit (int N)
{

//0! = 1, 1!=1, 2!=2, 3!=6... Omdat de eerste 2 cijfers zijn enen en staan niet in strikte volgorde, we forceren dit punt in de code

als n<2 return 1 ;
anders retour n * feit(n–1) // hier roept de functie zichzelf aan

}

int hoofd()
{
systeem("cls");
uit<// Aanroeppunt van de recursieve functie. Faculteit 10 op het scherm weergeven
haal();
retour 0;
}
ddd
============

Het belangrijkste onderdeel van een C++-recursieprogramma
retour n * feit(n–1)

Onze functie herberekent om de vorige waarde te verkrijgen. De echte waarde is de parameter waaraan wordt doorgegeven N vanaf het punt van de functieaanroep. Het punt van het aanroepen van onze functie is om deze aan te roepen vanuit het hoofdblok van het programma. In ons geval noemen we het vanuit een functie int hoofd()
Waarom schrijf ik niet de volgende, maar de vorige? Wanneer getallen worden vermenigvuldigd, dan is eerst 0 * 1, hier is onze huidige waarde 1, en nul is de vorige berekeningswaarde. Dit is de hele essentie van recursie: we berekenen de huidige waarde met behulp van de vorige, terwijl de vorige waarde door dezelfde berekening wordt verkregen. De compiler berekent zelf de vorige waarde en slaat deze waarde op in het geheugen. Het enige wat wij hoeven te doen is instructies geven. . Dankzij deze functie van compilers kan een functie die een instructie tegenkomt om zichzelf aan te roepen (in ons geval feit(n–1) ) overschrijft de doorgegeven parameter niet N om de functie te berekenen. De parameter doorgegeven aan N het blijft in het geheugen. In dit geval wordt bovendien een ander geheugengebied gedefinieerd waarin onze recursieve functie recursieve berekeningen uitvoert om het vorige resultaat te verkrijgen.

Mogen de programmeurs mij vergeven voor zo'n opgekauwd oordeel. Dit is ongeveer hoe beginners recursie waarnemen.

Ik hoop dat deze C++-blog voor beginners nuttig was voor iemand en iemand hielp het basisconcept van een recursieve functie in C++ te begrijpen

Opmerking. In dit artikel heb ik, net als in het vorige, de berekening niet uitgevoerd van 1 tot N, maar van de waarde die in het programma is ingevoerd. Het punt is dat ik geen extra regel code wilde schrijven en ervan uitging dat de gebruiker al goed thuis was in het invoeren van gegevens en het weergeven ervan op het scherm.

Hallo Habrahabr!

In dit artikel zullen we het hebben over recursieproblemen en hoe we deze kunnen oplossen.

Kort over recursie

Recursie is een vrij algemeen fenomeen dat niet alleen voorkomt op het gebied van de wetenschap, maar ook in het dagelijks leven. Bijvoorbeeld het Droste-effect, de Sierpinski-driehoek, enz. Een manier om recursie te zien is door de webcamera natuurlijk op het beeldscherm van de computer te richten, nadat u deze eerst hebt ingeschakeld. De camera zal dus het beeld van het computerscherm opnemen en op dit scherm weergeven, het zal zoiets als een gesloten lus zijn. Als resultaat zullen we iets zien dat lijkt op een tunnel.

Bij het programmeren is recursie nauw verwant aan functies; preciezer gezegd: het is dankzij functies bij het programmeren dat er zoiets bestaat als recursie of een recursieve functie. In eenvoudige bewoordingen is recursie de definitie van een deel van een functie (methode) via zichzelf, dat wil zeggen, het is een functie die zichzelf direct (in zijn lichaam) of indirect (via een andere functie) aanroept.

Er is veel gezegd over recursie. Hier zijn enkele goede bronnen:

Recursie en recursieve problemen. Toepassingsgebieden van recursie

Er wordt aangenomen dat de lezer theoretisch bekend is met recursie en weet wat het is. In dit artikel zullen we meer aandacht besteden aan recursieproblemen.

Taken

Bij het leren van recursie is het oplossen van problemen de meest effectieve manier om recursie te begrijpen.

Hoe recursieproblemen op te lossen?

Allereerst moet je begrijpen dat recursie een soort overkill is. Over het algemeen kan alles dat iteratief wordt opgelost, recursief worden opgelost, dat wil zeggen met behulp van een recursieve functie.

uit het netwerk

Elk algoritme dat in recursieve vorm is geïmplementeerd, kan in iteratieve vorm worden herschreven en omgekeerd. De vraag blijft of dit nodig is en hoe effectief dit zal zijn.

Om dit te rechtvaardigen kunnen de volgende argumenten worden aangevoerd.

Om te beginnen kunnen we ons de definities van recursie en iteratie herinneren. Recursie is een manier om gegevensverwerking te organiseren waarbij een programma zichzelf rechtstreeks of met behulp van andere programma's aanroept. Iteratie is een manier om gegevensverwerking te organiseren waarbij bepaalde acties vele malen worden herhaald zonder dat dit tot recursieve programma-oproepen leidt.

Waarna we kunnen concluderen dat ze onderling uitwisselbaar zijn, maar niet altijd met dezelfde kosten qua middelen en snelheid. Om dit te rechtvaardigen kunnen we het volgende voorbeeld geven: er is een functie waarin, om een bepaald algoritme te organiseren, er een lus is die een reeks acties uitvoert, afhankelijk van de huidige waarde van de teller (deze is mogelijk niet afhankelijk van Het). Omdat er een cyclus is, betekent dit dat het lichaam een reeks acties herhaalt: herhalingen van de cyclus. U kunt bewerkingen naar een afzonderlijke subroutine verplaatsen en de eventuele tellerwaarde doorgeven. Na voltooiing van de uitvoering van de subroutine controleren we de voorwaarden voor het uitvoeren van de lus, en als deze waar is, gaan we verder met een nieuwe aanroep van de subroutine, als deze onwaar is, voltooien we de uitvoering. Omdat We hebben de volledige inhoud van de lus in een subroutine geplaatst, wat betekent dat de voorwaarde voor het uitvoeren van de lus ook in de subroutine wordt geplaatst, en deze kan worden verkregen via de retourwaarde van de functie, parameters die worden doorgegeven door verwijzing of verwijzing naar de subroutine , evenals globale variabelen. Verder is het gemakkelijk om aan te tonen dat een oproep naar een bepaalde subroutine vanuit een lus gemakkelijk kan worden omgezet in een oproep of niet-oproep (waarbij een waarde wordt geretourneerd of simpelweg werk wordt voltooid) van een subroutine vanuit zichzelf, geleid door een aantal voorwaarden (de voorwaarden die bevonden zich voorheen in de lusconditie). Als je nu naar ons abstracte programma kijkt, lijkt het er grofweg op dat waarden worden doorgegeven aan een subroutine en deze worden gebruikt, wat de subroutine zal veranderen als deze klaar is, d.w.z. we hebben de iteratieve lus vervangen door een recursieve oproep naar een subroutine om een bepaald algoritme op te lossen.

De taak om recursie naar een iteratieve benadering te brengen is symmetrisch.

Samenvattend kunnen we de volgende gedachten uiten: voor elke aanpak is er zijn eigen klasse van taken, die wordt bepaald door de specifieke vereisten voor een specifieke taak.

Hier kunt u meer over te weten komen

Net als een opsomming (cyclus) moet recursie een stopvoorwaarde hebben - basisscenario (anders zal recursie, net als een cyclus, voor altijd werken - oneindig). Deze voorwaarde is het geval waarnaar de recursie gaat (recursiestap). Bij elke stap wordt een recursieve functie aangeroepen totdat de volgende aanroep de basisvoorwaarde activeert en de recursie stopt (of liever gezegd terugkeert naar de laatste functieaanroep). De hele oplossing komt neer op het oplossen van het basisscenario. In het geval dat een recursieve functie wordt aangeroepen om een complex probleem op te lossen (niet het basisscenario), worden een aantal recursieve aanroepen of stappen uitgevoerd om het probleem tot een eenvoudiger probleem terug te brengen. En zo verder totdat we een basisoplossing krijgen.

De recursieve functie bestaat dus uit

Stopconditie of basisscenario
Een voortzettingsvoorwaarde of een recursiestap is een manier om een probleem tot eenvoudiger problemen terug te brengen.

Laten we dit bekijken aan de hand van het voorbeeld van het vinden van de faculteit:

Public class Solution ( public static int recursion(int n) ( // exit condition // Base case // wanneer moet ik stoppen met het herhalen van de recursie? if (n == 1) ( return 1; ) // Recursion step / recursive condition return recursion( n - 1) * n; public static void main(String args) ( System.out.println(recursion(5)); // roep een recursieve functie aan ) )

Hier is de basisvoorwaarde de voorwaarde wanneer n=1. Omdat we weten dat 1!=1 en 1!=1 berekenen! wij hebben niets nodig. Om er 2 te berekenen! we kunnen 1! gebruiken, d.w.z. 2!=1!*2. Om er 3 te berekenen! we hebben 2!*3 nodig... Om n! we hebben (n-1) nodig!*n. Dit is de recursiestap. Met andere woorden: om de faculteitswaarde van een getal n te krijgen, volstaat het om de faculteitswaarde van het voorgaande getal met n te vermenigvuldigen.

Tags: