В чем разница между возвратом и рекурсией?
Опубликовано: 21 Февраля, 2023
Что такое рекурсия?
The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function.
Свойства рекурсии:
- Выполнение одних и тех же операций несколько раз с разными входными данными.
- На каждом этапе мы пытаемся вводить меньшие входные данные, чтобы уменьшить проблему.
- Базовое условие необходимо для остановки рекурсии, иначе возникнет бесконечный цикл.
Что такое откат?
Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point in time (by time, here, is referred to the time elapsed till reaching any level of the search tree).
Поиск с возвратом можно определить как общий алгоритмический метод, который рассматривает поиск всех возможных комбинаций для решения вычислительной задачи.
При возврате существует три типа проблем:
- Проблема решения. В этом мы ищем возможное решение.
- Проблема оптимизации. Здесь мы ищем лучшее решение.
- Проблема перечисления. В ней мы находим все возможные решения.
В чем разница между возвратом и рекурсией?
| Сл. Нет. | Рекурсия | Возвращение |
|---|---|---|
| 1 | Рекурсия не всегда требует возврата | Backtracking всегда использует рекурсию для решения проблем |
| 2 | Рекурсивная функция решает конкретную проблему, вызывая свою копию и решая меньшие подзадачи исходных задач. | Возврат на каждом шагу устраняет те варианты, которые не могут дать нам решение, и переходит к тем вариантам, которые потенциально могут привести нас к решению. |
| 3 | Рекурсия является частью самого поиска с возвратом, и ее проще написать. | Возврат сравнительно сложен в реализации. |
| 4 | Приложениями рекурсии являются обход дерева и графика, Ханойские башни, алгоритмы «разделяй и властвуй», сортировка слиянием, быстрая сортировка и двоичный поиск. | Применение Backtracking - задача N Queen, задача Rat in a Maze, задача Knight's Tour, решение судоку и задачи раскраски графа. |
Статьи по Теме:
- Введение в рекурсию - учебные пособия по структурам данных и алгоритмам
- Введение в поиск с возвратом — учебные пособия по структурам данных и алгоритмам