Kĩ thuật lập trình - Chương 15: Recursion

15Recursion 1We must learn to explore all the options and possibilities that confront us in a complex and rapidly changing world. —James William FulbrightO! thou hast damnable iteration, and art indeed able to corrupt a saint. —William ShakespeareIt's a poor sort of memory that only works backwards.—Lewis Carroll, Alice in WonderlandLife can only be understood backwards; but it must be lived forwards. —Soren KierkegaardPush on—keep moving. —Thomas Morton2OBJECTIVESIn this chapter you will learn:The concept of recursion.How to write and use recursive methods.How to determine the base case and recursion step in a recursive algorithm.How recursive method calls are handled by the system.The differences between recursion and iteration, and when it is appropriate to use each.What geometric shapes called fractals are and how to draw them using recursion.What recursive backtracking is and why it is an effective problem-solving technique.3 15.1   Introduction 15.2   Recursion Concepts 15.3   Example Using Recursion: Factorials 15.4   Example Using Recursion: Fibonacci Series 15.5   Recursion and the Method Call Stack 15.6   Recursion vs. Iteration 15.7   Towers of Hanoi 15.8   Fractals 15.9   Recursive Backtracking 15.10   Wrap-Up 15.11   Internet and Web Resources 415.1 IntroductionEarlier programs structured as methods that call one another in a disciplined, hierarchical mannerRecursive methodsCall themselvesUseful for some problems to define a method to call itselfCan be called directly or indirectly through another method5Fig. 15.1 | Summary of the 32 recursion examples and exercises in this text. (Part 1 of 2)6Fig. 15.1 | Summary of the 32 recursion examples and exercises in this text.  (Part 2 of 2)715.2 Recursion Concepts Recursive problem-solving elementsBase caseRecursive method capable of solving only simplest case—the base caseIf method is called with base case, method returns resultIf method is called with more complex problem, problem divided into two pieces—a piece the method knows how to do and a piece the method does not know how to do (called recursive call or recursion step)Recursive call/recursion stepMust resemble original problem but be slightly simpler or smaller versionMethod calls fresh copy of itself to work on smaller problemNormally includes return statementIndirect recursionRecursive method calls another method that eventually makes call back to recursive method815.3 Example Using Recursion: FactorialsFactorial of n, or n! is the productn · (n – 1) · (n – 2) · · 1With 1! equal to 1 and 0! Defined to be 1.Can be solved recursively or iteratively (nonrecursively)Recursive solution uses following relationship:n! = n · (n – 1)!Infinite recursion – recursive calls are continuously made until memory has been exhaustedCaused by either omitting base case or writing recursion step that does not converge on base case9Fig. 15.2 | Recursive evaluation of 5!. 10Base case returns 1Portion method knows how to doRecursion step breaks problem into two parts: one the method knows how to do, one the method does notRecursive call: Portion method does not know how to do; smaller version of original problemOriginal call to recursive method11Common Programming Error 15.1Either omitting the base case or writing the recursion step incorrectly so that it does not converge on the base case can cause a logic error known as infinite recursion, where recursive calls are continuously made until memory has been exhausted. This error is analogous to the problem of an infinite loop in an iterative (nonrecursive) solution. 12Calculate and display factorials1315.4 Example Using Recursion: Fibonacci SeriesFibonacci series begins with 0 and 1 and has property that each subsequent Fibonacci number is the sum of previous two Fibonacci numbers.Series occurs in nature, ratio of successive Fibonacci numbers converges on golden ratio or golden meanFibonacci series defined recursively as:fibonacci(0) = 0fibonacci(1) = 1fibonacci(n) = fibonacci(n – 1) + fibonacci(n – 2)Recursive solution for calculating Fibonacci values results in explosion of recursive method calls14Two base casesTwo recursive callsOriginal call to recursive method15Calculate and display Fibonacci values16Fig. 15.7 | Set of recursive calls for fibonacci( 3 ). 17Avoid Fibonacci-style recursive programs, because they result in an exponential “explosion” of method calls. Performance Tip 15.11815.5 Recursion and the Method Call StackMethod call stack used to keep track of method calls and local variables within a method callJust as with nonrecursive programming, recursive method calls are placed at the top of the method call stackAs recursive method calls return, their activation records are popped off the stack and the previous recursive calls continue executingCurrent method executing is always method whose activation record is at top of stack19Fig. 15.8 | Method calls made within the call fibonacci( 3 ). 20Fig. 15.9 | Method calls on the program execution stack. 2115.6 Recursion vs. IterationAny problem that can be solved recursively can be solved iterativelyBoth iteration and recursion use a control statementIteration uses a repetition statementRecursion uses a selection statementIteration and recursion both involve a termination testIteration terminates when the loop-continuation condition failsRecursion terminates when a base case is reachedRecursion can be expensive in terms of processor time and memory space, but usually provides a more intuitive solution22Iterative solution uses counter-controlled repetition2324Software Engineering Observation 15.1Any problem that can be solved recursively can also be solved iteratively (nonrecursively). A recursive approach is normally preferred over an iterative approach when the recursive approach more naturally mirrors the problem and results in a program that is easier to understand and debug. A recursive approach can often be implemented with fewer lines of code. Another reason to choose a recursive approach is that an iterative one might not be apparent. 25Avoid using recursion in situations requiring high performance. Recursive calls take time and consume additional memory. Performance Tip 15.226Common Programming Error 15.2Accidentally having a nonrecursive method call itself either directly or indirectly through another method can cause infinite recursion. 2715.7 Towers of HanoiClassic problem – Priests in Far East are attempting to move a stack of disks from one peg to another. One disk must be moved at a time, at no time may a larger disk be placed above a smaller diskRecursive solution:Move n – 1 disks from peg 1 to peg 2, using peg 3 as temporary holding areaMove the last disk (the largest) from peg 1 to peg 3Move the n – 1 disks from peg 2 to peg 3, using peg 1 as a temporary holding areaBase case: When only one disk needs to be moved – no temporary holding area needed, disk is simply moved28Fig. 15.12 | Towers of Hanoi for the case with four disks. 29Base case: Simply display move30Move n-1 disks from peg 1 to peg 2Move last disk from peg 1 to peg 3Move n-1 disks from peg 2 to peg 3Use peg 1 as temporary holding areaUse peg 3 as temporary holding area31Make initial call to recursive method3215.8 FractalsFractal – a geometric figure that often can be generated from a pattern repeated recursively an infinite number of timesPattern applied to each segment of original figureBenoit Mandelbrot introduced term “fractal,” along with specifics of how fractals are created and their practical applicationsHelp us better understand patterns in nature, the human body and the universePopular art form3315.8 FractalsSelf-similar property – fractals have this property in the case that, when subdivided into parts, each resembles a reduced-size copy of the wholeIf part is exact copy of original, fractal is said to be strictly self similarEach time pattern is applied, fractal is said to be at new level or depthFractal examples: Koch Curve, Koch Snowflake34Fig. 15.15 | Koch Curve fractal. (a)(b)(c)(d)(e)(f)35Fig. 15.16 | “Lo fractal” at level 0. 36Fig. 15.17 | Determining points C and D for level 1 of “Lo fractal.” 37Fig. 15.18 | “Lo fractal” at level 1, with C and D points determined for level 2. [Note: The fractal at level 0 is included as a dashed line as a reminder of where the line was located in relation to the current fractal.] 38Fig. 15.19 | “Lo fractal” at level 2, with dashed lines from level 1 provided. 39Fig. 15.20 | “Lo fractal” at level 2. 404142Retrieve current levelDecrease levelSet new levelRedraw fractal up to new level43Retrieve current levelIncrease levelSet new levelRedraw fractal up to new level444546Coordinates of first point for line where fractal is being appliedCoordinates of second point for line where fractal is being appliedBase case: Simply draw line, pattern is not appliedRecursion step: Apply fractal patternCalculate midpointCalculate point to form right triangleApply pattern to three new lines47Make first call to recursive method whenever window is repainted4849505115.9 Recursive BacktrackingRecursive Backtracking – process of using recursion to return to earlier decision pointIf one set of recursive calls does not result in solution, program backs up to previous decision point and makes different decision, often resulting in another set of recursive callsExamplesMaze problemEight-Queens problem52