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 võrdub 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 suunatakse summa funktsioonile arv, 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

Rekursioon on üsna tavaline nähtus, mis ei esine mitte ainult teadusvaldkondades, vaid ka nendes Igapäevane elu. Näiteks Droste efekt, Sierpinski kolmnurk jne. Lihtsaim 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 või rekursiivne funktsioon. Lihtsate sõnadega, rekursioon on 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). Tüüpiline rekursiivsed probleemid on ülesanded: n! leidmine, Fibonacci arvud. Oleme sellised probleemid juba lahendanud, kuid kasutades silmuseid, see tähendab iteratiivselt. Üldiselt võib öelda, et kõike iteratiivselt lahendatavat saab lahendada rekursiivselt ehk rekursiivse funktsiooni abil. Kogu lahendus taandub põhi- või, nagu seda nimetatakse ka, põhijuhtumi lahendamisele. On olemas selline asi nagu rekursioonisamm või rekursiivne kõne. Juhul, kui keeruka probleemi lahendamiseks kutsutakse välja rekursiivne funktsioon (mitte põhijuhtum), siis teatud arv rekursiivsed kõned või sammud ülesande taandamiseks lihtsamaks. Ja nii edasi, kuni jõuame põhilahendus. Töötame välja programmi, mis deklareerib rekursiivse funktsiooni, mis arvutab n!

"stdafx.h" #include << "Enter n!: "; cin >>n; cout<< 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; }

// kood Code::Blocks

// Dev-C++ kood

// factorial.cpp: määrab konsoolirakenduse sisenemispunkti. #kaasa kasutades nimeruumi std; unsigned long int faktoriaal(märgita long int // rekursiivse funktsiooni prototüüp int i = 1); // globaalse muutuja lähtestamine signeerimata rekursiivsete kõnede loendamiseks pikk int tulemus; // globaalne muutuja rekursiivse funktsiooni tagastatud tulemuse salvestamiseks int main(int argc, char* argv) ( int n; // lokaalne muutuja sisestatud numbri edastamiseks klaviatuurilt<< "Enter n!: "; cin >>n; cout<< 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 read 7, 9, 21 Andmetüüp deklareeritakse märgita long int , kuna faktoriaali väärtus kasvab väga kiiresti, näiteks juba 10! = 3 628 800 Kui andmetüübi suurus ei ole piisav, saame tulemuseks täiesti vale väärtuse. Kood deklareerib rohkem operaatoreid, kui on vaja n! leidmiseks. Seda tehakse selleks, et programm näitaks pärast käivitamist, mis toimub rekursiivsete kõnede igal etapil. Pange tähele esiletõstetud koodiridu, read 23, 24, 28 on n! rekursiivne lahendus. 23., 24. read on rekursiivse funktsiooni põhilahendus, st niipea, kui muutuja väärtus f võrdub 1 või 0 (kuna me teame, et 1! = 1 ja 0! = 1), rekursiivsed kõned peatuvad ja väärtusi hakatakse tagastama iga rekursiivse kõne kohta. Kui esimese rekursiivse kõne väärtus tagastab, tagastab programm arvutatud faktoriaali väärtuse. IN rida 28 funktsioon faktoriaal() kutsub ennast, kuid selle argument on ühe võrra väiksem. Argumenti vähendatakse iga kord, et jõuda konkreetse lahenduseni. Programmi tulemus (vt joonis 1).

Sisestage n!: 5 1. sammu tulemus = 0 2. sammu tulemus = 0 3. sammu tulemus = 0 4. sammu tulemus = 0 5! = 120

Joonis 1 – Rekursioon C++ keeles

Programmi tulemuse põhjal on iga samm selgelt nähtav ja tulemus igal sammul on null, välja arvatud viimane rekursiivne kõne. Oli vaja arvutada viis faktoriaali. Programm tegi neli rekursiivset kõnet ja viiendal kõnel leiti baasjuhtum. Ja kui programmil oli baasjuhtumile lahendus, lahendas see eelmised sammud ja väljastas üldtulemuse. Joonisel 1 on näha vaid neli sammu, sest viiendas etapis leiti osalahend, mis lõppkokkuvõttes tagastas lõpplahenduse ehk 120. Joonisel 2 on rekursiivne arvutusskeem 5!. Diagramm näitab selgelt, et esimene tulemus tagastatakse konkreetse lahenduseni jõudmisel, kuid mitte kohe pärast iga rekursiivset kõnet.

Joonis 2 – Rekursioon C++ keeles

Nii et leida 5! vaja teada 4! ja korrutage see 5-ga; 4! = 4 * 3! ja nii edasi. Vastavalt joonisel 2 näidatud skeemile taandatakse arvutus erijuhtumi leidmiseni, see tähendab 1!, misjärel tagastatakse väärtused kordamööda igale rekursiivsele kõnele. Viimane rekursiivne kõne tagastab väärtuse 5!.

Töötame faktoriaali leidmise programmi ümber, et saada faktoriaalide tabel. Selleks deklareerime for-tsükli, milles kutsume välja rekursiivse funktsiooni.

kasutades nimeruumi std; unsigned long int faktoriaal(märgita long int // rekursiivse funktsiooni prototüüp int i = 1); // globaalse muutuja lähtestamine signeerimata rekursiivsete kõnede loendamiseks pikk int tulemus; // globaalne muutuja rekursiivse funktsiooni tagastatud tulemuse salvestamiseks int main(int argc, char* argv) ( int n; // lokaalne muutuja sisestatud numbri edastamiseks klaviatuurilt<< "Enter n!: "; cin >>n; jaoks (int k = 1; k<= 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; jaoks (int k = 1; k<= 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 < << "Enter number from the Fibonacci series: "; cin >> <= entered_number; counter++) cout << setw(2) <

// kood Code::Blocks

// Dev-C++ kood

// fibonacci.cpp: määrab konsoolirakenduse sisenemispunkti. #kaasa // teek ekraanil kuvatava teabe vormindamiseks #include kasutades nimeruumi std; märgita pikk fibonacci(märgita pikk // rekursiivse funktsiooni prototüüp Fibonacci seeriast arvude otsimiseks int main(int argc, char* argv) ( märgita pikk sisestatud_number; cout);<< "Enter number from the Fibonacci series: "; cin >> sisestatud_number; for (int loendur = 1; loendur<= entered_number; counter++) cout << setw(2) <#kaasa kasutades nimeruumi std; tühi torn(int, int, int, int); // rekursiivse funktsiooni prototüübi deklaratsioon int count = 1; // globaalne muutuja sammude arvu loendamiseks int _tmain(int argc, _TCHAR* argv) ( cout<< "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >>number; cout<< "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >> põhi_varras; cout<< "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> lõplik_varras; int abi_varras; // abivarda numbri määramise plokk, alg- ja lõppvarda numbrite analüüsimine if (põhivarras != 2 && lõplik_varras != 2) abipulk = 2; else if (põhivarras != 1 && lõplik_varras != 1) abi_varras = 1; else if (põhivarras != 3 && lõplik_varras != 3) abi_varras = 3; tower(// rekursiivse funktsiooni käivitamine Towers of Hanoi probleemi lahendamiseks number, // muutuja, mis salvestab teisaldatavate ketaste arvu basic_rod, // muutuja, mis salvestab varda numbri, millele kettad algselt paigutatakse asukohaga help_rod , // ridva numbrit salvestav muutuja, mida kasutatakse abistava final_rodina); // muutuja, mis salvestab varda numbri, kuhu kettad tuleb teisaldada system("pause"); tagasi 0; ) void tower(int count_disk, int baza, int abi_baza, int uus_baza) ( if (count_disk == 1) // tingimus rekursiivsete kõnede lõpetamiseks ( cout<< 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); // перемещаем все диски со вспомогательного стержня на финальный } }

// kood Code::Blocks

// Dev-C++ kood

// hanoi_tower.cpp: määrab konsoolirakenduse sisenemispunkti. // Programm, mis lahendab rekursiivselt Hanoi torni probleemi #include #kaasa kasutades nimeruumi std; tühi torn(int, int, int, int); // rekursiivse funktsiooni prototüübi deklaratsioon int count = 1; // globaalne muutuja sammude arvu loendamiseks int main() ( cout<< "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >>number; cout<< "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >> põhi_varras; cout<< "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> lõplik_varras; int abi_varras; // abivarda numbri määramise plokk, alg- ja lõppvarda numbrite analüüsimine if (põhivarras != 2 && lõplik_varras != 2) abipulk = 2; else if (põhivarras != 1 && lõplik_varras != 1) abi_varras = 1; else if (põhivarras != 3 && lõplik_varras != 3) abi_varras = 3; tower(// rekursiivse funktsiooni käivitamine Towers of Hanoi probleemi numbri lahendamiseks, // muutuja, mis salvestab teisaldatavate ketaste arvu basic_rod, // muutuja, mis salvestab varda numbri, millele kettad algselt paigutatakse asukohaga help_rod , // ridva numbrit salvestav muutuja, mida kasutatakse abistava final_rodina); // muutuja, mis salvestab varda numbri, kuhu kettad tuleb liigutada return 0; ) void tower(int count_disk, int baza, int abi_baza, int uus_baza) ( if (count_disk == 1) // tingimus rekursiivsete kõnede lõpetamiseks ( cout<< 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); // перемещаем все диски со вспомогательного стержня на финальный } }

Joonisel 5 on kujutatud Tower of Hanoi rekursiivse programmi näide. Esiteks sisestasime ketaste arvu, mis võrdub kolmega, seejärel tutvustasime alusvarda (esimene) ja määrasime lõpliku varda (kolmanda). Automaatselt sai teine ​​ritv abiks. Programm andis tulemuse, mis kattub täielikult selle probleemi animeeritud lahendusega.

Ketaste arvu sisestamine: 3 Sisestage põhivarda arv: 1 Sisestage lõpliku varda arv: 3 1) 1 -> 3 2) 1 -> 2 3) 3 -> 2 4) 1 -> 3 5) 2 -> 1 6) 2 -> 3 7) 1 -> 3

Joonis 5 – Rekursioon C++ keeles

Jooniselt on näha, et kõigepealt liigub ketas ühelt vardalt kolmele, siis ühelt vardalt teisele, kolmelt vardalt vardalekaks jne. See tähendab, et programm kuvab lihtsalt ketta liigutuste jada ja minimaalse sammude arvu, mille jooksul kõik kettad liigutatakse.

Kõiki neid probleeme saab lahendada iteratiivselt. Tekib küsimus: "Kumba on parem lahendada, iteratiivselt või rekursiivselt?" Vastan: “Rekursiooni miinuseks on see, et see kulutab oluliselt rohkem arvutiressursse kui iteratsioon. Selle tulemuseks on suur koormus nii RAM-ile kui ka protsessorile. Kui on ilmne, et konkreetset probleemi saab lahendada iteratiivselt, siis tuleks seda kasutada teistmoodi, kasutades rekursiooni! Olenevalt lahendatavast probleemist muutub programmide kirjutamise keerukus ühe või teise lahendusmeetodi kasutamisel. Kuid sagedamini on koodi loetavuse seisukohalt rekursiivsel meetodil lahendatud probleem palju selgem ja lühem.

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! me 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 märksõnu