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