Difference between Backtracking and Recursion

What is Backtracking?

Backtracking is a process that helps to solve the problem recursively. In other words, backtracking is an algorithm that solves the problem. It uses a recursive function to find the solution to the given problem. It divides the process into smaller units and after that solves the problem one at a time and gives the solution.

With the help of backtracking, we can write the algorithm after that we can search for the solution for the given problem and try to make all possible outcomes, and give back the best solution from all the desired solutions.

Basically, this type of rule follows dynamic programming, but as we all know dynamic programming is used to find the solution to optimization problems. On the other hand, backtracking is not used for finding the solution to optimization problems. It is used for finding the best solution from the multiple solutions we get after using backtracking.

It is applied to some specific types of problems as follows:

Decision problems: In this type of problem, we find a reasonable solution to the problems.

Optimization problems: In this type of problem, we find the best and most reasonable solution to the problem that can be applied.

Enumeration problems: In this type of problem, we find all the reasonable solutions to the problems

In the backtracking algorithm, we try to find the sequence of the solution so we can set the best path which has some small checkpoints from where the problem we can backtrack if we don’t find a reasonable solution for the problem.

When to use backtracking?

When we have multiple solutions for a specific problem, we use a backtracking algorithm to find the best solution from the available choices.

There are some cases in which we need to use backtracking algorithms:

If we need some information that is not present in the database to make the best choice then we use a backtracking algorithm to try all the available solutions.
If each decision is leading to new choices then we need to backtrack to make new decisions. In these cases, we need to use backtracking algorithms.

How do backtracking algorithms work?

As we all know, Backtracking is a technique that works systematically to find the best solution and try out various sequences of solutions until finding the best solution for the problem.

Let's take an example to understand backtracking:

Backtracking always starts with a new node also known as the start node. First, we move to node 1. If 1 node is not a reasonable solution, so we move to the second node of the data, in this case, it is 2. If 2 is also not a feasible solution and it is also a dead end so now, we backtrack from node 2 to node 1.

Now, suppose we have a path that exists from node 1 to node 3. So now we move from node 1 to node 3. But node 3 is also a dead end. Again backtrack from node 3 to node 1. Now, we move from node 1 to starting node.

Now, we will check if there are any new paths to continue from the starting point. Now, we move from the starting point to node 4. Since node 4 is also not a reasonable solution so we move to the next node that is node 5. Node 5 is a success node.

Some related terms used in backtracking:

Live node: The nodes that can be further generated are known as the live nodes.

E node: E nodes are nodes whose children are generated,, and after generation, they become the success node.

Success node: If a specific node gives a reasonable solution or we can say a feasible solution then it is called a success node.

Dead node: If a node cannot give a feasible solution or node which cannot be further generated is known as a dead node.

With the help of backtracking, we can solve multiple problems, and those problems can satisfy a complex set of constraints.

There are two types of constraints in backtracking:

Implicit constraints: It is a rule that tells how each element in a tuple is related to each other.

Explicit constraints: It is a rule that helps to restrict elements to be chosen from the given set.

What is recursion?

Recursion is a process in which it calls itself to work on a smaller problem. Or we can say that recursion is a process in which a function calls a copy of itself and works on a sub-problem of the actual problem.

Any function which calls itself is called a recursive function, and this type of function calls is known as a recursive calls. With the use of a recursive algorithm, we can solve many problems easily without any problems.

For example, the tower of Hanoi, traversal of the tree (pre-order, post-order, in order), etc.

Why do we need recursion?

As we all know, recursion is a very good technique that helps us to reduce the length and complexity of our code so we can easily write and read the code. Recursion has an advantage over other techniques. With the help of recursion, we can create a function that can call itself until we get the desired solution we want.

How does recursion works?

Recursion is used to perform several repetitive calls to the function within the function. With the help of a recursive condition, we can perform repetitive calls to the function until we get the desired solution or we can say that until we match the base case condition. The base case is present inside the function and we can stop the execution after we satisfied the base case condition.

Let's understand recursion by an example:

Example 1: A program to find factorial in C++ using recursion

/* C++ program to find
factorial of given number*/
#include <iostream>
using namespace std;
/* Function to find factorial
of given number*/
unsigned int factorial(unsigned int n)
{
if (n == 0 || n == 1)
return 1;
return n * factorial(n - 1);
}
// main function
int main()
{
int num;
cout<<"enter the number for factorial: ";
cin>>num;
cout<< "Factorial of "
<<num<< " is " << factorial(num) <<endl;
return 0;
}

Output:

enter the number for factorial: 5
Factorial of 5 is 120

Now let us understand this example:

Factorial of 5:
Return 5*factorial(4) = 120
Return 4*factorial(3) = 24
Return 3*factorial(2) = 6
Return 2*factorial(1) = 2
Return 1*factorial(0) =1

In this example, we have a factorial function that is performing many repetitive calls to the function. The recursive condition should be n*factorial(n-1); in the function name and as we all know the value of n is 5.

5*factorial(4);
5*4*factorial(3);
5*4*3*factorial(2);
5*4*3*2*factorial(1);
5*4*3*2*1*factorial(0);

As we can see in this function, first we multiplied 5 with factorial(5-1) and after that 4 is passed to the function. Similarly, in the next iteration, we multiplied 4 with factorial (3-1). And this process will continue till the value of n becomes 1.

Here, two ways execution can be performed:

Top to down

Cout<<n;
Function(n-1);

In this approach, printing will happen before the execution of the recursive call.

Bottom to up

Function(n-1)
Cout<<n;

In this approach, printing happens after the execution of the recursive call.

Types of Recursion

Direct recursion
Indirect recursion

Direct recursion

As the name says, this type of recursion function calls itself directly.

void direct()
{
//code
direct();
}

Indirect recursion

As the name says, this type of recursion function calls itself indirectly from another function. That is why it is called indirect recursion.

voidindirect()
{
//code
func();
}
Void func()
{
//code
Indirect();
}