數(shù)據(jù)結(jié)構(gòu)迭代.ppt

1、Data Structure,Software College Northeastern University,Chapter 5,Recursion,Data Structure,Software College Northeastern University,Overview,Recursive Solutions Mathemetical Induction Recursive Definitions Stack Activation Frames Recursive and Iteration,Data Structure,Software College Northeastern U

2、niversity,Recursive Solutions,Sometimes, the best way to solve a problem is by solving a smaller version of the exact same problem first Recursion 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,Data Structure,Software

3、 College Northeastern University,Recursion,When you turn that into a program, you end up with functions that call themselves: Recursive Functions,Data Structure,Software College Northeastern University,Recursive Function,a recursion function is a function that either directly or indirectly makes a c

4、all 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 Structure,Software College Northeastern University,Finding a Recursive Solution,a recursive solution to a problem must be written car

5、efully 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,Data Struc

6、ture,Software College Northeastern University,Mathemetical Induction,To prove,Let 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 all n=

7、1 .,Data Structure,Software College Northeastern University,Mathemetical Induction,4 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 IH,Da

8、ta Structure,Software College Northeastern University,A recursive definition,int 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 Structure,Software College Northeastern University,Printing number i

9、n Any Base,const 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 DIGIT_TABLE n % base ; ,Potential problems in this code: if base16: - out of bound; if base = 0: - division by 0; i

10、f base = 1: - infinite loop.,Data Structure,Software College Northeastern University,General format for Many Recursive Functions,if (some easily-solved condition) / base case solution statement else / general case recursive function call,Data Structure,Software College Northeastern University,Recurs

11、ion does not terminate properly: Stack Overflow !,Common Programming Error,Data Structure,Software College Northeastern University,When 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 i

12、n the calling block after the function code is executed; This correct place is called the return address When any function is called, the run-time stack is used -On this stack is placed an activation record for the function call,Data Structure,Software College Northeastern University,Stack Activatio

13、n Frames,The activation record contains the return address for this function call, and also the parameters, 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

14、 the function code is reached, or when a return statement is reached in the function code At this time the functions return value, if non-void, is brought back to the calling block return address for use there,Data Structure,Software College Northeastern University,A Stake of Activation Records,int

15、s (int n) if (n =1) return 1; else return s(n-1) + n; void main() int sum; sum = s(4); /instruction 100 printf(“sum=%d”,sum); return; ,Data Structure,Software College Northeastern University,int Func(/* in */ int a, /* in */int b ) int result; if ( b = 0 ) / base case result = 0; else if ( b 0 ) / f

16、irst general case result = a + Func ( a , b - 1 ) ) ; / instruction 50 return result; void main() int x; x = Func(5,2); /instruction 100 printf(“%dn”,x); return; ,A recursive function,Data Structure,Software College Northeastern University,FCTVAL ? result ? b 2 a 5 Return Address 100,Run-Time Stack

17、Activation Records,original call at instruction 100 pushes on this record for Func(5,2),x = Func(5, 2);/ original call at instruction 100,Data Structure,Software College Northeastern University,FCTVAL ? result ? b 1 a 5 Return Address 50 FCTVAL ? result 5+Func(5,1) = ? b 2 a 5 Return Address 100,cal

18、l in Func(5,2) code at instruction 50 pushes on this record for Func(5,1),Run-Time Stack Activation Records,x = Func(5, 2);/ original call at instruction 100,Data Structure,Software College Northeastern University,FCTVAL ? result ? b 0 a 5 Return Address 50 FCTVAL ? result 5+Func(5,0) = ? b 1 a 5 Re

19、turn Address 50 FCTVAL ? result 5+Func(5,1) = ? b 2 a 5 Return Address 100,call in Func(5,1) code at instruction 50 pushes on this record for Func(5,0),Run-Time Stack Activation Records,x = Func(5, 2);/ original call at instruction 100,Data Structure,Software College Northeastern University,FCTVAL 0

20、 result 0 b 0 a 5 Return Address 50 FCTVAL ? result 5+Func(5,0) = ? b 1 a 5 Return Address 50 FCTVAL ? result 5+Func(5,1) = ? b 2 a 5 Return Address 100,record for Func(5,0) is popped first with its FCTVAL,record for Func(5,2),record for Func(5,1),Run-Time Stack Activation Records,x = Func(5, 2);/ o

21、riginal call at instruction 100,Data Structure,Software College Northeastern University,record for Func(5,2),record for Func(5,1) is popped next with its FCTVAL,Run-Time Stack Activation Records,x = Func(5, 2);/ original call at instruction 100,FCTVAL 5 result 5+Func(5,0) = 5+ 0 b 1 a 5 Return Addre

22、ss 50 FCTVAL ? result 5+Func(5,1) = ? b 2 a 5 Return Address 100,Data Structure,Software College Northeastern University,x = Func(5, 2);/ original call at instruction 100,FCTVAL 10 result 5+Func(5,1) = 5+5 b 2 a 5 Return Address 100,record for Func(5,2) is popped last with its FCTVAL,Run-Time Stack

23、Activation Records,Data Structure,Software College Northeastern University,Divide and Conquer (分治法),Given an instance of the problem to be solved, split this into several, smaller, sub-instances (of the same problem) independently solve each of the sub-instances and then combine the sub-instance sol

24、utions so as to yield a solution for the original instance.,Data Structure,Software College Northeastern University,原問題,子問題1,子問題2,子問題k,子問題1,子問題2,子問題3,相同類型,不可再分，直接求解,Data Structure,Software College Northeastern University,Too much recursion Can Be Dangerous,Fibonacci numbers. long fib (int n) if (n =

25、1) return n; else return fib(n-1) + fib(n-2); ,F5 F4 F3 F3 F2 F2 F1 F2 F1 F1 F0F1 F0 F1 F0,Data Structure,Software College Northeastern University,This definition will lead to exponential running time. Reason: - too much redundant work Not necessary to use recursive,Too much recursion Can Be Dangero

26、us,Data Structure,Software College Northeastern University,Recursion vs. Iteration,You could have written the power-function iteratively, i.e. using a loop construction Wheres the difference ?,Data Structure,Software College Northeastern University,Iteration can be used in place of recursion An iter

27、ative algorithm uses a looping structure A recursive algorithm uses a branching structure Recursive solutions are often less efficient, in terms of both time and space, than iterative solutions Recursion can simplify the solution of a problem, often resulting in shorter, more easily understood sourc

28、e code (Nearly) every recursively defined problem can be solved iteratively iterative optimization can be implemented after recursive design,Recursion vs. Iteration,Data Structure,Software College Northeastern University,Deciding whether to use a Recursive Function,When the depth of recursive calls

29、is relatively “shallow” The recursive version does about the same amount of work as the nonrecursive version The recursive version is shorter and simpler than the nonrecursive solution,Data Structure,Software College Northeastern University,Recursion or Iteration?,EFFICIENCY,CLARITY,Data Structure,S

30、oftware College Northeastern University,Examples: Fractal Tree,Data Structure,Software College Northeastern University,Examples: The 8 Queens Problem,http:/mossie.cs.und.ac.za/murrellh/javademos/queens/queens.html,Eight queens are to be placed on a chess board in such a way that no queen checks agai

31、nst any other queen,Data Structure,Software College Northeastern University,Backtracking（回溯法）,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 pat

32、h and (in the latter case) go back (track back) in order to try another path.,Data Structure,Software College Northeastern University,Backtracking (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 pa

33、rticular guess leads to an impasse (no solution絕境), we retrace our steps in reverse order to replace our last guess with another option, try to complete the solution again.,Data Structure,Software College Northeastern University,1,1,1,1,1,1,1,1,2,4,2,2,2,3,2,3,3,2,a,b,c,d,e,f,g,h,Data Structure,Soft

34、ware College Northeastern University,Traversing a Maze,Data Structure,Software College Northeastern University,Traversing a Maze,Data Structure,Software College Northeastern University,Entrance,exit,Traversing a Maze,Data Structure,Software College Northeastern University,Data Structure,Software Col

35、lege Northeastern University,Backtracking (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.,A,B,D,C,G,H

36、,E,F,I,J,K,Data Structure,Software College Northeastern University,Generating the candidates,Classic 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: Succe

37、ed:done,Data Structure,Software College Northeastern University,8-queens problem,Data Structure,Software College Northeastern University,Facts,8-queens has more than 281,474,976,711,000 candidates Prune（剪枝）: reject nonviable candidates early, not just when sequence is complete. Example: 8-queens wit

38、h pruning looks at about 16,000 partial and complete candidates 12 solutions( 92 if we consider symmetry),Data Structure,Software College Northeastern University,Eight Queens Strategy,Five queens that cannot attack each other, but that can attack all of column 6; backtracking to column 5 to try anot

39、her square for the queen; backtracking to column 4 to try another square for the queen and then considering column 5 again,Data Structure,Software College Northeastern University,The Eight Queens Problem,The Eight Queens Problem: Place eight queens on the chessboard so that no queen attack any other

40、 queen.,Data Structure,Software College Northeastern University,Eight Queens Class,const int BOARD_SIZE = 8; / squares per row or column class EightQueens public: EightQueens();/ Sets all squares to EMPTY. void clearBoard(); / Sets all squares to EMPTY. void displayBoard(); / Displays the board. boo

41、l placeQueens(int currColumn); / Places queens in columns of the board beginning at column 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 colu

42、mn of board contains one / queen and the function returns true otherwise returns false (no solution / exists for a queen anywhere in column currColumn).,Data Structure,Software College Northeastern University,Eight Queens Class,private: int boardBOARD_SIZE; / row-position per column, (zero=no queen)

43、 / NOTE: board is zero-indexed for columns void setQueen(int row, int column); / Places a queen in a 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

44、no queen in the given column. bool isUnderAttack(int row, int column); / Determines whether the square 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=i8. / Postcondition: If under attack, returns t

45、rue; otherwise, returns false. ; / end class,Data Structure,Software College Northeastern University,bool Queens:placeQueens(int currColumn) / Calls: isUnderAttack, setQueen, removeQueen. if (currColumn BOARD_SIZE) return true; / base case else bool queenPlaced = false; int row = 1; / number of squa

46、re in column while ( !queenPlaced / end placeQueens,Data Structure,Software College Northeastern University,Representation 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 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