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

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

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

СОДЕРЖАНИЕ

1. Обзор и основные отличия
2. Что такое рекурсия
3. Что такое итерация
4. Сходства между рекурсией и итерацией
5. Сравнение бок о бок - рекурсия и итерация в табличной форме
6. Резюме

Что такое рекурсия?

Когда функция вызывает себя внутри функции, она называется рекурсией. Есть два типа рекурсии. Это конечная рекурсия и бесконечная рекурсия. Конечная рекурсия имеет завершающее условие. Бесконечная рекурсия не имеет завершающего условия.

Рекурсию можно объяснить с помощью программы для расчета факториалов.

п! = n * (n-1) !, если n> 0

п! = 1, если n = 0;

См. Приведенный ниже код для расчета факториала 3 (3! = 3 * 2 * 1).

intmain ()

значение int = factorial (3);

printf («Факториал -% d \ n», значение);

вернуть 0;

intfactorial (intn)

if (n == 0)

возврат 1;

еще

вернуть n * факториал (n-1);

При вызове factorial (3) эта функция будет вызывать factorial (2). При вызове factorial (2) эта функция будет вызывать factorial (1). Тогда факториал (1) назовет факториал (0). factorial (0) вернет 1. В вышеприведенной программе условие n == 0 в блоке if является базовым условием. По аналогии, факториальная функция вызывается снова и снова.

Рекурсивные функции связаны со стеком. В C основная программа может иметь много функций. Таким образом, main () является вызывающей функцией, а функция, которая вызывается основной программой, является вызываемой функцией. Когда функция вызывается, управление передается вызываемой функции. После завершения выполнения функции управление возвращается в main. Затем основная программа продолжается. Таким образом, он создает запись активации или кадр стека для продолжения выполнения.

Рисунок 01: Рекурсия

В приведенной выше программе при вызове factorial (3) из main она создает запись активации в стеке вызовов. Затем создаётся кадр стека факториала (2) поверх стека и так далее. В записи активации хранится информация о локальных переменных и т. Д. Каждый раз, когда вызывается функция, в верхней части стека создается новый набор локальных переменных. Эти кадры стека могут замедлить скорость. Аналогично в рекурсии, функция вызывает себя. Временная сложность для рекурсивной функции определяется тем, сколько раз вызывается функция. Временная сложность для одного вызова функции составляет O (1). Для n числа рекурсивных вызовов сложность времени составляет O (n).

Что такое итерация?

Итерация - это блок инструкций, который повторяется снова и снова, пока данное условие не станет истинным. Итерация может быть достигнута с помощью «цикла for», «цикла do-while» или «цикла while». Синтаксис «для цикла» выглядит следующим образом.

for (инициализация; условие; изменить)

// заявления;

Рисунок 02: «для петлевой схемы»

Шаг инициализации выполняется первым. Этот шаг должен объявить и инициализировать переменные управления цикла. Если условие истинно, выполняются операторы внутри фигурных скобок. Эти операторы выполняются до тех пор, пока условие не станет истинным. Если условие ложно, элемент управления переходит к следующему оператору после «цикла for». После выполнения операторов внутри цикла, элемент управления переходит к модификации раздела. Это обновить переменную управления цикла. Затем условие проверяется снова. Если условие истинно, операторы внутри фигурных скобок будут выполняться. Таким образом, цикл for.

В «цикле пока», операторы внутри цикла выполняются до тех пор, пока условие не станет истинным.

while (условие)

//заявления

В цикле «делай пока», условие проверяется в конце цикла. Итак, цикл выполняется хотя бы один раз.

делать

//заявления

while (условие)

Программа для поиска факториала 3 (3!) С использованием итерации («для цикла») выглядит следующим образом.

int main ()

intn = 3, факториал = 1;

Инти;

для (я = 1; я<=n ; i++)

факториал = факториал * я;

printf («Факториал - это% d \ n», факториал);

вернуть 0;

Каковы сходства между рекурсией и итерацией?

• Оба метода для решения проблемы.
• Задача может быть решена в рекурсии или итерации.

В чем разница между рекурсией и итерацией?

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

Резюме - рекурсия против итерации

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

Скачать PDF версию рекурсии против итерации

Вы можете скачать PDF версию этой статьи и использовать ее в автономном режиме, как указано в примечании. Пожалуйста, загрузите PDF версию здесь Разница между рекурсией и итерацией

Ссылка:

1.Point, учебники. «Основы рекурсии структур данных и алгоритмов». Учебное пособие, 15 августа 2017 г. Доступно здесь 
2.nareshtechnologies. «Рекурсия в C-функциях | C Language Tutorial »YouTube, YouTube, 12 сентября 2016 года. Доступно здесь  
3.юсуф шейкель. «Рекурсивный алгоритм | Факториал - пошаговое руководство »YouTube, YouTube, 14 октября 2013 г. Доступно здесь  

Изображение предоставлено:

1. 'CPT-Recursion-Factorial-Code'By Pluke - собственная работа, (общественное достояние) через Commons Wikimedia 
2. «Для петлевой диаграммы» Автор не предоставил машиночитаемого текста - Предполагается собственная работа. (CC BY-SA 2.5) через Commons Wikimedia