Мени

Рекурзија у Ц ++

recursion c

Испробајте Наш Инструмент За Елиминисање Проблема

Истражите све о рекурзији на језику Ц ++ помоћу класичних примера.

У нашем претходном водичу сазнали смо више о функцијама на Ц ++.

Осим што користе функције за разградњу кода на подјединице и чине га једноставнијим и читљивијим, функције су корисне и у разним другим апликацијама, укључујући решавање проблема у реалном времену, математичко и статистичко рачунање.

Како развијамо сложеније апликације на језику Ц ++, сусрећемо се са многим захтевима, тако да морамо користити неколико посебних концепата језика Ц ++. Рекурзија је један такав концепт.

=> Посетите овде за комплетну листу водича за Ц ++.

веб страница за бесплатно гледање аниме

РЕЦУРЗИЈА У Ц ++

У овом упутству ћемо научити више о рекурзији, где и зашто се користи заједно са неким класичним примерима Ц ++ који примењују рекурзију.

Шта ћете научити:

Шта је рекурзија?

Рекурзија је процес у којем се функција позива. Функција која имплементира рекурзију или себе позива назива се рекурзивна функција. У рекурзији, рекурзивна функција се позива изнова и изнова и наставља све док се не испуни крајњи услов.

Слика испод приказује како функционише рекурзија:

Деловање рекурзије

Као што видимо на горњем дијаграму, главна функција позива функцију, фунцт (). Функција фунцт () заузврат себе назива унутар своје дефиниције. Тако функционише рекурзија. Овај процес позива саме функције ће се наставити све док не пружимо крајњи услов због којег ће се завршити.

Обично пружамо грану кода док имплементирамо рекурзију, тако да пружамо један услов који ће покренути рекурзију, а други за нормално извршавање.

Основно стање рекурзије

Када се изврши рекурзија, пружа се решење основног случаја или завршног случаја и решења већих проблема граде се на основу решења мањих проблема.

Размотримо класични пример рекурзије, факторијалну нотацију.

Знамо да је математички фактор броја н:

н! = нкн-1к… .к0!
с обзиром да је 0! = 1;

Дакле, факторијел за н = 3 биће 3! = 3 × 2!

3! = 3к2к1!
3! = 3к2к2к0!
3! = 3к2к1к1 = 6

Дакле, програмски ову израчун можемо изразити на следећи начин:

int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); }

Стога смо, као што је приказано горе, изразили горњи прорачун фактора у рекурзивни позив функције. Видимо да ако је број н мањи или једнак 1, вратимо 1 уместо рекурзивног позива. Ово се назива основни услов / случај за факторијел који омогућава заустављање рекурзије.

Дакле, основни услов у основи одлучује колико пута рекурзивна функција треба да се зове. То значи да можемо врло добро израчунати факторијел већег броја тако што ћемо га изразити мањим бројевима док се не постигне основна класа.

Доље дат је савршен пример за израчунавање факторијела броја:

#include #include using namespace std; int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); } int main() { int num,result; cout<>num; result = factorial(num); cout<

Излаз:

Унесите број чији факторијел треба израчунати: 10
10! = 3628800

У горњем примеру, примењујемо рекурзију. Број чији факторијел налазимо узимамо из стандардног улаза, а затим га прослеђујемо факторијелној функцији.

У факториској функцији дали смо основни услов као (н<=1). So, when the base case is reached, the function returns. Using this base case, we can calculate factorial of any number greater than 1.

Додељивање меморије за рекурзивни позив

Знамо да се, када се изврши позив функције, стање функције која се позива похрањује у стек и када се позив функције заврши, то стање се враћа натраг, тако да програм може да настави извршење.

Када се изврши рекурзивни позив функције, стање или меморија за позвану функцију се додељује поврх стања позивајуће функције и за сваки рекурзивни позив функције врши се другачија копија локалних променљивих.

Када се постигне основни услов, функција се враћа позивајућој функцији и меморија се раздваја и процес се наставља.

Преливање стека у рекурзији

Када се рекурзија настави неограничено дуго, то може довести до преливања стека.

Када се рекурзија може наставити овако? Једна је ситуација када не одредимо основни услов. Друга ситуација је када основни услов није постигнут током извршавања програма.

На пример,модификујемо горњи факторски програм и мењамо његово основно стање.

int factorial(int n){ if(n ==1000) return 1; else return n*factorial(n-1); }

У горњем коду смо променили основни услов у (н == 1000). Сада, ако дамо број н = 10, можемо закључити да основни услов никада неће достићи. На овај начин ће се у једном тренутку меморија на стеку исцрпити, што ће резултирати преливањем стека.

Стога, док дизајнирамо рекурзивне програме, морамо бити опрезни у погледу основног стања које пружамо.

Директна вс индиректна рекурзија

До сада смо у рекурзији видели како се функција позива. Ово је директна рекурзија.

Постоји још један тип рекурзије, тј. Индиректна рекурзија. У овом случају функција позива другу функцију, а затим ова функција позива функцију позивања. Ако су ф1 и ф2 две функције. Тада ф1 позива ф2 и ф2, заузврат, позива ф1. Ово је индиректна рекурзија.

Л и ревидирамо наш факторски програм како бисмо демонстрирали директну рекурзију.

#include #include using namespace std; int factorial_b(int); int factorial_a(int n){ if(n <=1) return 1; else return n*factorial_b(n-1); } int factorial_b(int n){ if(n <=1) return 1; else return n*factorial_a(n-1); } int main() { int num, result; cout<>num; result = factorial_a(num); cout<

Излаз:

Унесите број чији факторијел треба израчунати: 5
5! = 120

где бесплатно гледати аниме

У горњем примеру показали смо индиректну рекурзију. Главна функција позива фацториал_а. Фацториал_а позива фацториал_б. Заузврат фацториал_б назива фацториал_а. Видимо да то не утиче на излаз програма.

Таилед анд Нон-Таилед Рецурсион

Реактивна рекурзивна функција је рекурзивна функција у којој се у функцији извршава последњи позив.

На пример, размотрите следећу функцију.

void display(int n){ if(n<=1) return; cout<<” ”<

У горњем примеру, екран је такуална рекурзивна функција таква да је последњи позив функције.

Репне функције сматрају се бољим од нерепаних рекурзивних функција, јер их преводилац може оптимизирати. Разлог је тај што је, будући да је репни рекурзивни позив последњи израз у функцији, не постоји код који треба извршити након овог позива.

Као резултат, чување тренутног оквира стека за функцију није потребно.

За / против рекурзије због итеративног програмирања

Рекурзивни програми пружају компактан и чист код. Рекурзивни програм је једноставан начин писања програма. Постоје неки инхерентни проблеми попут факторијела, Фибоначијевог низа, ханојских кула, прелаза дрвећа итд. Којима је потребна рекурзија за решавање.

Другим речима, ефикасно се решавају рекурзијом. Такође се могу решити итеративним програмирањем помоћу стекова или других структура података, али постоје шансе да постану сложенији за примену.

Моћи рекурзивног и итеративног програмирања за решавање проблема су исте. Међутим, рекурзивни програми заузимају више меморијског простора јер сви позиви функција морају бити ускладиштени у стеку док се не подудара основни случај.

Рекурзивне функције такође имају временске трошкове због превише позива функција и повратних вредности.

Примери рекурзије

Даље ћемо применити неке примере рекурзивног програмирања.

Фибонацци Сериес

Фибоначијева серија је низ који је дат као

0 1 1 2 3 5 8 13 ……

Као што је горе приказано, прва два броја Фибоначијеве серије су 0 и 1. Следећи број у низу је збир претходна два броја.

Применимо ову серију помоћу Рекурзије.

#include using namespace std; void fibSeries(int n){ static int n1=0, n2=1, n3; if(n>0){ n3 = n1 + n2; n1 = n2; n2 = n3; cout<num; cout<<'Fibonacci Series for '<

Излаз:

Унесите број елемената за Фибоначијеву серију: 10
Фибоначијева серија за 10 бројева: 0 1 1 2 3 5 8 13 21 34

У овом примеру смо користили рекурзивни позив за генерисање Фибоначијеве секвенце. Видимо да се прва два броја која су константна директно штампају и за следеће бројеве у низу користимо рекурзивну функцију.

Палиндроме

Палиндромски број је број који је када се чита у обрнутом смеру једнак оном који се чита у левом на десно смер.

На пример, број 121 током читања слева надесно и здесна налево чита исто, тј. 121. Отуда је 121 палиндром.

Број 291, када читате здесна налево, тј. Обрнутим редоследом, чита се као 192. Отуда 291 није палиндром.

#include using namespace std; int reverse_digits(int n, int temp) { if (n == 0) return temp; temp = (temp * 10) + (n % 10); return reverse_digits(n / 10, temp); } int main() { int num; cout<>num; int result = reverse_digits(num, 0); if (result == num) cout << 'Number '<

Излаз:

Унесите број за проверу палиндрома: 6556
Број 6556 је палиндром

Снимак екрана за исти дат је у наставку.

Рекурзија - Палиндром

У горњем програму читамо улазни број са стандардног улаза. Затим прослеђујемо овај број рекурзивној функцији да преокрене цифре броја. Ако су обрнуте цифре и улазни број исти, онда је број палиндром.

Закључак

Са овим смо завршили са рекурзијом. У овом упутству проучавали смо рекурзивно програмирање, рекурзивну функцију, њене предности / недостатке, заједно са разним детаљима.

Осим ових примера, рекурзија се користи и у решавању неких стандардних проблема као што су обилазнице (инордер / преордер / постордер), торњеви Ханоја, БФС прелазак итд.

=> Посетите овде да бисте научили Ц ++ из огреботина.

Препоручено читање

^