Меню

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

recursion c

Спробуйте Наш Інструмент Для Усунення Проблем

Дослідіть все про рекурсію в C ++ на класичних прикладах.

У нашому попередньому уроці ми дізналися більше про функції в C ++.

Окрім використання функцій для розбиття коду на субодиниці та спрощення та читання коду, функції корисні в різних інших додатках, включаючи вирішення проблем у реальному часі, математичні та статистичні обчислення.

Розробляючи більш складні програми на C ++, ми стикаємося з багатьма вимогами, так що нам потрібно застосувати кілька спеціальних концепцій C ++. Рекурсія - одне з таких понять.

=> Відвідайте тут, щоб отримати повний список підручників з C ++.

РЕКУРСІЯ В С ++

У цьому підручнику ми дізнаємось більше про рекурсію, де і чому вона використовується, а також деякі класичні приклади на C ++, що реалізують рекурсію.

Що ви дізнаєтесь:

Що таке рекурсія?

Рекурсія - це процес, в якому функція викликає себе. Функція, яка реалізує рекурсію або сама викликається, називається рекурсивною функцією. У рекурсії рекурсивна функція викликає себе знову і знову і продовжує працювати, доки не буде виконана умова закінчення.

На зображенні нижче показано, як працює рекурсія:

Робота рекурсії

Як ми бачимо на наведеній вище схемі, основна функція викликає функцію funct (). Функція funct (), у свою чергу, викликає себе всередині свого визначення. Ось як працює рекурсія. Цей процес виклику самої функції триватиме доти, доки ми не надамо умову завершення, яка зробить її завершеною.

найкращий безкоштовний очищувач реєстру для Windows 10 -

Зазвичай ми надаємо гілку коду під час реалізації рекурсії, так що ми забезпечуємо одну умову, яка ініціюватиме рекурсію, а іншу - для нормального виконання.

Базовий стан рекурсії

Коли здійснюється рекурсія, надається рішення базової справи або закінчувального випадку, і рішення більших проблем будуються на основі рішень менших проблем.

Давайте розглянемо класичний приклад рекурсії, позначення факторіалу.

Ми знаємо, що математичним факторіалом числа 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.

Виділення пам'яті для рекурсивного дзвінка

Ми знаємо, що коли здійснюється виклик функції, стан виклику функції зберігається в стеку, а коли виклик функції завершується, цей стан відновлюється назад, щоб програма могла продовжувати виконання.

як відкрити файл .jar

Коли здійснюється виклик рекурсивної функції, стан або пам'ять для викликаної функції виділяється поверх стану викликаючої функції, а для кожного рекурсивного виклику функції робиться інша копія локальних змінних.

Коли досягнуто базової умови, функція повертається до функції, що викликає, і пам'ять вилучається, і процес продовжується.

Переповнення стеку в рекурсії

Коли рекурсія триває необмежену кількість часу, це може призвести до переповнення стека.

Коли рекурсія може тривати так? Одна ситуація - коли ми не вказуємо базову умову. Інша ситуація - коли під час виконання програми не досягається базовий стан.

Наприклад,ми модифікуємо вищезазначену факторіальну програму та змінюємо її базовий стан.

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. Наступне число в послідовності - це сума попередніх двох чисел.

Давайте реалізуємо цю серію, використовуючи Recursion.

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

Знімок екрана для того ж наведено нижче.

Рекурсія - Паліндром

У наведеній вище програмі ми зчитуємо номер вводу зі стандартного вводу. Потім ми передаємо це число рекурсивній функції для звороту цифр числа. Якщо зворотні цифри та введений номер однакові, то число є паліндромом.

Висновок

На цьому ми закінчили рекурсію. У цьому посібнику ми вивчали рекурсивне програмування, рекурсивну функцію, її переваги / недоліки, а також різні подробиці в деталях.

найкраща ідея python для Windows 10

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

=> Завітайте сюди, щоб вивчити C ++ з нуля.

Рекомендована література

^