Lets see some basics about Recursion and Backtracking,
What is Recursion ?
Any fuction which calls itself called recursive. A recursive method solves a problem by calling a replica of itself to work on small problem. This is called as recursion step. The recursion step can cause such recursive calls.
It is important to determine that the recursion terminates. The series of smaller problems must eventually converage on the base case.
Recursion is a useful technique borrow from mathematics. Recursive code is shorter and easier to write compared to iterative code. Generally, loops are turn into recursive functions when they are compile or interpret. Recursion is the most useful for tasks that can be define in terms of similar subtasks.
What is Backtracking ?
Backtracking is an progress of the brute force approach. It searches for a solution to a problem among all available options. In backtracking, we start with one possible option out of other options. Then try to solve the problem if we are able to solve the problem with thw selected to move then we will print the solution else we will backtrack and select other option and try to solve it. If none if the options work out we will claim that there is no solution for the problem.
Backtracking is a form of recursion. The ususal scenario is that you are face with a number of options, and you must choose one of these. After you make your choice you will get a new set of options and set of options you get depends on what choice you make. This procedure is repeated until you reach a final state. If you made a good sequence of choices, your final state is goal state.
Example Algorithms of Recursion : –
- Fibonacci series, Factorial finding
- Merge sort, Quick sort
- Binary Search
- Tree Traversal and many Tree problems: InOrder, PreOrder, PostOrder
- Graph Traversals: DFS and BFS
- Dynamic Programming Examples
- Divide and Conquer Algorithms
- Towers of Hanoi
Example Algorithms of Backtracking : –
- Binary Strings: generating all binary strings
- Generating k -ary strings
- N-Queens Problem
- The Knapsack Problem
- Generalized Strings
- Hamiltonian Cycles
- Graph Coloring Problem
