Eric Roberts Handout #18CS 106B April 15, 2009Procedural RecursionRecursion• One of the most important “Great Ideas” in CS 106B is theconcept of recursion, which is the process of solving aproblem by dividing it into smaller subproblems of the sameform. The italicized phrase is the essential characteristic ofrecursion; without it, all you have is a description of stepwiserefinement of the sort we teach in CS 106B.• The fact that recursive decomposition generates subproblemsthat have the same form as the original problem means thatrecursive programs will use the same function or method tosolve subproblems at different levels of the solution. In termsof the structure of the code, the defining characteristic ofrecursion is having functions that call themselves, directly orindirectly, as the decomposition process proceeds.A Simple Illustration of Recursion• Suppose that you are the national fundraising director for acharitable organization and need to raise $1,000,000.• One possible approach is to find a wealthy donor and ask fora single $1,000,000 contribution. The problem with thatstrategy is that individuals with the necessary combination ofmeans and generosity are difficult to find. Donors are muchmore likely to make contributions in the $10 range.• Another strategy would be to ask 100,000 friends for $10each. Unfortunately, most of us don’t have 100,000 friends.• There are, however, more promising strategies. You could,for example, find ten regional coordinators and charge eachone with raising $100,000. Those regional coordinators couldin turn delegate the task to local coordinators, each with agoal of $10,000, continuing the process reached a manageablecontribution level.A Simple Illustration of RecursionThe following diagram illustrates the recursive strategy forraising $1,000,000 described on the previous slide:Goal:$1,000,000Goal:$100,000Goal:$100,000Goal:$100,000Goal:$100,000Goal:$100,000Goal:$100,000Goal:$100,000Goal:$100,000Goal:$100,000Goal:$100,000Goal:$10,000Goal:$10,000Goal:$10,000Goal:$10,000Goal:$10,000Goal:$10,000Goal:$10,000Goal:$10,000Goal:$10,000Goal:$10,000Goal:$1000Goal:$1000Goal:$1000Goal:$1000Goal:$1000Goal:$1000Goal:$1000Goal:$1000Goal:$1000Goal:$1000Goal:$100Goal:$100Goal:$100Goal:$100Goal:$100Goal:$100Goal:$100Goal:$100Goal:$100Goal:$100A Pseudocode Fundraising StrategyIf you were to implement the fundraising strategy in the form ofa C++ function, it would look something like this:void CollectContributions(int n) { if (n <= 100) { Collect the money from a single donor. } else { Find 10 volunteers. Get each volunteer to collect n/10 dollars. Combine the money raised by the volunteers. }}What makes this strategy recursive is that the lineGet each volunteer to collect n/10 dollars.will be implemented using the following recursive call:CollectContributions(n / 10);The Towers of Hanoi Solutionint main() {Hanoivoid MoveTower(int n, char start, char finish, char temp) { if (n == 1) { MoveSingleDisk(start, finish); } else { MoveTower(n - 1, start, temp, finish); MoveSingleDisk(start, finish); MoveTower(n - 1, temp, finish, start); }}start finish'A' 'B'n3temp'C'The Recursive “Leap of Faith”• The purpose of going through the complete decomposition ofthe Towers of Hanoi problem is to convince you that theprocess works and that recursive calls are in fact no differentfrom other method calls, at least in their internal operation.• The danger with going through these details is that it mightencourage you to do the same when you write your ownrecursive programs. As it happens, tracing through the detailsof a recursive program almost always makes such programsharder to write. Writing recursive programs becomes naturalonly after you have enough confidence in the process that youdon’t need to trace them fully.• As you write a recursive program, it is important to believethat any recursive call will return the correct answer as longas the arguments define a simpler subproblem. Believing thatto be true—even before you have completed the code—iscalled the recursive leap of faith.– 2 –The Recursive Paradigm• Most recursive methods you encounter in an introductorycourse have bodies that fit the following general pattern:if (test for a simple case) { Compute and return the simple solution without using recursion.} else { Divide the problem into one or more subproblems that have the same form. Solve each of the problems by calling this method recursively. Return the solution from the results of the various subproblems.}• Finding a recursive solution is mostly a matter of figuring outhow to break it down so that it fits the paradigm. When youdo so, you must do two things:Identify simple cases that can be solved without recursion.1.Find a recursive decomposition that breaks each instance ofthe problem into simpler subproblems of the same type, whichyou can then solve by applying the method recursively.2.Graphical Recursion• Recursion comes up in certain graphical applications, mostnotably in the creation of fractals, which are mathematicalstructures that consist of similar figures repeated at variousdifferent scales. Fractals were popularized in a 1982 book byBenoit Mandelbrot entitled The Fractal Geometry of Nature.• One of the simplest fractal patterns to draw is the Kochfractal, named after its inventor, the Swedish mathematicianHelge von Koch (1870-1924). The Koch fractal is sometimescalled a snowflake fractal because of the beautiful, six-sidedsymmetries it displays as the figure becomes more detailed. asillustrated in the following diagram:Methods in the Graphics LibraryInitGraphics()Initializes the graphics library and clears the graphics window.MovePen(x, y)Moves the drawing pen to the point (x, y) without drawing a line.DrawLine(dx, dy)Draws a line from the current point using the displacements dx and dy.GetWindowWidth()Returns the width of the graphics window.GetWindowHeight()Returns the height of the graphics window.SetCoordinateSystem(system)Sets the coordinate system to "screen" or "cartesian".DrawPolarLineconst double PI = 3.1415926535;void DrawPolarLine(double r, double theta) { double radians = theta / 180 * PI; DrawLine(r * cos(radians), r * sin(radians));}• The Koch snowflake fractal is much easier to write if you usepolar coordinates, in which each line segment is specified interms of its length (r) and its angle from the origin ( ), asillustrated in the