Slide 1OverviewOverviewOverviewFactorialsSubstitution model for recursive evaluationGreatest Common Divisor (GCD)Greatest Common DivisorGreatest Common DivisorSlide 10Slide 12HtreeHtree in JavaAnimated H-treeSlide 16Towers of HanoiTowers of Hanoi LegendTowers of Hanoi: Recursive SolutionTowers of Hanoi: Properties of SolutionSlide 21Fibonacci NumbersFibonacci Numbers and NatureFibonacci Numbers and NatureA Possible Pitfall With RecursionRecursion Challenge 1 (difficult but important)Recursion Challenge 2 (easy and also important)SummaryModule 6: RecursionIntroduction to Programming in Java: An Interdisciplinary Approach · Robert Sedgewick and Kevin Wayne · Copyright © 2002–2010 · 1/13/19 09:53:03 PM2OverviewWhat is recursion? When one function calls itself directly or indirectly.Reproductive PartsM. C. Escher, 19483OverviewWhat is recursion? When one function calls itself directly or indirectly.4OverviewWhat is recursion? When one function calls itself directly or indirectly.FactorialsWrite a method fact(N) such thatfact(N) = 1 * 2 * 3 …… * NThink recursively: how does fact(N) relate to fact(N-1)?fact(N) = fact(N-1) * N is it true for all N?public static int fact(n) {if (n==0) return 1;else return n * fact(n-1);}5Substitution model for recursive evaluation6public static int fact(n) {if (n==0) return 1; // I tend to put base case firstelse return n * fact(n-1);}fact(3) = 3 * fact(3-1)= 3 * fact(2)= 3 * 2 * fact(2-1)= 3 * 2 * fact(1)= 3 * 2 * 1 * fact(1-1)= 3 * 2 * 1 * fact(0)= 3 * 2 * 1 * 1= 3 * 2 * 1= 3 * 2= 67Greatest Common Divisor (GCD)Gcd. Find the largest integer that evenly divides into p and q.Ex. gcd(4032, 1272) = 24.4032 = 26  32  71 1272 = 23  31  531 gcd = 23  31 = 248Greatest Common DivisorGcd. Find the largest integer d that evenly divides into p and q.Euclid's algorithm. [Euclid 300 BCE] (assume p >= q)gcd(4032, 1272) = gcd(1272, 216)= gcd(216, 192)= gcd(192, 24)= gcd(24, 0)= 24.gcd(p, q)p if q0gcd(q, p %q) otherwisebase casereduction step,converges to base case4032 = 3  1272 + 2169Greatest 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);}gcd(p, q)p if q0gcd(q, p %q) otherwisebase casereduction step,converges to base caseRecursive Graphics1213HtreeH-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 3tipsizepublic 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); }}14Htree in Javadraw the H, centered on (x, y)recursively draw 4 half-size Hs1520%40%60%80% 100%Animated H-treeAnimated H-tree.http://en.wikipedia.org/wiki/Image:Hanoiklein.jpgTowers of Hanoi17Towers 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.start finishEdouard Lucas (1883)18Towers of Hanoi LegendQ. Is world going to end (according to legend)?64 golden discs on 3 diamond pegs.World ends when certain group of monks accomplish task.Q. Will computer algorithms help?19Towers of Hanoi: Recursive SolutionMove the largest disc to the goal peg.Initial configuration Move n-1 smallest discs to the non-goal peg1234Move the n-1 discs to the goal peg.20Towers of Hanoi: Properties of SolutionRemarkable properties of recursive solution.Takes 2n - 1 moves to solve n disc problem.Recursive algorithm may reveal fate of world.Takes 585 billion years for n = 64 (at rate of 1 disc per second).Reassuring fact: any solution takes at least this long!Fibonacci Numbers22Fibonacci NumbersFibonacci numbers. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … Fibonacci rabbitsL. P. Fibonacci(1170 - 1250)F(n) 0 if n 01 if n 1F(n 1)  F(n 2) otherwise23Fibonacci Numbers and NatureFibonacci numbers. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … F(n) 0 if n 01 if n 1F(n 1)  F(n 2) otherwisepineconecauliflower24Fibonacci Numbers and NatureFibonacci numbers. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … F(n) 0 if n 01 if n 1F(n 1)  F(n 2) otherwiseLilies, irises, and the trillium have 3 petals; columbines, buttercups, larkspur, and wild rose have 5 petals; delphiniums, bloodroot, and cosmos have 8 petals; corn marigolds have 13 petals; asters have 21 petals; and daisies have 34, 55, or 89 petals25A Possible Pitfall With RecursionFibonacci numbers. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … A natural for recursion?public static long F(int n) { if (n == 0) return 0; if (n == 1) return 1; return F(n-1) + F(n-2);} F(n) 0 if n 01 if n 1F(n 1)  F(n 2) otherwise26Recursion Challenge 1 (difficult but important)Q. Is this an efficient way to compute F(50)?A. No, no, no! This code is spectacularly inefficient.public static long F(int n) { if (n == 0) return 0; if (n == 1) return 1; return F(n-1) + F(n-2);} F(50)F(49) F(48)F(48)F(47) F(46)F(47)F(46) F(45)F(46)F(45) F(44)F(47)F(46) F(45)F(50) is called once.F(49) is called once.F(48) is called 2 times.F(47) is called 3 times.F(46) is called 5 times.F(45) is called 8 times....F(1) is called 12,586,269,025 times.recursion tree for naïve Fibonacci functionF(50)27Recursion Challenge 2 (easy and also important)Q. Is this a more efficient way to compute F(50)?A. Yes. This code does it with 50 additions. Lesson. Don’t use recursion to engage in exponential waste.Context. This is a special case of an important programming technique known as dynamic programming (stay tuned).F(n) n (1)n5n5  = golden ratio  1.618FYI: classic mathpublic static long F(int n) { if (n == 0) return 0; long[] F = new long[n+1]; F[0]