Ключова разлика - рекурсия срещу итерация
Рекурсията и итерацията могат да се използват за решаване на проблеми с програмирането. Подходът за решаване на проблема с помощта на рекурсия или итерация зависи от начина за решаване на проблема. Ключовата разлика между рекурсията и итерацията е, че рекурсията е механизъм за извикване на функция в рамките на същата функция, докато итерацията е да изпълнява набор от инструкции многократно, докато даденото условие е вярно. Рекурсията и итерацията са основни техники за разработване на алгоритми и изграждане на софтуерни приложения.
СЪДЪРЖАНИЕ
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 () е извикващата функция, а функцията, която се извиква от основната програма, е извиканата функция. Когато функцията е извикана, контролът се дава на извиканата функция. След като изпълнението на функцията приключи, контролата се връща към main. Тогава основната програма продължава. Така че, той създава запис за активиране или рамка на стека, за да продължи изпълнението.
Фигура 01: Рекурсия
В горната програма, когато извиква факториал (3) от main, тя създава запис за активиране в стека на повикванията. След това, факториална (2) рамка на стека се създава върху стека и така нататък. Записът за активиране съхранява информация за локални променливи и т.н. Всеки път, когато се извика функцията, в горната част на стека се създава нов набор от локални променливи. Тези рамки на стека могат да забавят ускоряването. По същия начин при рекурсия, функция се извиква. Сложността на времето за рекурсивна функция се намира по броя на извикванията на функцията. Сложността във времето за едно извикване на функция е O (1). За n брой рекурсивни повиквания сложността във времето е O (n).
Какво е итерация?
Итерацията е блок от инструкции, който се повтаря отново и отново, докато даденото условие е истина. Итерацията може да бъде постигната с помощта на „for loop“, „do-while loop“или „while loop“. Синтаксисът „за цикъл“е както следва.
за (инициализация; условие; промяна) {
// изявления;
}
Фигура 02: „за диаграма на контура“
Първо се изпълнява стъпка за инициализация. Тази стъпка е да декларира и инициализира контролни променливи на цикъла. Ако условието е вярно, изпълненията в къдравите скоби се изпълняват. Тези изявления се изпълняват, докато условието е вярно. Ако условието е невярно, контролата преминава към следващия оператор след цикъла „for“. След изпълнението на операторите вътре в цикъла контролата преминава към раздел за модифициране. Той трябва да актуализира контролната променлива на цикъла. След това състоянието се проверява отново. Ако условието е вярно, операторите във фигурните скоби ще се изпълнят. По този начин цикълът „for“се повтаря.
В „while цикъл“операторите вътре в цикъла се изпълняват, докато условието не е вярно.
докато (състояние) {
//изявления
}
В цикъл „do-while“състоянието се проверява в края на цикъла. И така, цикълът се изпълнява поне веднъж.
направи {
//изявления
} докато (състояние)
Програмата за намиране на факториал на 3 (3!) С помощта на итерация („за цикъл“) е както следва.
int main () {
intn = 3, факториал = 1;
inti;
за (i = 1; i <= n; i ++) {
факториал = факториал * i;
}
printf („Факториалът е% d / n“, факториал);
връщане 0;
}
Какви са приликите между рекурсия и итерация?
- И двете са техники за решаване на проблем.
- Задачата може да бъде решена или в рекурсия, или в итерация.
Каква е разликата между рекурсията и итерацията?
Различна статия Средна преди таблица
Рекурсия срещу итерация |
|
| Рекурсията е метод за извикване на функция в рамките на същата функция. | Итерацията е блок от инструкции, който се повтаря, докато даденото условие не е вярно. |
| Сложност на пространството | |
| Сложността на пространството на рекурсивните програми е по-висока от итерациите. | Сложността на пространството е по-ниска при повторения. |
| Скорост | |
| Изпълнението на рекурсията е бавно. | Обикновено итерацията е по-бърза от рекурсията. |
| Състояние | |
| Ако няма условие за прекратяване, може да има безкрайна рекурсия. | Ако условието никога не стане фалшиво, това ще бъде безкрайна итерация. |
| Стек | |
| При рекурсия стекът се използва за съхраняване на локални променливи при извикване на функцията. | При итерация стекът не се използва. |
| Кодово четливост | |
| Рекурсивната програма е по-четлива. | Итеративната програма е по-трудна за четене от рекурсивната програма. |
Резюме - Рекурсия срещу итерация
Тази статия обсъжда разликата между рекурсията и итерацията. И двете могат да се използват за решаване на проблеми с програмирането. Разликата между рекурсията и итерацията е, че рекурсията е механизъм за извикване на функция в рамките на същата функция и итерацията, за да изпълнява набор от инструкции многократно, докато даденото условие е вярно. Ако проблемът може да бъде решен в рекурсивна форма, той също може да бъде решен с помощта на итерации.
Изтеглете PDF версията на Recursion vs Iteration
Можете да изтеглите PDF версия на тази статия и да я използвате за офлайн цели според бележката към цитата. Моля, изтеглете PDF версия тук Разлика между рекурсия и итерация
