Меню

Рекурсия в C ++

recursion c

Опитайте Нашия Инструмент За Премахване На Проблемите

как да отворите json файл

Разгледайте всичко за рекурсията в C ++ с класически примери.

В предишния ни урок научихме повече за функциите в C ++.

Освен че използват функциите за разбиване на кода на подединици и правят кода по-опростен и четим, функциите са полезни и в различни други приложения, включително решаване на проблеми в реално време, математически и статистически изчисления.

Докато разработваме по-сложни приложения в C ++, срещаме много изисквания, така че трябва да използваме няколко специални концепции на C ++. Рекурсията е едно такова понятие.

=> Посетете тук за пълния списък с уроци за C ++.

РЕКУРСИЯ В C ++

В този урок ще научим повече за рекурсията, къде и защо се използва заедно с някои класически примери за C ++, които прилагат рекурсия.

Какво ще научите:

Какво е рекурсия?

Рекурсията е процес, при който функция се извиква. Функцията, която реализира рекурсия или се извиква, се нарича Рекурсивна функция. При рекурсия рекурсивната функция се извиква отново и отново и продължава, докато не бъде изпълнено условие за край.

Изображението по-долу показва как работи рекурсията:

Работа на рекурсия

Както виждаме в горната диаграма, основната функция извиква функция, funct (). Функцията funct () от своя страна се извиква вътре в дефиницията си. Ето как работи рекурсията. Този процес на извикване на самата функция ще продължи, докато не осигурим прекратяващо условие, което ще я накара да приключи.

Обикновено ние предоставяме разклонение на кода, докато изпълняваме рекурсия, така че предоставяме едно условие, което ще задейства рекурсия, а друго за нормално изпълнение.

Рекурсивно базово състояние

Когато се извършва рекурсия, се предоставя решението на основния случай или крайния случай и решенията на по-големите проблеми се изграждат въз основа на решенията на по-малките проблеми.

Нека разгледаме класически пример за рекурсия, нотариалната нотация.

Знаем, че математически факториалът на число n е:

н! = nxn-1x ... .x0!
като се има предвид, че 0! = 1;

Значи факториал за n = 3 ще бъде 3! = 3 × 2!

3! = 3x2x1!
3! = 3x2x2x0!
3! = 3x2x1x1 = 6

Така че програмно можем да изразим това изчисление по следния начин:

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

По този начин, както е показано по-горе, ние сме изразили горното изчисление на факториал в рекурсивно извикване на функция. Виждаме, че ако числото n е по-малко или равно на 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

В горния пример ние прилагаме рекурсия. Взимаме числото, чийто факториал се намира от стандартния вход, и след това го предаваме на факториалната функция.

Във факториалната функция ние дадохме основното условие като (n<=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); }

В горния код сме променили основното състояние на (n == 1000). Сега, ако дадем числото n = 10, можем да заключим, че основното състояние никога няма да достигне. По този начин в един момент паметта в стека ще бъде изчерпана, което ще доведе до препълване на стека.

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

Директна срещу непряка рекурсия

Досега в рекурсия видяхме как функцията се извиква. Това е директната рекурсия.

Има и друг тип рекурсия, т.е. непряка рекурсия. При това функция извиква друга функция и след това тази функция извиква повикващата функция. Ако f1 и f2 са две функции. Тогава f1 извиква f2 и f2, от своя страна, извиква f1. Това е индиректна рекурсия.

L и ние преразгледаме нашата факториална програма, за да демонстрираме директна рекурсия.

#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

как да създам фалшив имейл

В горния пример показахме непряка рекурсия. Основната функция извиква factorial_a. Factorial_a извиква factorial_b. На свой ред factorial_b извиква factorial_a. Виждаме, че изходът на програмата не е засегнат.

Опашка и неопашка рекурсия

Опазната рекурсивна функция е рекурсивна функция, при която последното повикване се изпълнява във функцията.

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

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 е палиндром

Екранна снимка за същото е дадена по-долу.

Рекурсия - палиндром

В горната програма четем входния номер от стандартния вход. След това предаваме това число на рекурсивна функция за обръщане на цифрите на число. Ако обърнатите цифри и входният номер са еднакви, тогава числото е палиндром.

Заключение

С това приключихме с рекурсията. В този урок изучихме рекурсивно програмиране, рекурсивна функция, нейните предимства / недостатъци, заедно с различни примери в детайли.

Освен тези примери, рекурсията се използва и при решаването на някои стандартни проблеми като обхождания (inorder / preorder / postorder), кули на Ханой, BFS обхождане и др.

=> Посетете тук, за да научите C ++ от нулата.

Препоръчително четене

^