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

• 2019

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

Сравнительная таблица

Основа для сравнения	Рекурсия	итерация
основной	Оператор в теле функции вызывает саму функцию.	Позволяет многократно выполнять набор инструкций.
Формат	В рекурсивной функции указывается только условие завершения (базовый случай).	Итерация включает в себя инициализацию, условие, выполнение оператора в цикле и обновление (увеличение и уменьшение) управляющей переменной.
прекращение	Условный оператор включен в тело функции, чтобы заставить функцию возвращаться без выполнения рекурсивного вызова.	Оператор итерации выполняется многократно, пока не будет достигнуто определенное условие.
Состояние	Если функция не сходится к какому-либо условию (базовый случай), это приводит к бесконечной рекурсии.	Если условие управления в инструкции итерации никогда не становится ложным, это приводит к бесконечной итерации.
Бесконечное повторение	Бесконечная рекурсия может привести к сбою системы.	Бесконечный цикл использует циклы процессора многократно.
прикладной	Рекурсия всегда применяется к функциям.	Итерация применяется к операторам итерации или «циклам».
стек	Стек используется для хранения набора новых локальных переменных и параметров при каждом вызове функции.	Не использует стек.
накладные расходы	Рекурсия обладает накладными расходами на повторные вызовы функций.	Нет накладных расходов на повторный вызов функции.
скорость	Медленный в исполнении.	Быстро в исполнении.
Размер кода	Рекурсия уменьшает размер кода.	Итерация делает код длиннее.

Определение рекурсии

C ++ позволяет функции вызывать себя внутри своего кода. Это означает, что определение функции обладает вызовом функции для себя. Иногда это также называют « круговым определением ». Набор локальных переменных и параметров, используемых функцией, создается заново каждый раз, когда функция вызывает себя, и сохраняется в верхней части стека. Но каждый раз, когда функция вызывает себя, она не создает новую копию этой функции. Рекурсивная функция существенно не уменьшает размер кода и даже не улучшает использование памяти, но делает некоторые по сравнению с итерацией.

Чтобы завершить рекурсию, вы должны включить оператор SELECT в определение функции, чтобы заставить функцию возвращаться без рекурсивного вызова самой себя. Отсутствие оператора select в определении рекурсивной функции позволит функции в бесконечной рекурсии однажды вызываться.

Давайте разберемся с рекурсией с помощью функции, которая будет возвращать факториал числа.

 int factorial (int num) {int answer; if (num == 1) {return 1; } else {answer = factorial (num-1) * num; // рекурсивный вызов} return (answer); } 

В приведенном выше коде оператор в другой части показывает рекурсию, так как оператор вызывает функцию factorial (), в которой он находится.

Определение итерации

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

Оператор итерации не использует стек для хранения переменных. Следовательно, выполнение оператора итерации быстрее по сравнению с рекурсивной функцией. Даже у итерационной функции нет накладных расходов на повторный вызов функции, что также делает ее выполнение быстрее, чем рекурсивная функция. Итерация заканчивается, когда условие управления становится ложным. Отсутствие условия управления в операторе итерации может привести к бесконечному циклу или к ошибке компиляции.

Давайте разберемся с итерацией в отношении приведенного выше примера.

 int factorial (int num) {int answer = 1; // требуется инициализация, поскольку она может содержать мусорное значение перед инициализацией для (int t = 1; t> num; t ++) // iteration {answer = answer * (t); возврат (ответ); }} 

В приведенном выше коде функция возвращает факториал числа, используя оператор итерации.

Ключевые различия между рекурсией и итерацией

1. Рекурсия - это когда метод в программе повторно вызывает сам себя, тогда как итерация - это когда набор инструкций в программе выполняется многократно.
2. Рекурсивный метод содержит набор инструкций, сам оператор вызова и условие завершения, тогда как операторы итерации содержат инициализацию, приращение, условие, набор инструкций в цикле и управляющую переменную.
3. Условный оператор решает завершение рекурсии, а значение управляющей переменной определяет завершение итерационного оператора.
4. Если метод не приводит к условию завершения, он входит в бесконечную рекурсию. С другой стороны, если переменная управления никогда не приводит к значению завершения, оператор итерации повторяется бесконечно.
5. Бесконечная рекурсия может привести к сбою системы, тогда как бесконечная итерация потребляет циклы ЦП.
6. Рекурсия всегда применяется к методу, тогда как итерация применяется к набору инструкций.
7. Переменные, созданные во время рекурсии, хранятся в стеке, тогда как для итерации стек не требуется.
8. Рекурсия вызывает издержки повторного вызова функции, тогда как итерация не имеет функции, вызывающей издержки.
9. Из-за накладных расходов на вызов функции выполнение рекурсии медленнее, тогда как выполнение итерации быстрее.
10. Рекурсия уменьшает размер кода, тогда как итерации делают код длиннее.

Заключение:

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