© 2006 Pearson Addison-Wesley. All rights reserved 6-1Chapter 6Recursion as a Problem-Solving TechniqueCS102 Sections 51 and 52Marc Smith and Jim Ten EyckSpring 2008© 2006 Pearson Addison-Wesley. All rights reserved 6-2Backtracking• Backtracking– A strategy for guessing at a solution andbacking up when an impasse is reached• Recursion and backtracking can becombined to solve problems© 2006 Pearson Addison-Wesley. All rights reserved 6-3The Eight Queens Problem• Problem– Place eight queens on the chessboard so that noqueen can attack any other queen• Strategy: guess at a solution– There are 4,426,165,368 ways to arrange 8queens on a chessboard of 64 squares© 2006 Pearson Addison-Wesley. All rights reserved 6-4The Eight Queens Problem• An observation that eliminates many arrangementsfrom consideration– No queen can reside in a row or a column that containsanother queen• Now: only 40,320 arrangements of queens to bechecked for attacks along diagonals© 2006 Pearson Addison-Wesley. All rights reserved 6-5The Eight Queens Problem• Providing organization for the guessing strategy– Place queens one column at a time– If you reach an impasse, backtrack to the previouscolumn© 2006 Pearson Addison-Wesley. All rights reserved 6-6The Eight Queens ProblemFigure 6-1Figure 6-1a) Five queens that cannot attack each other, but that can attack all ofcolumn 6; b) backtracking to column 5 to try another square for the queen;c) backtracking to column 4 to try another square for the queen and then consideringcolumn 5 again© 2006 Pearson Addison-Wesley. All rights reserved 6-7The Eight Queens Problem• A recursive algorithm that places a queen in acolumn– Base case• If there are no more columns to consider– You are finished– Recursive step• If you successfully place a queen in the current column– Consider the next column• If you cannot place a queen in the current column– You need to backtrack© 2006 Pearson Addison-Wesley. All rights reserved 6-8The Eight Queens ProblemFigure 6-2Figure 6-2A solution to the Eight Queensproblem© 2006 Pearson Addison-Wesley. All rights reserved 6-9Defining Languages• A language– A set of strings of symbols– Examples: English, Java– If a Java program is one long string of characters, thelanguage JavaPrograms is defined asJavaPrograms = {strings w : w is a syntactically correctJava program}© 2006 Pearson Addison-Wesley. All rights reserved 6-10Defining Languages• A language does not have to be a programming ora communication language– Example• The set of algebraic expressionsAlgebraicExpressions = {w : w is an algebraicexpression}© 2006 Pearson Addison-Wesley. All rights reserved 6-11Defining Languages• Grammar– States the rules for forming the strings in a language• Benefit of recursive grammars– Ease of writing a recognition algorithm for thelanguage• A recognition algorithm determines whether a givenstring is in the language© 2006 Pearson Addison-Wesley. All rights reserved 6-12The Basics of Grammars• Symbols used in grammars– x | y means x or y– x y means x followed by y(In x • y, the symbol • means concatenate, or append)– < word > means any instance of word that the definitiondefines© 2006 Pearson Addison-Wesley. All rights reserved 6-13The Basics of Grammars• Java identifiers– A Java identifier begins with a letter and is followed byzero or more letters and digitsFigure 6-3Figure 6-3A syntax diagram for Java identifiers© 2006 Pearson Addison-Wesley. All rights reserved 6-14The Basics of Grammars• Java identifiers– LanguageJavaIds = {w : w is a legal Java identifier}– Grammar< identifier > = < letter > | < identifier > < letter > | <identifier > < digit>< letter > = a | b | … | z | A | B | …| Z | _ | $< digit > = 0 | 1 | … | 9© 2006 Pearson Addison-Wesley. All rights reserved 6-15The Basics of Grammars• Recognition algorithmisId(w)if (w is of length 1) {if (w is a letter) { return true}else { return false}}else if (the last character of w is a letter or a digit) {return isId(w minus its last character)}else { return false}© 2006 Pearson Addison-Wesley. All rights reserved 6-16Two Simple Languages:Palindromes• A string that reads the same from left to right as itdoes from right to left• Examples: radar, deed• LanguagePalindromes = {w : w reads the same left to right as right to left}© 2006 Pearson Addison-Wesley. All rights reserved 6-17Palindromes• Grammar< pal > = empty string | < ch > | a < pal > a | b < pal > b | …| Z < pal > Z< ch > = a | b | … | z | A | B | … | Z© 2006 Pearson Addison-Wesley. All rights reserved 6-18Palindromes• Recognition algorithmisPal(w)if (w is the empty string or w is of length 1) {return true}else if (w’s first and last characters are the same letter ) {return isPal(w minus its first and last characters)}else {return false}© 2006 Pearson Addison-Wesley. All rights reserved 6-19Strings of the form AnBn• AnBn– The string that consists of n consecutive A’s followedby n consecutive B’s• LanguageL = {w : w is of the form AnBn for some n ! 0}• Grammar< legal-word > = empty string | A < legal-word > B© 2006 Pearson Addison-Wesley. All rights reserved 6-20Strings of the form AnBn• Recognition algorithmisAnBn(w)if (the length of w is zero) {return true}else if (w begins with the character A and endswith the character B) {return isAnBn(w minus its first and last characters)}else {return false}© 2006 Pearson Addison-Wesley. All rights reserved 6-21Algebraic Expressions• Three languages for algebraic expressions– Infix expressions• An operator appears between its operands• Example: a + b– Prefix expressions• An operator appears before its operands• Example: + a b– Postfix expressions• An operator appears after its operands• Example: a b +© 2006 Pearson Addison-Wesley. All rights reserved 6-22Algebraic Expressions• To convert a fully parenthesized infix expressionto a prefix form– Move each operator to the position marked by itscorresponding open parenthesis– Remove the parentheses– Example• Infix expression: ((a + b) * c• Prefix expression: * + a b c© 2006 Pearson Addison-Wesley. All rights reserved 6-23Algebraic Expressions• To convert a fully parenthesized infix expressionto a postfix form– Move each operator to the position marked by itscorresponding closing parenthesis– Remove the parentheses– Example• Infix form: ((a + b) * c)• Postfix form: