Разница между возвратом и рекурсией?

Этот вопрос похож на вопрос, в чем разница между автомобилем и DeLorean.

В рекурсии функция вызывает себя, пока не достигнет базового случая.

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

Может быть немного сложно понять, я прикрепляю текст из здесь :

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

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))

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

Описанная вами программа использует рекурсию. Подобно функции факториала, она уменьшает аргумент на 1 и завершается, если n‹1 (потому что тогда она будет печатать ar вместо остальных).

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

рекурсия - нет брошенных значений;

возврат - отказаться от некоторых вариантов решения;

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

Рекурсия такая же, как то, что вы показали. Если подпрограмма A вызывает A или если A вызывает B, а B вызывает A, это рекурсия.

Backtrack — это не алгоритм, это структура управления. При использовании возврата программа кажется способной работать в обратном направлении. Это полезно при написании программы для такой игры, как шахматы, где вы хотите заглянуть вперед на некоторое количество ходов. Когда программа хочет сделать ход, она выбирает ход, затем переключается на программу-противника, которая делает ход, и так далее. Если исходная программа доходит до нужного места, она хочет сказать «Ура» и выполнить первый сделанный ход. Если какая-либо программа попадает в плохое место, она хочет отступить и попробовать другой ход.

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

Итак, если эта идея привлекательна, как вы это делаете? Во-первых, вам нужен своего рода оператор, представляющий choice, где выбирается ход, к которому вы можете вернуться и пересмотреть свой выбор. Во-вторых, всякий раз, когда у вас есть последовательность операторов, подобных A;B, вы делаете A функцией и передаете ей функцию, способную выполнять B. Что-то вроде A(lambda()B(...)). Поэтому, когда A завершает выполнение, перед возвратом он вызывает свой аргумент, который выполняет B. Если A хочет потерпеть неудачу и начать работать в обратном направлении, он просто возвращается, не вызывая функцию, которая вызывает B. Я знаю, что этому трудно следовать. Я сделал это с помощью макросов в LISP, и это работает хорошо. Сделать это на обычном языке компилятора, таком как C++, невероятно сложно.

Я сделал что-то подобное на C/C++ таким образом, чтобы сохранить красоту, но на самом деле не работал в обратном направлении. Идея состоит в том, что вы делаете это для выполнения поиска по дереву в глубину. Но вместо этого вы могли бы сделать это серией ударов вниз от корня дерева, следуя по другому пути каждый раз, когда вы наносите удар. Против этого могут возразить по соображениям производительности, но на самом деле это не стоит намного больше, поскольку основная часть работы выполняется в листьях дерева. Если дерево имеет 3 слоя в глубину и имеет коэффициент ветвления 5 в каждом узле, это означает, что оно имеет 5 + 25 + 125 или 155 узлов. Но в серии ударов от корня он посещает 125 * 3 = 375 узлов, снижение производительности менее чем в 3 раза, что может быть вполне терпимо, если только производительность не является проблемой. (Помните, что настоящий возврат может включать довольно много машин, создание лямбда-выражений и так далее.)

Вот основной код, с которым я это сделал:

#define NLEVEL 20
int ia[NLEVEL];
int na[NLEVEL];
int iLevel = 0;
int choose(int n){
    if (ilevel >= ns){ na[ns]=n; ia[ns]=0; ns++; }
    return ia[ilevel++];
}
void step(){
    while (ns > 0){
        if (++ia[ns-1] >= na[ns-1]) ns--;
        else break;
    }
}
bool search(int iLevel){
    iLevel++;
    switch(choose(2)){
    break; case 0:;
        // see if 0 is a win. if not, fail by returning false
    break; case 1:
        // choose move 1 and recur
        return search(iLevel);
    }
    return true;
}
// this is the "top level" routine
void running(){
    ns = 0;
    // repeat for stabs into choice tree until success
    do {
        bool bSuccess = search(0);
        if (bSuccess){
            // Yay!
            break;
        }
        step(); // this advances the stack of choices
    } while(ns > 0); // stop when success or there are no more choices
}

Я использовал этот код для создания собственного средства доказательства теорем вместо подпрограммы search.

Рекурсия –

• Проблема может быть разбита на более мелкие проблемы того же типа.
• Требуется базовый вариант

Возврат –

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

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

Например, обратный LinkedList с использованием рекурсии просто добавляет головной узел к уже обращенному подсписку.https://leetcode.com/problems/reverse-linked-list/discuss/386764/Java-recursive

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