Разница между рекурсией и итерацией

2024 Автор: Mildred Bawerman | [email protected]. Последнее изменение: 2023-12-16 08:42

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

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

СОДЕРЖАНИЕ

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-версию здесь. Разница между рекурсией и итерацией.