Recursive Search with BacktrackingCS 311 Data Structures and AlgorithmsLecture SlidesFriday, October 2, 2009Glenn G. ChappellDepartment of Computer ScienceUniversity of Alaska [email protected]© 2005–2009 Glenn G. Chappell2 Oct 2009 CS 311 Fall 2009 2Unit OverviewRecursion & SearchingMajor Topics Introduction to Recursion Search Algorithms Recursion vs. Iteration Eliminating Recursion Recursive Search with Backtracking2 Oct 2009 CS 311 Fall 2009 3ReviewRecursion vs. Iteration [1/3]Five Fibonacci number computation programs. fibo1.cpp: Recursive.Uses “obvious” algorithm. fibo2.cpp: Iterative. fibo3.cpp: Inspired by previous. Recursive. Returns 2 values, instead of 1. Added wrapper. fibo4.cpp: Recursive memoizing.  Memoizing (which we do not really cover) is saving values of a function, to be returnedwhen it is called with the same parameters. A special case of caching. fibo5.cpp: Uses a formula.Very slow.Also much faster.Much faster.Wow!Recursion is a lot slower than iteration!Wrong! Wrong, wrong, wrong, wrong, wrong, wrong.You’re wrong.2 Oct 2009 CS 311 Fall 2009 4ReviewRecursion vs. Iteration [2/3]Choice of algorithm can make a huge difference in performance.As we will see, data structures can make a similar difference.F5F1F2F0F1F2F0F1F3F1F2F0F1F4F2F0F1F3F1F0F1F6F5& F6F6F4& F5F3& F4F2& F3F1& F2F0& F1F-1& F0In fibo1.cpp In fibo3.cppRecursive calls made to compute F6.F3F4F2White boxes represent calls not made in fibo4.cpp.2 Oct 2009 CS 311 Fall 2009 5ReviewRecursion vs. Iteration [3/3]Two factors can make recursive algorithms inefficient. Inherent inefficiency of some recursive algorithms However, there are efficient recursive algorithms (fibo3.cpp). Function-call overhead Making all those function calls requires work: saving return addresses, creating and destroying automatic variables.And recursion has another problem. Memory-management issues Memory for automatic variables is allocated ina way that does not allow for normal errorhandling. Making too many recursive calls willcause stack overflow (resulting in a crash — or worse). When we use iteration, we can manage memory ourselves. This is more work, but it also allows us to handle errors properly.These two are important regardless of the recursive algorithm used.2 Oct 2009 CS 311 Fall 2009 6ReviewEliminating RecursionEvery recursive function can be rewritten as an iterative function that uses essentially the same algorithm. The system helps you do recursion by providing a Stack, used to hold return addresses for function calls, and values of automatic local variables. We can eliminate recursion (convert it to iteration) by mimicking the system’s method of handling recursive calls using Stack frames. This “brute force” method is primarily of theoretical interest. When eliminating recursion, it is usually better to do some thinking. We will look at this method again when we study Stacks.Tail recursion is when the recursive call is the last operation a function does. Tail recursion is easy to eliminate. Some compilers (not C++) do this automatically: tail call optimization.2 Oct 2009 CS 311 Fall 2009 7Recursive Search with BacktrackingIntroduction — BacktrackingIn most of the programming you have done, you have probably proceeded directly toward our goal. Work never had to be undone. But what if it does …Sometimes we search for a solution to a problem. When we search for solutions, we may hit “dead ends” that do notwork. Then we need to restore the program to a previous state. This iscalled backtracking.Recursion is often a convenient technique for search with backtracking. However, such recursive programming can require rather differentways of thinking from “normal” recursive programming.2 Oct 2009 CS 311 Fall 2009 8Recursive Search with BacktrackingIntroduction — Partial SolutionsRecursive solution search works well when we have a notion of a partial solution. Each recursive call says, “Look for full solutions based on this partial solution.” The function attempts to build more complete solutions based on the partial solution it was given. For each possible more complete solution, a recursive call is made. We usually have a wrapper function, so that the client does not need to deal with partial solutions.In a recursive solution search, to backtrack, we often simply return from a function.2 Oct 2009 CS 311 Fall 2009 9Recursive Search with BacktrackingIntroduction — No-Backtracking DiagramIn the recursion we studied earlier: A recursive call is a request for information (or action). The return sends the information back (if any).The diagram below shows the information flow in the first version of fibo.fibo(3)fibo(1)ClientF3=? F3=2F1=?F1=1fibo(2)F2=?F2=1fibo(0)F0=?F0=0fibo(1)F1=?F1=1GoalQ: What is F3?A: F3= 2.2 Oct 2009 CS 311 Fall 2009 10Recursive Search with BacktrackingPrinting Solutions — DiagramIn recursive search with backtracking: A recursive call means “continue with the proposed partial solution”. The return means “backtrack”.The diagram below illustrates a search for 3-digit sequences with digits in {0, 1}, in which no two consecutive digits are the same.On finding a solution, we can stop. Or continue, finding all solutions.0,0 okay?No.<empty> okay?Yes. Continue.0,1,0 okay?Yes. OUTPUT.0,1 okay?Yes. Continue.0 okay?Yes. Continue.1 okay?Yes. Continue.0,1,1 okay?No.1,0 okay?Yes. Continue.1,1 okay?No.1,0,0 okay?No.1,0,1 okay?Yes. OUTPUT.Add 0 Add 1Add 0 Add 1 Add 0 Add 1Add 0 Add 1Add 0 Add 1GoalRecursive calls handle partial solutions2 Oct 2009 CS 311 Fall 2009 11Recursive Search with BacktrackingPrinting Solutions — n-Queens ProblemWe now look at how to solve the n-Queens Problem. Place n queens on an n × n chessboard so that none of them can attack each other.QQQQQQQQQQQGood Good BADQQQQ4×4 chessboardQueenCan attackN, S, E, W& 4 diagonals,any distanceQ2 Oct 2009 CS 311 Fall 2009 12Recursive Search with BacktrackingPrinting Solutions — How to Do It [1/4]To Figure Out What is a partial solution for the problem we wish to solve? How should we represent a partial solution? If possible, we should represent a partial solution in a way that makes it convenient to determine whether we have a full solution. It is also nice if we can quickly determine whether we have a dead end. How should we output a full solution?2 Oct 2009