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

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

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

Зачем нам нужна рекурсия?

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

Используя рекурсивный подход, можно решить такие вопросы, как Ханойские башни (TOH), обход дерева без порядка, обход дерева до порядка, обход по дереву после порядка, DFS графа и другие.

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

Мы можем определить шаги рекурсивного решения следующим образом:

1. Базовый случай

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

2. Рекурсивный вызов

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

3. Небольшой расчет

Как правило, мы выполняем некоторые шаги расчета при каждом рекурсивном вызове. Мы можем выполнить этот шаг вычисления до или после рекурсивного вызова в зависимости от характера проблемы. Здесь важно отметить, что рекурсия использует стек для хранения рекурсивных вызовов. Итак, чтобы избежать проблемы переполнения памяти, мы должны определить рекурсивное решение с минимально возможным количеством рекурсивных вызовов, чтобы базовое условие было достигнуто до того, как стек рекурсии начнет переполняться при заполнении.

СНАЧАЛА, ВАМ НУЖНО ПОНИМАТЬ, ЧТО ЯВЛЯЕТСЯ БОЛЬШЕЙ ПРОБЛЕМОЙ, И ПОТОМ КАК ОНА ЗАВИСИТ ОТ МЕНЬШЕЙ ПРОБЛЕМЫ, И ГДЕ НУЖНО ОСТАНОВИТЬ !!

Примечание.

Здесь интересно отметить, что концепция рекурсии основана на математической концепции PMI (принцип математической индукции).

Когда мы используем PMI для доказательства теоремы, мы должны показать, что базовый случай (обычно для x = 0 или x = 1) верен, и предположение индукции для случая x = k истинно должно подразумевать, что случай x = k + 1 тоже верно. Теперь мы можем понять, как шаги, которые мы выполнили в рекурсии, основаны на шагах индукции, как и в рекурсии, у нас есть базовый случай, в то время как предположение соответствует рекурсивному вызову.

Почему при рекурсии возникает ошибка переполнения стека?

Если базовый случай недостижим или не определен в коде, код завершается бесконечным циклом и выдает исключение StackOverflow.

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

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

Рассмотрим рекурсивный факт функции (int n)

int факт (int n)

{

// неправильный базовый случай (это может вызвать переполнение стека).

if (n == 100)

возврат 1;

еще

return n * fact (n-1);

}

В этом вопросе пусть n = 5. Когда fact () вызывает рекурсивные вызовы, он вызывает fact (4), fact (3)… .. но никогда не достигнет fact (100). Итак, базовый случай недостижим, память исчерпана этими функциями в стеке, это вызовет ошибку переполнения стека.

Приложения

После понимания концепции и работы рекурсивных функций давайте разберемся, где обычно используется рекурсия:

  1. Динамическое программирование
  2. Графики
  3. Деревья
  4. Возврат
  5. Алгоритмы разделяй и властвуй

Несколько хороших вопросов, которые помогут вам лучше понять решение вопросов с помощью рекурсии

  1. Комбинированная сумма
  2. Удалить средний элемент стопки
  3. Сортировка стека с помощью рекурсии
  4. Перестановка с пробелами
  5. Генератор мощности
  6. Перестановки заданной строки
  7. K-й символ в грамматике
  8. Реши судоку

Ресурсы