Різниця між рекурсією та ітерацією

Ключова різниця - рекурсія проти ітерації
 

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

ЗМІСТ

1. Огляд та ключові відмінності
2. Що таке рекурсія
3. Що таке ітерація
4. Подібність між рекурсією та ітерацією
5. Поплечне порівняння - рекурсія проти ітерації в табличній формі
6. Підсумок

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

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

Рекурсію можна пояснити за допомогою програми для обчислення факторіалів.

н! = n * (n-1) !, якщо n> 0

н! = 1, якщо n = 0;

Подайте наступний код для обчислення факторіалу 3 (3! = 3 * 2 * 1).

intmain ()

значення int = факторіал (3);

printf (значення "Фактор є% d \ n", значення);

повернути 0;

intfactorial (intn)

якщо (n == 0)

повернути 1;

ще

повернути n * факторіал (n-1);

При виклику факторіалу (3) ця функція буде викликати факторіал (2). При виклику факторіалу (2) ця функція буде викликати факторіал (1). Тоді факториал (1) викличе факторіал (0). факториал (0) повернеться 1. У вищенаведеній програмі n == 0 умовою у "if block" є базова умова. Згідно з аналогічним чином, факторіальна функція викликається знову і знову.

Рекурсивні функції пов'язані зі стеком. В C основна програма може мати багато функцій. Отже, main () - це функція виклику, а функція, яка викликається основною програмою, називається функцією. Коли функція викликається, управління передається викликаної функції. Після завершення виконання функції елемент повертається до основного. Потім основна програма продовжується. Отже, він створює запис активації або стек-кадр для продовження виконання.

Малюнок 01: Рекурсія

У вищевказаній програмі при виклику факторіалу (3) з main він створює запис активації в стеку викликів. Потім на вершині стека створюється рамка стека факторіального (2) тощо. Запис активації зберігає інформацію про локальні змінні тощо. Щоразу, коли функція викликається, новий набір локальних змінних створюється у верхній частині стека. Ці рамки стека можуть уповільнити швидкість. Так само в рекурсії функція викликає себе. Складність часу для рекурсивної функції знаходимо за кількістю разів, функція називається. Часова складність для одного виклику функції дорівнює O (1). Для n кількості рекурсивних викликів часова складність становить O (n).

Що таке ітерація?

Ітерація - це блок інструкцій, який повторюється знову і знову, поки задана умова не відповідає дійсності. Ітерація може бути досягнута за допомогою "для циклу", "циклу до виконання" або "під час циклу". Синтаксис "for loop" такий.

for (ініціалізація; умова; змінити)

// заяви;

Малюнок 02: "для схеми потоку циклу"

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

У "while циклі", оператори всередині циклу виконуються, поки умова не відповідає дійсності.

while (умова)

// заяви

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

робити

// заяви

пока (умова)

Програма пошуку фактора 3 (3!) За допомогою ітерації ("для циклу") полягає в наступному.

int main ()

intn = 3, факторіал = 1;

inti;

для (i = 1; i<=n ; i++)

факторіал = факторіал * я;

printf ("Факторний% d \ n", факториальний);

повернути 0;

Які подібності між рекурсією та ітерацією?

• Обидва - це методи вирішення проблеми.
• Завдання можна вирішити або в рекурсії, або в ітерації.

Яка різниця між рекурсією та ітерацією?

Рекурсія проти ітерації
Рекурсія - це метод виклику функції в межах однієї функції.	Ітерація - це блок інструкцій, який повторюється, поки задана умова не відповідає дійсності.
Космічна складність
Складність простору рекурсивних програм вище, ніж ітерацій.	Космічна складність в ітераціях менша.
Швидкість
Виконання рекурсії відбувається повільно.	Зазвичай ітерація швидша, ніж рекурсія.
Умова
Якщо немає умови припинення, може відбутися нескінченна рекурсія.	Якщо стан ніколи не стане помилковим, це буде нескінченна ітерація.
Стек
У рекурсії стек використовується для зберігання локальних змінних при виклику функції.	В ітерації стек не використовується.
Читання коду
Рекурсивна програма легше читається.	Ітераційну програму важче читати, ніж рекурсивну програму.

Підсумок - рекурсія проти ітерації

У цій статті розглянуто різницю між рекурсією та ітерацією. І те й інше можна використовувати для вирішення проблем програмування. Різниця між рекурсією та ітерацією полягає в тому, що рекурсія - це механізм виклику функції в межах однієї функції та ітерації її для виконання набору вказівок повторно, поки задана умова не відповідає дійсності. Якщо проблему можна вирішити в рекурсивному вигляді, її можна вирішити також за допомогою ітерацій.

Завантажте PDF-версію Рекурсія проти Ітерації

Ви можете завантажити PDF-версію цієї статті та використовувати її в офлайн-цілях відповідно до примітки. Завантажте тут версію PDF тут Різниця між рекурсією та ітерацією

Довідка:

1.Будинка, Підручники. «Структури даних та алгоритми основи рекурсії»., Навчальний посібник, 15 серпня 2017 р. Доступний тут 
2.натехнології. “Рекурсія у функціях C | Підручник з мов C »YouTube, YouTube, 12 вересня 2016. Доступний тут  
3.юйсуф шейкель. «Алгоритм рекурсії | Факторний - покроковий посібник ”YouTube, YouTube, 14 жовтня 2013 р. Доступний тут  

Надано зображення:

1.'CPT-Recursion-Factorial-Code'By Pluke - Власна робота, (Public Domain) через Commons Wikimedia 
2.'Для діаграми циклу '. Немає автора, який читається машиною, - передбачається власна робота. (CC BY-SA 2.5) через Wikimedia Commons