Может ли рекурсивная функция иметь итерации / циклы?

12

Я изучал рекурсивные функции, и, очевидно, они являются функциями, которые вызывают сами себя и не используют итераций / циклов (иначе это не было бы рекурсивной функцией).

Однако, просматривая примеры в интернете (рекурсивная проблема с 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задействована петля.

... так что я немного растерялся сейчас. Могу ли я использовать петли или нет?

Омега
источник
5
Это компилируется. Да. Так зачем спрашивать?
Томас Эдинг
6
Всего определение рекурсии является то , что в какой - то момент, функция может быть повторно вызывается как часть своего собственного выполнения , прежде чем он возвращается (будь то повторно вызывается самостоятельно или с помощью какой - либо другой функции , которую он называет). Ничто в этом определении не исключает возможности зацикливания.
Чао
В качестве дополнения к комментарию cHao, рекурсивная функция будет повторно вызываться для более простой версии самой себя (в противном случае она будет зациклена навсегда). Процитируем орблинг (из «Простого английского языка, что такое рекурсия?» ): «Рекурсивное программирование - это процесс постепенного сокращения проблемы до более простого решения ее версий». В этом случае самой сложной версией placeQueenявляется «место 8 королев», а более простой версией placeQueen- «место 7 королев» (затем место 6 и т. Д.)
Брайан
Вы можете использовать все, что работает Омега. Очень редко в спецификациях программного обеспечения указывается, какой стиль программирования использовать - если вы не учитесь в школе и ваше назначение не говорит об этом.
Апурв Хурасия
@ThomasEding: Да, конечно, он компилируется и работает. Но сейчас я просто изучаю инженерию - для меня сейчас важна строгая концепция / определение, а не то, как ее используют программисты в наши дни. Поэтому я спрашиваю, верна ли моя концепция (что, похоже, не так).
Омега

Ответы:

41

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

Единственное требование, чтобы функция считалась рекурсивной, - это наличие пути кода, через который она вызывает себя, прямо или косвенно. Все правильные рекурсивные функции также имеют своего рода условные выражения, предотвращающие их «повторное использование» навсегда.

Ваша рекурсивная функция идеально подходит для иллюстрации структуры рекурсивного поиска с возвратом. Он начинается с проверки условия выхода row < nи переходит к принятию решений о поиске на уровне рекурсии (т. Е. Выбирается возможная позиция для номера ферзя row). После каждой итерации выполняется рекурсивный вызов для построения конфигурации, которую функция нашла до сих пор; в конце концов, он « rowдостигает дна», когда достигает nв рекурсивном вызове nуровня глубоко.

dasblinkenlight
источник
1
+1 для «правильных» рекурсивных функций есть условные, множество неправильных, которые не хе
Джимми Хоффа
6
+1 "возвращающийся вниз" навсегда `Черепаха () {Turtle ();}
Мистер Миндор,
1
@ Mr.Mindor Мне нравится цитата "Это все черепахи внизу" :)
dasblinkenlight
Это заставило меня улыбнуться :-)
Martijn Verburg
2
«Все правильные рекурсивные функции также имеют какое-то условие, предотвращающее их« повторное использование »навсегда». не верно с не строгой оценкой.
Пабби
12

Общая структура рекурсивной функции выглядит примерно так:

myRecursiveFunction(inputValue)
begin
   if evaluateBaseCaseCondition(inputValue)=true then
       return baseCaseValue;
   else
       /*
       Recursive processing
       */
       recursiveResult = myRecursiveFunction(nextRecursiveValue); //nextRecursiveValue could be as simple as inputValue-1
       return recursiveResult;
   end if
end

Текст, который я пометил как /*recursive processing*/мог быть чем угодно. Он может включать цикл, если этого требует решаемая проблема, а также может включать рекурсивные вызовы myRecursiveFunction.

FrustratedWithFormsDesigner
источник
1
Это вводит в заблуждение, поскольку подразумевает, что существует только один рекурсивный вызов, и в значительной степени исключает случаи, когда рекурсивный вызов сам находится внутри цикла (например, обход B-дерева).
Питер Тейлор
@PeterTaylor: Да, я пытался сделать это простым.
FrustratedWithFormsDesigner
Или даже несколько вызовов без цикла, как, например, обход простого двоичного дерева, когда у вас будет 2 вызова, потому что у каждого узла будет 2 дочерних элемента.
Изката
6

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

марко-fiset
источник
1

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

А whileпетля соответствует хвостовой рекурсии вызова (смотрите , например , здесь ), т.е. итерация , в которой вам не нужно сохранять промежуточные результаты между двумя итерациями (все результаты одного цикла готовы , когда вы входите в следующий цикл). Если вам нужно сохранить промежуточные результаты, которые вы сможете использовать позже, вы можете использовать whileцикл вместе со стеком (см. Здесь ), или нерекурсивный (то есть произвольный) рекурсивный вызов.

Многие языки позволяют вам использовать оба механизма, и вы можете выбрать тот, который вам больше подходит, и даже смешать их вместе в своем коде. В императивных языках, таких как C, C ++, Java и т. Д., Вы обычно используете цикл whileили, forкогда вам не нужен стек, и используете рекурсивные вызовы, когда вам нужен стек (вы неявно используете стек времени выполнения). Haskell (функциональный язык) не предлагает структуру управления итерацией, поэтому вы можете использовать только рекурсивные вызовы для выполнения итерации.

В вашем примере (см. Мои комментарии):

// queens should have type int [] , not int.
private boolean placeQueen(int row, int [] queens, int n)
{
    boolean result = false;
    if (row < n)
    {
        // Iterate with queens[row] = 1 to n - 1.
        // After each iteration, you either have a result
        // in queens, or you have to try the next column for
        // the current row: no intermediate result.
        while ((queens[row] < n - 1) && !result)
        {
            queens[row]++;
            if (verify(row,queens,n))
            {
                // I think you have 'result' here, not 'ok'.
                // This is another loop (iterate on row).
                // The loop is implemented as a recursive call
                // and the previous values of row are stored on
                // the stack so that we can resume with the previous
                // value if the current attempt finds no solution.
                result = placeQueen(row + 1,queens,n);
            }
        }
        if (!result) {
            queens[row] = -1;
        }
    }else{
        result = true;
    }
    return result;
}
Джорджио
источник
1

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

В восьми королевах рекурсивная часть связана с хранением данных, необходимых для обратного отслеживания. Когда вы думаете о рекурсии, полезно подумать о том, что помещается в стек. Стек может содержать передаваемые по значению параметры и локальные переменные, которые играют ключевую роль в алгоритме, или иногда вещи, которые не так очевидны, как адрес возврата, или в этом случае переданное значение с количеством используемых ферзей, но не изменяется по алгоритму.

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

DeveloperDon
источник
0

Часть «создать уменьшенную версию проблемы» может иметь петли. Пока метод вызывает себя, передавая в качестве параметра меньшую версию проблемы, метод является рекурсивным. Конечно, условие выхода, когда решается наименьшая возможная версия проблемы и метод возвращает значение, должно быть предусмотрено, чтобы избежать условия переполнения стека.

Метод в вашем вопросе является рекурсивным.

Тулаинс Кордова
источник
0

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

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