Ключова разлика – рекурсия срещу итерация
Рекурсията и итерацията могат да се използват за решаване на проблеми с програмирането. Подходът за решаване на проблема чрез рекурсия или итерация зависи от начина за решаване на проблема. Ключовата разлика между рекурсия и итерация е, че рекурсията е механизъм за извикване на функция в рамките на същата функция, докато итерацията е да изпълнява набор от инструкции многократно, докато даденото условие е вярно. Рекурсията и итерацията са основни техники за разработване на алгоритми и изграждане на софтуерни приложения.
Какво е рекурсия?
Когато функция извиква сама себе си в рамките на функцията, това е известно като рекурсия. Има два вида рекурсия. Те са крайна рекурсия и безкрайна рекурсия. Крайната рекурсия има терминиращо условие. Безкрайната рекурсия няма крайно условие.
Рекурсията може да бъде обяснена с помощта на програмата за изчисляване на факториели.
n!=n(n-1)!, ако n>0
n!=1, ако n=0;
Вижте кода по-долу, за да изчислите факториел от 3(3!=321).
intmain () {
int стойност=факториал (3);
printf(“Факториал е %d\n”, стойност);
върни 0;
}
intfactorial (intn) {
if(n==0) {
върни 1;
}
друго {
върни n факториел(n-1);
}
}
Когато извиквате факториел (3), тази функция ще извика факториел (2). При извикване на факториел (2), тази функция ще извика факториел (1). Тогава факториел (1) ще извика факториел (0). factorial (0) ще върне 1. В горната програма условието n==0 в блока „if“е основното условие. Според Likewise факторната функция се извиква отново и отново.
Рекурсивните функции са свързани със стека. В C основната програма може да има много функции. И така, main () е извикващата функция, а функцията, която се извиква от основната програма, е извикваната функция. Когато функцията бъде извикана, управлението се дава на извиканата функция. След приключване на изпълнението на функцията, контролът се връща към основния. След това продължава основната програма. И така, той създава запис за активиране или стекова рамка, за да продължи изпълнението.
Фигура 01: Рекурсия
В горната програма, когато се извиква факториел (3) от main, тя създава запис за активиране в стека на повикванията. След това факторна (2) стекова рамка се създава върху стека и така нататък. Записът за активиране пази информация за локални променливи и т.н. При всяко извикване на функцията се създава нов набор от локални променливи в горната част на стека. Тези стекови рамки могат да забавят скоростта. По същия начин при рекурсия функцията извиква сама себе си. Времевата сложност за рекурсивна функция се определя от броя пъти, когато функцията е извикана. Времевата сложност за едно извикване на функция е O(1). За n брой рекурсивни повиквания времевата сложност е O(n).
Какво е итерация?
Итерацията е блок от инструкции, който се повтаря отново и отново, докато даденото условие стане вярно. Итерацията може да бъде постигната с помощта на „for цикъл“, „do-while цикъл“или „while цикъл“. Синтаксисът на "for цикъл" е както следва.
за (инициализация; състояние; промяна) {
// изявления;
}
Фигура 02: „диаграма на потока за контур“
Стъпката на инициализация се изпълнява първа. Тази стъпка е да декларирате и инициализирате контролни променливи на цикъл. Ако условието е вярно, операторите във фигурните скоби се изпълняват. Тези изрази се изпълняват, докато условието е вярно. Ако условието е невярно, контролата преминава към следващия оператор след „цикъла for“. След изпълнение на изразите вътре в цикъла, контролата отива в секцията за модифициране. Това е за актуализиране на контролната променлива на цикъла. След това условието се проверява отново. Ако условието е вярно, операторите във фигурните скоби ще се изпълнят. По този начин „for цикълът“се повтаря.
В “while цикъл” операторите в цикъла се изпълняват, докато условието стане вярно.
докато (условие){
//изявления
}
В цикъла “do-while” условието се проверява в края на цикъла. И така, цикълът се изпълнява поне веднъж.
правя{
//изявления
} докато (условие)
Програмата за намиране на факториела на 3 (3!) с помощта на итерация („for цикъл“) е както следва.
int main(){
intn=3, факториел=1;
inti;
for(i=1; i<=n; i++){
факториал=факториелi;
}
printf(“Факториал е %d\n”, факториел);
върни 0;
}
Какви са приликите между рекурсия и итерация?
- И двете са техники за решаване на проблем.
- Задачата може да бъде решена чрез рекурсия или итерация.
Каква е разликата между рекурсия и итерация?
Рекурсия срещу итерация |
|
| Рекурсията е метод за извикване на функция в рамките на същата функция. | Итерацията е блок от инструкции, който се повтаря, докато даденото условие стане вярно. |
| Космическа сложност | |
| Пространствената сложност на рекурсивните програми е по-висока от итерациите. | Сложността на пространството е по-ниска при итерации. |
| Скорост | |
| Изпълнението на рекурсията е бавно. | Обикновено итерацията е по-бърза от рекурсията. |
| Състояние | |
| Ако няма условие за прекратяване, може да има безкрайна рекурсия. | Ако условието никога не стане невярно, това ще бъде безкрайна итерация. |
| Стак | |
| При рекурсия стекът се използва за съхраняване на локални променливи, когато се извика функцията. | В итерация стекът не се използва. |
| Четимост на кода | |
| Рекурсивната програма е по-четлива. | Итеративната програма е по-трудна за четене от рекурсивната програма. |
Резюме – Рекурсия срещу итерация
Тази статия обсъжда разликата между рекурсия и итерация. И двете могат да се използват за решаване на проблеми с програмирането. Разликата между рекурсия и итерация е, че рекурсията е механизъм за извикване на функция в рамките на същата функция и итерацията за изпълнение на набор от инструкции многократно, докато даденото условие е вярно. Ако даден проблем може да бъде решен в рекурсивна форма, той може да бъде решен и с помощта на итерации.
Изтеглете PDF версията на рекурсия срещу итерация
Можете да изтеглите PDF версия на тази статия и да я използвате за офлайн цели според бележката за цитиране. Моля, изтеглете PDF версия тук Разлика между рекурсия и итерация
