數(shù)據(jù)結(jié)構(gòu)英文教學(xué)課件：Chapter 5 Recursion

1、Data StructureSoftware College Northeastern UniversityChapter 5Recursion Data StructureSoftware College Northeastern UniversityOverview Recursive Solutions Mathemetical Induction Recursive Definitions Stack Activation Frames Recursive and Iteration divide and conquer & backtrackingData StructureSoft

2、ware College Northeastern UniversityRecursive SolutionsSometimes, the best way to solve a problem is by solving a smaller version of the exact same problem firstRecursion is a technique that solves a problem by solving a smaller problem of the same type A procedure that is defined in terms of itself

3、Data StructureSoftware College Northeastern UniversityRecursionWhen you turn that into a program, you end up with functions that call themselves:Recursive FunctionsData StructureSoftware College Northeastern UniversityRecursive Functiona recursion function is a function that either directly or indir

4、ectly makes a call to itself. but we need to avoid making an infinite sequence of function calls (infinite recursion) int s (int n) if (n =1) return 1; else return s(n-1) + n;Data StructureSoftware College Northeastern UniversityFinding a Recursive Solutiona recursive solution to a problem must be w

5、ritten carefully the idea is for each successive recursive call to bring you one step closer to a situation in which the problem can easily be solved this easily solved situation is called the base case each recursive algorithm must have at least one base case, as well as a general (recursive) case

6、Data StructureSoftware College Northeastern UniversityMathemetical InductionTo proveLet p(n) denote the statement involving the integer variable n. The Principle of Mathematical Induction states: If p(1) is true and, for some integer K =1 , p(k+1) is true whenever p(k) is true then p(n) is true for

7、all n=1 . Data StructureSoftware College Northeastern UniversityMathemetical Induction4 steps in using Induction: Base cases; p(1), p(2), Induction hypothesis (IH); assume p(k) is true Statement to be proved in induction; it is true for p(k+1) Induction step. prove p(k+1) is true based on IHData Str

8、uctureSoftware College Northeastern UniversityA recursive definitionint s (int n) if (n =1) return 1; else return s(n-1) + n;A few of problems: n 0 at the beginning; return value might be too large to fit in an int.Data StructureSoftware College Northeastern UniversityPrinting number in Any Basecons

9、t char * DIGIT_TABLE = 0123456789abcdef; const int MAX_BASE = strlen(DIGIT_TABLE); void printIntRec( int n, int base ) if( n = base ) printIntRec( n / base, base ); cout 16: out of bound; if base = 0: division by 0; if base = 1: infinite loop.Data StructureSoftware College Northeastern UniversityGen

10、eral format for Many Recursive Functions if (some easily-solved condition) / base case solution statement else / general case recursive function call Data StructureSoftware College Northeastern UniversityRecursion does not terminate properly: Stack Overflow !Common Programming ErrorData StructureSof

11、tware College Northeastern UniversityWhen a function is called.A transfer of control occurs from the calling block to the code of the function -It is necessary that there be a return to the correct place in the calling block after the function code is executed; This correct place is called the retur

12、n address When any function is called, the run-time stack is used -On this stack is placed an activation record for the function callData StructureSoftware College Northeastern UniversityStack Activation FramesThe activation record contains the return address for this function call, and also the par

13、ameters, and local variables, and space for the functions return value, if non-void The activation record for a particular function call is popped off the run-time stack when the final closing brace in the function code is reached, or when a return statement is reached in the function codeAt this ti

14、me the functions return value, if non-void, is brought back to the calling block return address for use there Data StructureSoftware College Northeastern UniversityA Stake of Activation RecordsS(1)S(2)S(3)S(4)Main()int s (int n) if (n =1) return 1; else return s(n-1) + n;void main() int sum; sum = s

15、(4); /instruction 100 printf(“sum=%d”,sum); return;Data StructureSoftware College Northeastern Universityint Func(/* in */ int a, /* in */int b ) int result; if ( b = 0 ) / base case result = 0; else if ( b 0 ) / first general case result = a + Func ( a , b - 1 ) ) ; / instruction 50 return result;

16、void main() int x; x = Func(5,2); /instruction 100 printf(“%dn”,x); return;A recursive functionData StructureSoftware College Northeastern University FCTVAL ? result ? b 2 a 5Return Address 100 Run-Time Stack Activation Recordsoriginal call at instruction 100 pushes on this record for Func(5,2)x = F

17、unc(5, 2);/ original call at instruction 100 Data StructureSoftware College Northeastern University FCTVAL ? result ? b 1 a 5Return Address 50 FCTVAL ? result 5+Func(5,1) = ? b 2 a 5Return Address 100record for Func(5,2)call in Func(5,2) codeat instruction 50 pushes on this recordfor Func(5,1) Run-T

18、ime Stack Activation Recordsx = Func(5, 2);/ original call at instruction 100 Data StructureSoftware College Northeastern University FCTVAL ? result ? b 0 a 5Return Address 50 FCTVAL ? result 5+Func(5,0) = ? b 1 a 5Return Address 50 FCTVAL ? result 5+Func(5,1) = ? b 2 a 5Return Address 100record for

19、 Func(5,2)record for Func(5,1)call in Func(5,1) codeat instruction 50pushes on this record for Func(5,0) Run-Time Stack Activation Recordsx = Func(5, 2);/ original call at instruction 100 Data StructureSoftware College Northeastern University FCTVAL 0 result 0 b 0 a 5Return Address 50 FCTVAL ? resul

20、t 5+Func(5,0) = ? b 1 a 5Return Address 50 FCTVAL ? result 5+Func(5,1) = ? b 2 a 5Return Address 100record for Func(5,0)is popped first with its FCTVALrecord for Func(5,2)record for Func(5,1) Run-Time Stack Activation Recordsx = Func(5, 2);/ original call at instruction 100 Data StructureSoftware Co

21、llege Northeastern Universityrecord for Func(5,2)record for Func(5,1)is popped nextwith its FCTVAL Run-Time Stack Activation Recordsx = Func(5, 2);/ original call at instruction 100 FCTVAL 5 result 5+Func(5,0) = 5+ 0 b 1 a 5Return Address 50 FCTVAL ? result 5+Func(5,1) = ? b 2 a 5Return Address 100D

22、ata StructureSoftware College Northeastern Universityx = Func(5, 2);/ original call at instruction 100 FCTVAL 10 result 5+Func(5,1) = 5+5 b 2 a 5Return Address 100record for Func(5,2)is popped lastwith its FCTVAL Run-Time Stack Activation RecordsData StructureSoftware College Northeastern University

23、Too much recursion Can Be DangerousFibonacci numbers.long fib (int n) if (n 1.We shall usually omit stating the base case when T(n) = O(1) for sufficiently small n, but only when it has no effect on the asymptotic solution to the recurrence. Master theorem can find a good upper bound on T(n).47Recur

24、sion treeSolve T(n) = 2T(n/2) + cn, where c 0 is constant.48Recursion treeSolve T(n) = 2T(n/2) + cn, where c 0 is constant.T(n)49Recursion treeSolve T(n) = 2T(n/2) + cn, where c 0 is constant.T(n/2)T(n/2)cn50Recursion treeSolve T(n) = 2T(n/2) + cn, where c 0 is T(n/4)T(n/4)T(n/4)T(n/4)cn/2cn/251Recu

25、rsion treeSolve T(n) = 2T(n/2) + cn, where c 0 is cn/4cn/4cn/4cn/4cn/2cn/2O(1)52Recursion treeSolve T(n) = 2T(n/2) + cn, where c 0 is cn/4cn/4cn/4cn/4cn/2cn/2O(1)h = lg n53Recursion treeSolve T(n) = 2T(n/2) + cn, where c 0 is cn/4cn/4cn/4cn/4cn/2cn/2O(1)h = lg ncn54Recursion treeSolve T(n) = 2T(n/2)

26、 + cn, where c 0 is cn/4cn/4cn/4cn/4cn/2cn/2O(1)h = lg ncncn55Recursion treeSolve T(n) = 2T(n/2) + cn, where c 0 is cn/4cn/4cn/4cn/4cn/2cn/2O(1)h = lg ncncncn56Recursion treeSolve T(n) = 2T(n/2) + cn, where c 0 is cn/4cn/4cn/4cn/4cn/2cn/2O(1)h = lg ncncncn#leaves = nO(n)57Recursion treeSolve T(n) =

27、2T(n/2) + cn, where c 0 is cn/4cn/4cn/4cn/4cn/2cn/2O(1)h = lg ncncncn#leaves = nO(n)Total = Q(n lg n)Data StructureSoftware College Northeastern University/zona/mmts/geometrySection/fractals/tree/treeFractal.htmlExamples: Fractal TreeData StructureSoftware College Northeastern UniversityBacktracking

28、 If we want to find (a) specific path in a search tree, we may use backtracking, i.e.going deep down into the tree until we either find a solution or understand that there cannot be a solution with this path and (in the latter case)go back (track back) in order to try another path.Data StructureSoft

29、ware College Northeastern UniversityBacktracking (cont.)Backtracking is a solution strategy that may be implemented using recursion and a sequence of guesses that ultimately lead to a solution.If a particular guess leads to an impasse (no solution), we retrace our steps in reverse order to replace o

30、ur last guess with another option, try to complete the solution again.Problem statementsProblem：A solution to the problem can be represented by n- turple (x1,xn), where xi comes from a limited set SiSolution space：X= (x1,xn)| xi Si the number of possible elements (size ) is m=m1m2mnNot all x X is th

31、e solution to the problemConstrains: g(x)=true Existence：Feasible Solution Optimization: target function maxf(x)Optimal Solution x0 st f(x0)=maxf(x)How to get the feasible /optimal solution from SS?Define solution space（1）Eight queens puzzleThe queens must be placed in such a way that no two queens

32、would be able to attack each other. The solution can be represented by 8- turple (x1,x8) where xi is the column number of queen iThe size of SS is 88Constrain xixj |xi-xj| j-i | for all i, j QQQQQQQQ123456781 2 3 4 5 6 7 888 chessboardDefine solution space （2）Subset sum problemA pair (S, M), where S

33、 is a set w1, w2, ., wn of positive integers and M is a positive integer. Exists there a subset of S that adds up exactly to the target value M? Solution space represented by A vector with the index of wiA n-turple (x1,xn)n=4, M=31, W=(11,13,24,7) (11,13,7) and（24,7）(1,2,4) and (3,4)(1,1,0,1) and (0

34、,0,1,1)Organize the solution spaceThe principle for model selection：Depending on the definition of SS Benefiting for searching the solutions Two models：Tree Graph Tree model is commonly used because it is helpful To enumerate the components of a turple To design the searching algorithmTo use the bou

35、nding functionsState space treeProblem state: each node in the treeState space: all paths from root to a node in the treeSolution state: a path from root to current node Answer state: a path satisfying constrains State space tree is the tree organization of the solution spaceMarking a node k using a

36、 path from root to k (x(1),x(k)SST for 4 queens puzzleThe node number is encoded by the order of DFS The edge is marked by the values of xi. . This tree is also called Permutation Tree. A solution is defined by the path from root to leaf. SST for subset sum (1) Represented by a vector with the index

37、 of win=4, M=31, W=(11,13,24,7)SST for subset sum (2) Represented by n-turplen=4, M=31, W=(11,13,24,7)SST ( an example of 0/1 knapsack) n=3，w= 20 , 15 , 15 ，p= 40 , 25 , 25 , c= 30。TSPSST of TSPSearching solution space: searching methods Searching solutions equals to traverse the state space treeNod

38、e states during expending a treeLive node： A node that has been reached, but not all of its children have been exploredDied node： A node where all of its children have been exploredE-Node (expansion node)： A live node in which its children are currently being explored.Searching solution space: searc

39、hing methods Depth First Search: DFSA node has one/more chance(s) to be a E-NodeBacktrack: A variant version of DFS with a bound functionBreadth-first searchA node has only one chance to be a E-NodeLive nodes are stored in a listBranch-bound: A variant version of BFS with a bound functionBest first

40、search Explores a tree by expanding the most promising node chosen according to a specified rule.BoundingA boolean function to kill a live nodeBi(x1,x2,xi)=true iff (x1,x2,xi) is impossible to be expended to an answer nodeBounding function:Obtained by some heuristics from constrains Must be simple D

41、ata StructureSoftware College Northeastern UniversityExamples: The 8 Queens Problemhttp:/mossie.cs.und.ac.za/murrellh/javademos/queens/queens.htmlEight queens are to be placed on a chess board in such a way that no queen checks against any other queenData StructureSoftware College Northeastern Unive

42、rsityTraversing a Maze Data StructureSoftware College Northeastern UniversityTraversing a Maze Data StructureSoftware College Northeastern UniversityEntrance exitTraversing a Maze Data StructureSoftware College Northeastern University樹Data StructureSoftware College Northeastern UniversityBacktrackin

43、g (cont.)Solution Search Space is a tree Each inner node is a set of alternatives that may lead to a solution. Each leaf is either a solution or no solution. We search this solution search space using recursion and backtracking to find a solution.ABDCGHEFIJKData StructureSoftware College Northeaster

44、n UniversityGenerating the candidatesClassic backtrack algorithm:At decision point, do something new (extend something that hasnt been added to this sequence at this place before.)Fail: Backtrack: Undo most recent decision (retract). l: Succeed:doneData StructureSoftware College Northeastern Univers

45、ity8-queens problemData StructureSoftware College Northeastern UniversityFacts8-queens has more than 281,474,976,711,000 candidatesPrune: reject nonviable candidates early, not just when sequence is complete.Example: 8-queens with pruning looks at about 16,000 partial and complete candidates12 solut

46、ions( 92 if we consider symmetry)Data StructureSoftware College Northeastern UniversityEight Queens StrategyFive queens that cannot attack each other, but that can attack all of column 6; backtracking to column 5 to try another square for the queen; backtracking to column 4 to try another square for

47、 the queen and then considering column 5 againData StructureSoftware College Northeastern UniversityThe Eight Queens ProblemThe Eight Queens Problem: Place eight queens on the chessboard so that no queen attack any other queen.QData StructureSoftware College Northeastern UniversityEight Queens Class

48、const int BOARD_SIZE = 8; / squares per row or columnclass EightQueens public:EightQueens();/ Sets all squares to EMPTY.void clearBoard(); / Sets all squares to EMPTY.void displayBoard(); / Displays the board.bool placeQueens(int currColumn);/ Places queens in columns of the board beginning at colum

49、n specified./ Precondition: Queens are placed correctly in columns 1 through/currColumn-1 and no Queens are placed in columns currColumn through/ BOARD_SIZE./ Postcondition: If a solution is found, each column of board contains one/ queen and the function returns true otherwise returns false (no sol

50、ution/ exists for a queen anywhere in column currColumn).Data StructureSoftware College Northeastern UniversityEight Queens Classprivate: int boardBOARD_SIZE; / row-position per column, (zero=no queen)/ NOTE: board is zero-indexed for columns void setQueen(int row, int column); / Places a queen in a

51、 given row and column. / Postcondition: There is exactly one queen in the given column. void removeQueen(int row, int column); / Removes a queen from a given row and column. / Postcondition: There is no queen in the given column. bool isUnderAttack(int row, int column); / Determines whether the squa

52、re on the board at a given row and column is under attack by any queen in any column./ Precondition: Queens are placed correctly, i.e. 0=boardi=8 for 0=i BOARD_SIZE) return true; / base case else bool queenPlaced = false;int row = 1; / number of square in column while ( !queenPlaced & (row = BOARD_S

53、IZE) ) / if square can be attacked if (isUnderAttack(row, currColumn) +row; / then consider next square in currColumn else / else place queen and consider next column setQueen(row, currColumn); queenPlaced = placeQueens(currColumn+1); / if no queen is possible in next column, backtrack: remove queen

54、 placed earlier and try next square in column if (!queenPlaced) removeQueen(row, currColumn); +row; / end of while return queenPlaced; / end placeQueensData StructureSoftware College Northeastern UniversityRepresentation of a mazemazem+2p+2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0 1 1 0 0 0 1 1

55、 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 1 1 0 1 0 0