Difference between backtracking and recursion?

Question

What is the difference between backtracking and recursion? How is this program working?

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.
    }
}

Chantay

I think you'd better make your question a bit more clear. ar isn't even defined in the code you supply. – Militant

great question! recursion as you show it, serves as implementation mechanism for full enumeration of all possible results; instead of just printing at the base case, add a test, a conditional printing for when the test is passed, and optional bail-out, and you've got yourself a mini-Prolog for a specific problem baked in. – Cattleya

Answer 1

That question is like asking what's the difference between a car and a DeLorean.

In recursion function calls itself until reaches a base case.

In backtracking you use recursion in order to explore all the possibilities until you get the best result for the problem.

Can be a bit hard to understand, I attach some text from here:

"Conceptually, you start at the root of a tree; the tree probably has some good leaves and some bad leaves, though it may be that the leaves are all good or all bad. You want to get to a good leaf. At each node, beginning with the root, you choose one of its children to move to, and you keep this up until you get to a leaf.

Suppose you get to a bad leaf. You can backtrack to continue the search for a good leaf by revoking your most recent choice, and trying out the next option in that set of options. If you run out of options, revoke the choice that got you here, and try another choice at that node. If you end up at the root with no options left, there are no good leaves to be found."

This needs an example:

Your piece of code is simply recursion, as you never get back if the result doesn't fit your goal.

Biagi

no, OP code does get back after the first attempt of ar[n-1]='0'; and undoes it to ar[n-1]='1'; and then goes forth again, with the new choice. as to your picture, there can be more than one good leaf in the tree, in particular each leaf can be good, as well. backtracking enumerates all good leaves by enumerating and testing all nodes/leaves, and if every node/leaf is good then all leaves will be reported/collected/produced in the end. which is the case with the OP code. – Cattleya

Backtracking doesn't have to use recursion actually - all it means is revisiting a decision point you took before, and taking new information (the path you took) into consideration. – Serin

Really, recursion is just one way to implement recursion. Backtracking is a more general idea from the area of exact algorithms. It should be noted that what you have mentioned is called Chronological Backtracking, which is just one of the variants of the algorithm. You can also check out BJ, CBJ, FC, MFC, among others. – Laresa

Answer 2

Recursion describes the calling of the same function that you are in. The typical example of a recursive function is the factorial, i.e. something like

int fact(int n) {
    int result;
    if(n==1) return 1;
    result = fact(n-1) * n;
    return result;
}

What you see here is that fact calls itself. This is what is called recursion. You always need a condition that makes recursion stop. Here it is if(n==1) combined with the fact that n will always decrease each time it is called (fact(n-1))

Backtracking is an algorithm that tries to find a solution given parameters. It builds candidates for the solution and abandons those which cannot fulfill the conditions. A typical example for a task to solve would be the Eight Queens Puzzle. Backtracking is also commonly used within Neuronal Networks.

The program you described uses recursion. Similar to the factorial function, it decreases the argument by 1 and ends if n<1 (because then it will print ar instead of doing the rest).

Disseminule

no, the OP program decreases the argument, proceeds with that value, then goes back, changes the ar[n-1] to '1' and goes forth with that same (n-1) value again. – Cattleya

Answer 3

recursion - no values abandoned;

backtracking - abandon some solution candidates;

also note that backtracking will call itself more than once in the body of function, while it's not normally true for recursion

Interconnect

there's no requirement to abandon some solutions. if every enumerated solution is good, then so be it. it's still a backtracking. similarly, if after going back the program sees there's no more choices to make, it just returns from that level, so it doesn't matter if that was the first and only choice or there were more choices. a list is a degenerate tree, but it's still a tree. :) – Cattleya

This is so not true, everything you mentioned can be part of a recursion. – Yip

Answer 4

In my understanding, backtracking is an algorithm, like all the other algorithms, like BFS and DFS, but recursion and also iteration are methods, they are at a higher level than the algorithms, for example, to implement a DFS, you can use recursion, which is quite intuitive, but you can also use iteration with a stack, or you can also think recursion and iteration are just methods to support your algorithms.

Shute

Answer 5

Recursion is like a bottom-up process. You can solve the problem just by using the result of the sub-problem.

For example, reverse LinkedList using recursion is just appending a head node on the already reversed sublist.https://leetcode.com/problems/reverse-linked-list/discuss/386764/Java-recursive

Backtracking is still like a top-down process. Sometimes you can't solve the problem just by using the result of the sub-problem, you need to pass the information you already got to the sub-problems. The answer(s) to this problem will be computed at the lowest level, and then these answer(s) will be passed back to the problem with the information you got along the way.

Eureetloir

"The answer(s) to this problem will be [produced] at the lowest level" is the most important distinction of backtracking from (structural/primitive) recursion, which builds up its result on the way from the bottom to the top where it is finally produced (at the top). General recursion OTOH, there's no knowing what that does. – Cattleya

Answer 6

Recursion is just like what you showed. If routine A calls A, or if A calls B and B calls A, that is recursion.

Backtrack is not an algorithm, it is a control structure. When using backtrack, a program appears to be able to run backward. This is useful when writing a program to play a game like chess, where you want to look ahead some number of moves. When the program wants to make a move, it picks a move, then switches to its mirror-image opponent program, which picks a move, and so on. If the initial program gets to a "good place" it wants to say "Yay" and carry out the first move it made. If either program gets to a "bad place" it wants to back out and try another move.

You could just think of this as searching a tree, but if the move choices are complicated it may be more intuitive to think of it as a program "backing up" to the last place it chose a move, choosing a different move, and running forward again.

OK, so if that idea has appeal, how do you do it? First, you need a kind of statement representing a choice, where a move is chosen, that you can "back up" to and revise your choice. Second, whenever you have a sequence of statements like A;B, you make A a function, and you pass to it a function capable of executing B. Something like A(lambda()B(...)). So when A is finished executing, before returning it calls its argument that executes B. If A wants to "fail" and start "running backward" it simply returns without calling the function that calls B. I know this is hard to follow. I've done it via macros in LISP, and it works well. To do it in a normal compiler language like C++ is incredibly hairy.

I have done something like it in C/C++ in a way that preserves the "prettiness" but doesn't actually run backwards. The idea is you're doing this to perform some kind of depth-first tree search. But you could do it instead as a series of "stabs" down from the root of the tree, following a different path each time you "stab". This might be objected to on performance grounds, but it doesn't actually cost that much more, since the bulk of the work happens in the leaves of the tree. If the tree is 3 layers deep and has a branching factor of 5 at each node, that means it has 5 + 25 + 125 or 155 nodes. But in a series of "stabs" from the root, it visits 125 * 3 = 375 nodes, a performance penalty of less than 3x, which can be quite tolerable unless performance is really a problem. (Remember that real backtrack can involve quite a bit of machinery, making lambdas and so on.)

Here's the basic code I did it with:

#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
}

I've used this code to build a home-grown theorem prover in place of the search routine.

Rutheruthenia

Answer 7

Recursion -

• The problem can be broken down into smaller problems of same type.
• Base case is required

Backtracking -

• General algorithmic technique that takes in all the possible combination to solve a computational problem.

Convivial

Answer 8

First understand what backtracking is:

Backtracking is an approach to solve problems which involves exploring all the paths.

The Approach

Suppose we have a problem and then we have multiple options available to proceed to the solution. Given that one or more (possibly zero) options can lead to the full solution. Then we just explore all the options available one by one.

Note that after exploring one option, if we didn't find any solution or in case we want multiple solutions, we go back to the same previous state (the backtracking step) and explore other options available.

Now this approach can be implemented iteratively or recursively.

So keeping it simple, Backtracking is an approach which can be implemented using recursive algorithms.

Herwin

Answer 9

Recursion typically follow a top-down approach, breaking down the problem into smaller manageable subproblems until reaching the base case, and then combining the results to obtain the final solution. It starts from the top and works its way down to the base case.

On the other hand, backtracking often follow a systematic approach. They explore the solution space incrementally, trying out different options at each step. If they reach an invalid or unsatisfactory state, they backtrack and explore alternative choices. This process continues until a valid solution is found or all possibilities have been exhausted.

Backtracking algorithms can be seen as a way to systematically explore the solution space, testing different combinations and configurations by trying out options and backtracking when necessary. The key idea is to make a choice, explore its consequences, and if it leads to a dead end, undo the choice (backtrack) and try a different one.

Credit

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Lyall