В чем разница между возвратом и рекурсией? Как работает эта программа?
void generate_all(int n)
{
if(n<1) printf("%s\n", ar);
else{
ar[n-1]='0'; //fix (n)th bit as '0'
generate_all(n-1); //generate all combinations for other n-1 positions.
ar[n-1]='1'; //fix (n)th bit as '1'
generate_all(n-1); //generate all combinations for other n-1 positions.
}
Этот вопрос все равно, что спросить, в чем разница между автомобилем и делорианом.
В рекурсии функция вызывает сама себя, пока не достигнет базового варианта.
В обратном отслеживании вы используете рекурсию, чтобы изучить все возможности, пока не получите лучший результат для задачи.
Может быть немного трудно понять, я прилагаю текст из здесь:
"Концептуально вы начинаете с корня дерева; дерево, вероятно, имеет несколько хороших листьев и несколько плохих листьев, хотя может случиться так, что листья все хорошие или все плохие. Вы хотите получить хороший лист. В каждом узле Начиная с корня, вы выбираете одного из его дочерних элементов, к которому хотите перейти, и продолжаете в том же духе, пока не дойдете до листа.
Предположим, вы попали в плохой лист. Вы можете вернуться, чтобы продолжить поиск хорошего листа, отменив последний выбор и опробовав следующий вариант в этом наборе параметров. Если у вас закончились варианты, отмените выбор, который получил вас здесь, и попробуйте другой вариант на этом узле. Если вы окажетесь в корне, и у вас не останется ни одного варианта, хороших листьев не будет. "
Для этого нужен пример:
Ваш кусок кода является просто рекурсией, поскольку вы никогда не получите ответ, если результат не соответствует вашей цели.
Рекурсия описывает вызов той же функции, в которой вы находитесь. Типичным примером рекурсивной функции является факториал, т.е. что-то вроде
int fact(int n) {
int result;
if(n==1) return 1;
result = fact(n-1) * n;
return result;
}
То, что вы видите здесь, тот факт вызывает сам. Это то, что называется рекурсией. Вам всегда нужно условие, которое останавливает рекурсию. Здесь if(n==1) в сочетании с тем, что n всегда будет уменьшаться каждый раз, когда он вызывается (fact(n-1))
Backtracking - это алгоритм, который пытается найти решение заданных параметров. Он создает кандидатов для решения и оставляет те, которые не могут выполнить условия. Типичным примером для решения задачи будет Eight Queens Puzzle. Backtracking также широко используется в нейронных сетях.
В описанной вами программе используется рекурсия. Подобно факториальной функции, он уменьшает аргумент на 1 и заканчивается, если n < 1 (потому что тогда он будет печатать ar вместо остальных).
В моем понимании, backtracking - это алгоритм, как и все другие алгоритмы, такие как BFS и DFS, но рекурсия, а также итерация - это методы, они находятся на более высоком уровне, чем алгоритмы, например, для реализации DFS, вы может использовать рекурсию, которая довольно интуитивно понятна, но вы также можете использовать итерацию со стеком, или вы также можете думать, что рекурсия и итерация - это просто методы поддержки ваших алгоритмов.
рекурсия - нет заброшенных значений;
возвращение назад - отказаться от некоторых вариантов решения;
Также обратите внимание, что обратное отслеживание будет вызывать себя более одного раза в теле функции, хотя обычно это не так для рекурсии.
Рекурсия похожа на процесс снизу вверх. Вы можете решить проблему, просто используя результат подзадачи.
Например, обратный LinkedList с использованием рекурсии просто добавляет головной узел в уже перевернутый подсписок.https://leetcode.com/problems/reverse-linked-list/discuss/386764/Java-recursive
Откат по-прежнему похож на нисходящий процесс. Иногда вы не можете решить проблему, просто используя результат подзадачи, вам нужно передать информацию, которую вы уже получили, подзадачам. Ответ на эту проблему будет вычислен на самом низком уровне, а затем эти ответы будут возвращены к проблеме с информацией, которую вы получили по пути.