2.3 RecursionOverviewGreatest Common DivisorSlide 4Slide 5How-To’s on Writing Recursive FunctionsRecursive GraphicsSlide 8H-treeSlide 10Htree in Java Dr. Java DemoComputational Cost of the H-Tree ProgramSlide 13Towers of HanoiTowers of Hanoi: Recursive Solution2.3 RecursionM. C. Escher, 19482OverviewWhat is recursion? When one function calls itself directly or indirectly.Why learn recursion?Occurs in natureNew way of thinking about programmingPowerful programming paradigm.Many computations are naturally self-referential.Mergesort, FFT, gcd.A folder contains files and other folders.Closely related to mathematical induction.M. C. Escher, 19483Greatest Common DivisorGcd. Find largest integer that evenly divides into p and q.Ex. gcd(4032, 1272) = 24.Applications.Simplify fractions: 1272/4032 = 53/168. RSA cryptosystem.4032 = 26 32 71 1272 = 23 31 531 gcd = 23 31 = 244Greatest Common DivisorGcd. Find largest integer that evenly divides into p and q.Euclid's algorithm. [Euclid 300 BCE]gcd(4032, 1272) = gcd(1272, 216)= gcd(216, 192)= gcd(192, 24)= gcd(24, 0)= 24.base casereduction step,converges to base case4032 = 3 1272 + 2165Greatest Common DivisorGcd. Find largest integer d that evenly divides into p and q.Java implementation.base casereduction steppublic static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q);}base casereduction step,converges to base case6How-To’s on Writing Recursive FunctionsBase Case: You must check if we’ve reached the base case before doing another level of recursion! Make Progress Towards Base Case:Your recursive calls must be on a smaller or simpler input. Eventually this must reach the base case (and not miss it).Multiple recursive calls:Sometimes more than one recursive call. Sometimes not.Are their return values chosen, combined? Learn and follow these rules carefully!Recursive Graphics89H-treeUsed in integrated circuits to distribute the clock signal.H-tree of order n.Draw an H.Recursively draw 4 H-trees of order n-1, one connected to each tip.and half the sizeorder 1order 2order 3tipsize1011Htree in JavaDr. Java Demopublic class Htree { public static void draw(int n, double sz, double x, double y) { if (n == 0) return; double x0 = x - sz/2, x1 = x + sz/2; double y0 = y - sz/2, y1 = y + sz/2; StdDraw.line(x0, y, x1, y); StdDraw.line(x0, y0, x0, y1); StdDraw.line(x1, y0, x1, y1); draw(n-1, sz/2, x0, y0); draw(n-1, sz/2, x0, y1); draw(n-1, sz/2, x1, y0); draw(n-1, sz/2, x1, y1); } public static void main(String[] args) { int n = Integer.parseInt(args[0]); draw(n, .5, .5, .5); }}draw the H, centered on (x, y)recursively draw 4 half-size HsComputational Cost of the H-Tree ProgramH-tree of Order 1First invocation of draw() calls itself 4 timesH-tree of Order 2?1213Towers of Hanoihttp://en.wikipedia.org/wiki/Image:Hanoiklein.jpg14Towers of HanoiMove all the discs from the leftmost peg to the rightmost one.Only one disc may be moved at a time.A disc can be placed either on empty peg or on top of a larger disc.Towers of Hanoi demostart finishEdouard Lucas (1883)15Towers of Hanoi: Recursive SolutionMove n-1 smallest discs right.Move n-1 smallest discs right. Move largest disc left.cyclic
View Full Document
Unlocking...