Я изучал рекурсивные функции, и, очевидно, они являются функциями, которые вызывают сами себя и не используют итераций / циклов (иначе это не было бы рекурсивной функцией).
Однако, просматривая примеры в интернете (рекурсивная проблема с 8 ферзями), я обнаружил эту функцию:
private boolean placeQueen(int rows, int queens, int n) {
boolean result = false;
if (row < n) {
while ((queens[row] < n - 1) && !result) {
queens[row]++;
if (verify(row,queens,n)) {
ok = placeQueen(row + 1,queens,n);
}
}
if (!result) {
queens[row] = -1;
}
}else{
result = true;
}
return result;
}
Здесь while
задействована петля.
... так что я немного растерялся сейчас. Могу ли я использовать петли или нет?
placeQueen
является «место 8 королев», а более простой версиейplaceQueen
- «место 7 королев» (затем место 6 и т. Д.)Ответы:
Вы неправильно поняли рекурсию: хотя она может использоваться для замены итерации, абсолютно не требуется, чтобы рекурсивная функция не имела внутренних итераций.
Единственное требование, чтобы функция считалась рекурсивной, - это наличие пути кода, через который она вызывает себя, прямо или косвенно. Все правильные рекурсивные функции также имеют своего рода условные выражения, предотвращающие их «повторное использование» навсегда.
Ваша рекурсивная функция идеально подходит для иллюстрации структуры рекурсивного поиска с возвратом. Он начинается с проверки условия выхода
row < n
и переходит к принятию решений о поиске на уровне рекурсии (т. Е. Выбирается возможная позиция для номера ферзяrow
). После каждой итерации выполняется рекурсивный вызов для построения конфигурации, которую функция нашла до сих пор; в конце концов, он «row
достигает дна», когда достигаетn
в рекурсивном вызовеn
уровня глубоко.источник
Общая структура рекурсивной функции выглядит примерно так:
Текст, который я пометил как
/*recursive processing*/
мог быть чем угодно. Он может включать цикл, если этого требует решаемая проблема, а также может включать рекурсивные вызовыmyRecursiveFunction
.источник
Вы наверняка можете использовать циклы в рекурсивной функции. То, что делает функцию рекурсивной, это только тот факт, что функция вызывает себя в какой-то момент своего пути выполнения. Однако у вас должно быть какое-то условие, чтобы предотвратить бесконечные рекурсивные вызовы, из которых ваша функция не может вернуться.
источник
Рекурсивные вызовы и циклы - это всего лишь два способа / конструкции для реализации итерационных вычислений.
А
while
петля соответствует хвостовой рекурсии вызова (смотрите , например , здесь ), т.е. итерация , в которой вам не нужно сохранять промежуточные результаты между двумя итерациями (все результаты одного цикла готовы , когда вы входите в следующий цикл). Если вам нужно сохранить промежуточные результаты, которые вы сможете использовать позже, вы можете использоватьwhile
цикл вместе со стеком (см. Здесь ), или нерекурсивный (то есть произвольный) рекурсивный вызов.Многие языки позволяют вам использовать оба механизма, и вы можете выбрать тот, который вам больше подходит, и даже смешать их вместе в своем коде. В императивных языках, таких как C, C ++, Java и т. Д., Вы обычно используете цикл
while
или,for
когда вам не нужен стек, и используете рекурсивные вызовы, когда вам нужен стек (вы неявно используете стек времени выполнения). Haskell (функциональный язык) не предлагает структуру управления итерацией, поэтому вы можете использовать только рекурсивные вызовы для выполнения итерации.В вашем примере (см. Мои комментарии):
источник
Вы правы, полагая, что существует связь между рекурсией и итерацией или циклом. Рекурсивные алгоритмы часто вручную или даже автоматически преобразуются в итерационные решения с использованием оптимизации хвостового вызова.
В восьми королевах рекурсивная часть связана с хранением данных, необходимых для обратного отслеживания. Когда вы думаете о рекурсии, полезно подумать о том, что помещается в стек. Стек может содержать передаваемые по значению параметры и локальные переменные, которые играют ключевую роль в алгоритме, или иногда вещи, которые не так очевидны, как адрес возврата, или в этом случае переданное значение с количеством используемых ферзей, но не изменяется по алгоритму.
Действие, которое происходит в восьми королевах, заключается в том, что по существу нам дается частичное решение для некоторого числа королев в первых нескольких столбцах, из которого мы итеративно определяем допустимые на текущий момент выборы в текущем столбце, которые мы рекурсивно передаем для оценки для остальные столбцы. Локально, восемь ферзей отслеживают, какую строку он пробует, и, если происходит обратное отслеживание, он готов перешагнуть оставшиеся строки или продолжить отслеживание, просто вернувшись, если не найдет другой строки, которая могла бы работать.
источник
Часть «создать уменьшенную версию проблемы» может иметь петли. Пока метод вызывает себя, передавая в качестве параметра меньшую версию проблемы, метод является рекурсивным. Конечно, условие выхода, когда решается наименьшая возможная версия проблемы и метод возвращает значение, должно быть предусмотрено, чтобы избежать условия переполнения стека.
Метод в вашем вопросе является рекурсивным.
источник
В основном, рекурсия вызывает вашу функцию снова, и главное преимущество рекурсии - экономия памяти. В рекурсии могут быть циклы, которые они используют для выполнения какой-либо другой операции.
источник