Разлика между рекурсия и итерация

Ключова разлика - рекурсия срещу итерация
 

Рекурсия и итерация могат да се използват за решаване на проблеми с програмирането. Подходът за решаване на проблема с помощта на рекурсия или итерация зависи от начина за решаване на проблема. Най- ключова разлика между рекурсия и итерация е това рекурсията е механизъм за извикване на функция в рамките на същата функция, докато итерацията е да се изпълнява набор от инструкции многократно, докато даденото условие е вярно. Рекурсия и итерация са основни техники за разработване на алгоритми и изграждане на софтуерни приложения.

СЪДЪРЖАНИЕ

1. Преглед и ключова разлика
2. Какво е рекурсия
3. Какво е итерация
4. Прилики между рекурсия и итерация
5. Паралелно сравнение - рекурсия срещу итерация в таблична форма
6. Резюме

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

Когато функция се обажда в рамките на функцията, тя е известна като Рекурсия. Има два вида рекурсия. Те са крайна рекурсия и безкрайна рекурсия. Крайна рекурсия има прекратяващо състояние. Безкрайна рекурсия няма условие за прекратяване.

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

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

н! = 1, ако п = 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). factorial (0) ще се върне 1. В горната програма, n == 0 условието в „if block“ е основното условие. Според По същия начин факторната функция се извиква отново и отново.

Рекурсивните функции са свързани със стека. В C основната програма може да има много функции. И така, main () е извикващата функция, а функцията, която се извиква от основната програма, е наречената функция. Когато функцията се извиква, контролът се дава на наречената функция. След приключване на изпълнението на функцията, контролът се връща към основното. Тогава основната програма продължава. Така че, той създава запис на активиране или стек кадър, за да продължи изпълнението.

Фигура 01: Рекурсия

В горната програма, когато извиква facialorial (3) от main, тя създава запис за активиране в стека на повикванията. След това, факторната (2) стекова рамка се създава отгоре на стека и така нататък. Записът за активиране съхранява информация за локални променливи и т.н. Всеки път, когато се извика функцията, се създава нов набор от локални променливи в горната част на стека. Тези стекове могат да забавят скоростта. По същия начин при рекурсия функция се извиква. Времевата сложност за рекурсивна функция се намира от броя пъти, функцията се нарича. Времевата сложност за едно функционално обаждане е O (1). За n брой рекурсивни повиквания, времевата сложност е O (n).

Какво е итерация?

Итерацията е блок от инструкции, който се повтаря отново и отново, докато даденото условие е вярно. Итерацията може да се постигне, като се използва „for loop“, „do-while loop“ или „while loop“. Синтаксисът „за цикъл“ е следният.

за (инициализация; условие; промяна)

// изявления;

Фигура 02: „за схема на потока на веригата“

Първата стъпка се изпълнява. Тази стъпка е за деклариране и инициализиране на променливи за управление на контура. Ако условието е вярно, изявленията вътре в къдравите скоби се изпълняват. Тези изявления се изпълняват, докато условието е вярно. Ако условието е невярно, контролът преминава към следващото изявление след „за цикъл“. След изпълнение на операторите в цикъла, контролът преминава към промяна на секцията. Тя е да се актуализира променливата за управление на цикъла. Тогава състоянието се проверява отново. Ако условието е вярно, ще се изпълнят отчетите вътре в къдравите скоби. По този начин „за цикъла“ се итератира.

В „докато цикъл“, отчетите вътре в цикъла се изпълняват, докато условието е вярно.

докато (условие)

//изявления

В цикъл „до-докато“, състоянието се проверява в края на контура. Така че цикълът се изпълнява поне веднъж.

направи

//изявления

докато (условие)

Програма за намиране на фактор на 3 (3!) С помощта на итерация („за цикъл“) е следната.

int main ()

intn = 3, факториален = 1;

Инти;

за (i = 1; i<=n ; i++)

факториален = факторен * i;

printf („Факторът е% d \ n“, факторен);

връщане 0;

Какви са приликите между рекурсия и итерация?

• И двете са техники за решаване на проблем.
• Задачата може да бъде решена или в рекурсия, или в итерация.

Каква е разликата между рекурсия и итерация?

Рекурсия срещу итерация
Рекурсията е метод за извикване на функция в рамките на една и съща функция.	Итерацията е блок от инструкции, който се повтаря, докато даденото условие е вярно.
Космическа сложност
Космическата сложност на рекурсивните програми е по-висока от итерациите.	Космическата сложност е по-ниска в итерациите.
скорост
Изпълнението на рекурсията е бавно.	Обикновено итерацията е по-бърза от рекурсията.
състояние
Ако няма условие за прекратяване, може да има безкрайна рекурсия.	Ако състоянието никога не стане невярно, това ще бъде безкрайна итерация.
купчина
В рекурсия стекът се използва за съхраняване на локални променливи, когато се извиква функцията.	В итерация стекът не се използва.
Четене на код
Рекурсивната програма е по-четена.	Итеративната програма е по-трудна за четене от рекурсивната програма.

Обобщение - рекурсия срещу итерация

Тази статия обсъжда разликата между рекурсия и итерация. И двете могат да се използват за решаване на проблеми с програмирането. Разликата между рекурсия и итерация е, че рекурсията е механизъм за извикване на функция в рамките на същата функция и итерация, за да изпълнява набор от инструкции многократно, докато даденото условие е вярно. Ако даден проблем може да бъде решен в рекурсивна форма, той може да бъде решен и с помощта на итерации.

Изтеглете PDF версията на рекурсия срещу итерация

Можете да изтеглите PDF версия на тази статия и да я използвате за офлайн цели, съгласно цитираната бележка. Моля, изтеглете PDF версия тук Разлика между рекурсия и итерация

справка:

1. Точка, уроци. „Основи на рекурсията на структури от данни и алгоритми.”, Точка за уроци, 15 август 2017 г. Достъпно тук 
2.nareshtechnologies. „Рекурсия в C функции | Урок за езика на C “YouTube, YouTube, 12 септември 2016 г. Достъпно тук  
3.yusuf шейкъл. „Алгоритъм за рекурсия | Factorial - ръководство стъпка по стъпка “YouTube, YouTube, 14 октомври 2013. Достъпно тук  

С любезност на изображенията:

1.'CPT-Recursion-Factorial-Code'By Pluke - Собствена работа, (Public Domain) чрез Commons Wikimedia 
2. 'За диаграма за цикъл'. Не е предоставен машинно четим автор - Предполага се собствена работа. (CC BY-SA 2.5) през Wikimedia на Commons