BackTracking and Recursion

In this tutorial i am going to show the difference between recursion and backtracking .

Backtracking is general algorithm for finding solution to some computational problem. We have set of several choices. If one choice from set of choices proves incorrect, computation backtracks or restarts at the point of choice and tries another choice.

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

Lets take an example.

At first we make a simple tree with all its left and right nodes and having parent node ‘A’. Here we have set of possible nodes and we have to find that particular node which has true value. So we recursively check whether this tree has that particular node or not.

Recursion function calls itself until reaches a base case.Simple example like we are finding the factorial of a number.In recursion solution depends on smaller instances of that problem. It must have a base case to stop the recursion.It make stack of each method call.

 

Please follow and like us:

Post Author: Ambrish Rajput

Leave a Reply

Your email address will not be published. Required fields are marked *