Ключевая разница - рекурсия и итерация
Рекурсия и итерация могут использоваться для решения задач программирования. Подход к решению задачи с помощью рекурсии или итерации зависит от способа решения задачи. Ключевое различие между рекурсией и итерацией заключается в том, что рекурсия - это механизм вызова функции внутри одной и той же функции, а итерация - многократное выполнение набора инструкций до тех пор, пока заданное условие не станет истинным. Рекурсия и итерация - основные методы разработки алгоритмов и создания программных приложений.
Что такое рекурсия?
Когда функция вызывает саму себя внутри функции, это называется рекурсией. Существует два типа рекурсии. Это конечная рекурсия и бесконечная рекурсия. Конечная рекурсия имеет завершающее условие. Бесконечная рекурсия не имеет условия завершения.
Рекурсию можно объяснить с помощью программы для вычисления факториалов.
н!=n(n-1)!, если n>0
н!=1, если n=0;
См. приведенный ниже код для вычисления факториала 3(3!=321).
intmain () {
целое значение=факториал (3);
printf("Факториал равен %d\n", значение);
возврат 0;
}
интфакториал (внутренний) {
if(n==0) {
возврат 1;
}
else {
возвратить n факториал(n-1);
}
}
При вызове factorial (3) эта функция вызовет factorial (2). При вызове factorial (2) эта функция вызовет factorial (1). Тогда факториал (1) вызовет факториал (0). factorial (0) вернет 1. В приведенной выше программе условие n==0 в блоке if является базовым условием. Аналогично, функция факториала вызывается снова и снова.
Рекурсивные функции связаны со стеком. В C основная программа может иметь множество функций. Итак, main() - это вызывающая функция, а функция, которую вызывает основная программа, - это вызываемая функция. При вызове функции управление передается вызываемой функции. После завершения выполнения функции управление возвращается на главную. Затем продолжается основная программа. Таким образом, он создает запись активации или кадр стека для продолжения выполнения.
Рисунок 01: Рекурсия
В приведенной выше программе при вызове factorial (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, factorial=1;
инти;
for(i=1; i<=n; i++){
factorial=factoriali;
}
printf("Факториал равен %d\n", факториал);
возврат 0;
}
Каковы сходства между рекурсией и итерацией?
- Оба метода позволяют решить проблему.
- Задачу можно решить как рекурсией, так и итерацией.
В чем разница между рекурсией и итерацией?
Рекурсия против итерации |
|
| Рекурсия - это метод вызова функции внутри той же функции. | Итерация - это блок инструкций, который повторяется до тех пор, пока заданное условие не станет истинным. |
| Космическая сложность | |
| Объемная сложность рекурсивных программ выше, чем итераций. | Сложность пространства ниже в итерациях. |
| Скорость | |
| Рекурсия выполняется медленно. | Обычно итерация выполняется быстрее, чем рекурсия. |
| Условие | |
| Если нет условия завершения, может быть бесконечная рекурсия. | Если условие никогда не становится ложным, это будет бесконечная итерация. |
| Стек | |
| В рекурсии стек используется для хранения локальных переменных при вызове функции. | В итерации стек не используется. |
| Читаемость кода | |
| Рекурсивная программа более читабельна. | Итеративную программу труднее читать, чем рекурсивную. |
Резюме – рекурсия против итерации
В этой статье обсуждалась разница между рекурсией и итерацией. Оба могут быть использованы для решения задач программирования. Разница между рекурсией и итерацией заключается в том, что рекурсия - это механизм вызова функции внутри одной и той же функции и повторения ее для повторного выполнения набора инструкций до тех пор, пока заданное условие не станет истинным. Если проблему можно решить в рекурсивной форме, ее также можно решить с помощью итераций.
Загрузить PDF-версию рекурсии и итерации
Вы можете загрузить PDF-версию этой статьи и использовать ее в автономном режиме в соответствии с примечанием к цитированию. Пожалуйста, загрузите PDF-версию здесь. Разница между рекурсией и итерацией
