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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
class BinaryTree { BinaryTree left; BinaryTree right; String name; boolean data; public BinaryTree(BinaryTree left, BinaryTree right, String name, boolean data) { this.left = left; this.right = right; this.name = name; } static BinaryTree maketree() { BinaryTree e = new BinaryTree(null, null, "E", false); BinaryTree d = new BinaryTree(null, null, "D", false); BinaryTree b = new BinaryTree(d, e, "B", false); BinaryTree f = new BinaryTree(null, null, "F", false); BinaryTree g = new BinaryTree(null, null, "G", true); BinaryTree c = new BinaryTree(f, g, "C", false); BinaryTree root = new BinaryTree(b, c, "A", false); return root; } static boolean findSolution(BinaryTree tree) { if (tree == null) return false; if (tree.data) return true; return findSolution(tree.left) || findSolution(tree.right); } public static void main(String[] args) { BinaryTree node = maketree(); System.out.println(findSolution(node)); } } |

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.

1 2 3 4 5 6 |
int fact(int n) { int result; if(n==1) return 1; result = fact(n-1) * n; return result; } |