backtracking backtracking is form of recursion that is particularly useful for types of problems such as traversing tree structureswhere we are presented with number of options at each nodefrom which we must choose one subsequently we are presented with different set of optionsand depending on the series of choices made either goal state or dead end is reached if it is the latterwe must backtrack to previous node and traverse different branch backtracking is divide and conquer method for exhaustive search importantly backtracking prunes branches that cannot give result an example of back tracking is given in the following example herewe have used recursive approach to generating all the possible permutations of given stringsof given length ndef bitstr(ns)if = return return digit bits for digit in bitstr( , )for bits in bitstr( , )print (bitstr( ,'abc')this generates the following outputnotice the double list compression and the two recursive calls within this comprehension this recursively concatenates each element of the initial sequencereturned when with each element of the string generated in the previous recursive call in this sense it is backtracking to uncover previously ingenerated combinations the final string that is returned is all letter combinations of the initial string divide and conquer long multiplication for recursion to be more than just clever trickwe need to understand how to compare it to other approachessuch as iterationand to understand when its use will lead to faster algorithm an iterative algorithm that we are all familiar with is the procedure we learned in primary math classesused to multiply two large numbers that islong multiplication if you rememberlong multiplication involved iterative multiplying and carry operations followed by shifting and addition operation