Сравнительная таблица
| Основа для сравнения | Рекурсия | итерация |
|---|---|---|
| основной | Оператор в теле функции вызывает саму функцию. | Позволяет многократно выполнять набор инструкций. |
| Формат | В рекурсивной функции указывается только условие завершения (базовый случай). | Итерация включает в себя инициализацию, условие, выполнение оператора в цикле и обновление (увеличение и уменьшение) управляющей переменной. |
| прекращение | Условный оператор включен в тело функции, чтобы заставить функцию возвращаться без выполнения рекурсивного вызова. | Оператор итерации выполняется многократно, пока не будет достигнуто определенное условие. |
| Состояние | Если функция не сходится к какому-либо условию (базовый случай), это приводит к бесконечной рекурсии. | Если условие управления в инструкции итерации никогда не становится ложным, это приводит к бесконечной итерации. |
| Бесконечное повторение | Бесконечная рекурсия может привести к сбою системы. | Бесконечный цикл использует циклы процессора многократно. |
| прикладной | Рекурсия всегда применяется к функциям. | Итерация применяется к операторам итерации или «циклам». |
| стек | Стек используется для хранения набора новых локальных переменных и параметров при каждом вызове функции. | Не использует стек. |
| накладные расходы | Рекурсия обладает накладными расходами на повторные вызовы функций. | Нет накладных расходов на повторный вызов функции. |
| скорость | Медленный в исполнении. | Быстро в исполнении. |
| Размер кода | Рекурсия уменьшает размер кода. | Итерация делает код длиннее. |
Определение рекурсии
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); возврат (ответ); }} В приведенном выше коде функция возвращает факториал числа, используя оператор итерации.
Ключевые различия между рекурсией и итерацией
- Рекурсия - это когда метод в программе повторно вызывает сам себя, тогда как итерация - это когда набор инструкций в программе выполняется многократно.
- Рекурсивный метод содержит набор инструкций, сам оператор вызова и условие завершения, тогда как операторы итерации содержат инициализацию, приращение, условие, набор инструкций в цикле и управляющую переменную.
- Условный оператор решает завершение рекурсии, а значение управляющей переменной определяет завершение итерационного оператора.
- Если метод не приводит к условию завершения, он входит в бесконечную рекурсию. С другой стороны, если переменная управления никогда не приводит к значению завершения, оператор итерации повторяется бесконечно.
- Бесконечная рекурсия может привести к сбою системы, тогда как бесконечная итерация потребляет циклы ЦП.
- Рекурсия всегда применяется к методу, тогда как итерация применяется к набору инструкций.
- Переменные, созданные во время рекурсии, хранятся в стеке, тогда как для итерации стек не требуется.
- Рекурсия вызывает издержки повторного вызова функции, тогда как итерация не имеет функции, вызывающей издержки.
- Из-за накладных расходов на вызов функции выполнение рекурсии медленнее, тогда как выполнение итерации быстрее.
- Рекурсия уменьшает размер кода, тогда как итерации делают код длиннее.
Заключение:
Рекурсивная функция проста в написании, но она неэффективна по сравнению с итерацией, в то время как итерация трудна для записи, но ее производительность хорошая по сравнению с рекурсией.
