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

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

Как работает рекурсия?

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

Пример

Давайте посмотрим, как этот код работает в деталях:

int _pow_recursion(int x, int y)
{
 if (y == 0)
 return (1);
 
 if (y < 0)
 return (_pow_recursion(x, y + 1) / x);
 
 return (_pow_recursion(x, y — 1) * x);
}

На рисунке ниже показана иллюстрация для случая, когда x = 3, y = 3.

  1. _pow_recursion(3, 0) возвращает 1
  2. _pow_recursion(3, 1) возвращает _pow_recursion(3, 0) * 3. Результат _pow_recursion(3, 0) равен 1, поэтому 1 * 3 = 3. Таким образом, результат _pow_recursion(3, 1) равен 3
  3. _pow_recursion(3, 2) возвращает _pow_recursion(3, 1) * 3.
    3 * 3 = 9
  4. _pow_recursion(3, 3) возвращает _pow_recursion(3, 2) * 3.
    9 * 3 = 27. Таким образом, результат 3**3 равен 27.
    Функция pow-рекурсии вызывает саму себя, вычитая с 1, пока базовый случай не будет распознан.

Различия и сходства (итеративность и рекурсия)

Итеративный метод также является методом решения проблем, но вместо вызовов функций для выполнения оператора мы используем циклы, такие как while или for.

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

Различия

Краткое содержание

Рекурсия — это широко используемая парадигма программирования, относящаяся к категории подходов разделяй и властвуй. Когда проблему трудно решить, рекурсивный метод направлен на решение меньшего экземпляра проблемы. Он повторяет одни и те же шаги (рекурсивный шаг) до тех пор, пока не будет найдено тривиальное решение (базовый случай).

Хотя рекурсивные методы эффективны во многих практических ситуациях, они часто страдают от высокой временной и пространственной сложности.

Вы когда-нибудь использовали рекурсию? Какие ваши любимые парадигмы программирования? Комментарий ниже :)

Ресурсы
GeeksforGeeks