# What is recursion

###### What is recursion 3
2.3 Recursion Introduction to Programming in Java: An Interdisciplinary Approach · Robert Sedgewick and Kevin Wayne · Copyright © 2002–2010 · 9/14/11 10:07 AM Overview What is recursion When one function calls itself directly or indirectly. Why learn recursion   New mode of thinking.   Powerful programming paradigm. Many computations are naturally selfreferential.   Mergesort, FFT, gcd, depthfirst search.   Linked data structures.   A folder contains files and other folders. Closely related to mathematical induction. Reproductive Parts M. C. Escher, 1948 2 Greatest Common Divisor Gcd. Find largest integer that evenly divides into p and q. Ex. gcd(4032, 1272) = 24. 6 2 1 4032 = 2 × 3 × 7 3 1 1 1272 = 2 × 3 × 53 3 1 gcd = 2 × 3 = 24 Applications.   Simplify fractions: 1272/4032 = 53/168.   RSA cryptosystem. 3 Greatest Common Divisor Gcd. Find largest integer d that evenly divides into p and q. Euclid's algorithm. Euclid 300 BCE ⎧ base case p if q = 0 gcd(p, q) =⎨ gcd(q, p q) otherwise reduction step, ⎩ converges to base case € gcd(4032, 1272) = gcd(1272, 216) = gcd(216, 192) = gcd(192, 24) 4032 = 3 × 1272 + 216 = gcd(24, 0) = 24. 4 Greatest Common Divisor Gcd. Find largest integer d that evenly divides into p and q. ⎧ base case p if q = 0 gcd(p, q) =⎨ reduction step, gcd(q, p q) otherwise ⎩ converges to base case € p q q p q x x x x x x x x gcd p = 8x q = 3x gcd(p, q) = x 5 Greatest Common Divisor Gcd. Find largest integer d that evenly divides into p and q. ⎧ base case p if q = 0 gcd(p, q) =⎨ reduction step, gcd(q, p q) otherwise ⎩ converges to base case € Java implementation. public static int gcd(int p, int q) if (q == 0) return p; base case else return gcd(q, p q); reduction step 6 Recursive Graphics 9 Htree Htree of order n. and half the size   Draw an H.   Recursively draw 4 Htrees of order n1, one connected to each tip. tip size order 3 order 1 order 2 10 Htree in Java public 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; draw the H, centered on (x, y) StdDraw.line(x0, y, x1, y); StdDraw.line(x0, y0, x0, y1); StdDraw.line(x1, y0, x1, y1); recursively draw 4 halfsize Hs draw(n1, sz/2, x0, y0); draw(n1, sz/2, x0, y1); draw(n1, sz/2, x1, y0); draw(n1, sz/2, x1, y1); public static void main(String args) int n = Integer.parseInt(args0); draw(n, .5, .5, .5); 11 Animated Htree Animated Htree. Pause for 1 second after drawing each H. 20 40 60 80 100 12 Towers of Hanoi http://en.wikipedia.org/wiki/Image:Hanoiklein.jpg Towers of Hanoi Move 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 finish Towers of Hanoi demo Edouard Lucas (1883) 14 Towers of Hanoi Legend Q. 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 15 Towers of Hanoi: Recursive Solution Move n1 smallest discs right. Move largest disc left. cyclic wraparound Move n1 smallest discs right. 16 Towers of Hanoi: Recursive Solution public class TowersOfHanoi public static void moves(int n, boolean left) if (n == 0) return; moves(n1, left); if (left) System.out.println(n + " left"); else System.out.println(n + " right"); moves(n1, left); public static void main(String args) int N = Integer.parseInt(args0); moves(N, true); moves(n, true) : move discs 1 to n one pole to the left moves(n, false): move discs 1 to n one pole to the right smallest disc 17 Towers of Hanoi: Recursive Solution java TowersOfHanoi 4 java TowersOfHanoi 3 1 right 1 left 2 left 2 right 1 right 1 left 3 right 3 left 1 right 1 left 2 left 2 right 1 right 1 left 4 left 1 right 2 left 1 right 3 right every other move is smallest disc 1 right 2 left 1 right subdivisions of ruler 18 Towers of Hanoi: Recursion Tree n, left 3, true 1 14 28 15 2, false 2, false 8 16 21 2 7 13 27 22 1, true 1, true 1, true 1, true 3 4 6 5 9 17 18 10 11 12 19 20 23 24 25 26 1 left 2 right 1 left 3 left 1 left 2 right 1 left 19 Towers of Hanoi: Properties of Solution Remarkable properties of recursive solution. n   Takes 2 1 moves to solve n disc problem.   Sequence of discs is same as subdivisions of ruler.   Every other move involves smallest disc. Recursive algorithm yields nonrecursive solution   Alternate between two moves: to left if n is odd –  move smallest disc to right if n is even –  make only legal move not involving smallest disc 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 20 DivideandConquer Divideandconquer paradigm.   Break up problem into smaller subproblems of same structure.   Solve subproblems recursively using same method.   Combine results to produce solution to original problem. Divide et impera. Veni, vidi, vici. Julius Caesar Many important problems succumb to divideandconquer.   FFT for signal processing.   Parsers for programming languages.   Multigrid methods for solving PDEs.   Quicksort and mergesort for sorting.   Hilbert curve for domain decomposition.   Quadtree for efficient Nbody simulation.   Midpoint displacement method for fractional Brownian motion. 21 Fibonacci Numbers Fibonacci Numbers Fibonacci numbers. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … ⎧ 0 if n = 0 ⎪ F(n) = 1 if n =1 ⎨ ⎪ F(n−1) + F(n− 2) otherwise ⎩ € L. P. Fibonacci (1170 1250) Fibonacci rabbits 23 Fibonacci Numbers and Nature Fibonacci numbers. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … ⎧ 0 if n = 0 ⎪ F(n) = 1 if n =1 ⎨ ⎪ F(n−1) + F(n− 2) otherwise ⎩ € pinecone cauliflower 24 A Possible Pitfall With Recursion Fibonacci numbers. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … ⎧ 0 if n = 0 ⎪ F(n) = 1 if n =1 ⎨ ⎪ F(n−1) + F(n− 2) otherwise ⎩ € A natural for recursion public static long F(int n) if (n == 0) return 0; if (n == 1) return 1; return F(n1) + F(n2); 25 Recursion Challenge 1 (difficult but important) Q. Is this an efficient way to compute F(50) public static long F(int n) if (n == 0) return 0; if (n == 1) return 1; return F(n1) + F(n2); A. No, no, no This code is spectacularly inefficient. F(50) F(50) is called once. F(49) F(48) F(49) is called once. F(48) is called 2 times. F(48) F(47) F(47) F(46) F(47) is called 3 times. F(46) is called 5 times. F(47) F(46) F(46) F(45) F(46) F(45) F(45) F(44) F(45) is called 8 times. ... F(1) is called 12,586,269,025 times. recursion tree for naïve Fibonacci function F(50) 26 Recursion Challenge 2 (easy and also important) Q. Is this a more efficient way to compute F(50) public static long F(int n) FYI: classic math if (n == 0) return 0; n n φ −(1−φ) long F = new longn+1; F(n) = 5 F0 = 0; n = φ 5 ⎣ ⎦ F1 = 1; for (int i = 2; i = n; i++) φ = golden ratio ≈ 1.618 Fi = Fi1 + Fi2; return Fn; € 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). 27 Summary How to write simple recursive programs   Base case, reduction step.   Trace the execution of a recursive program.   Use pictures. Why learn recursion Towers of Hanoi by W. A. Schloss.   New mode of thinking.   Powerful programming tool. Divideandconquer. Elegant solution to many important problems. 28
Website URL
Comment
Presentations
Free
Category:
Presentations
User Name:
OscarTucker
User Type:
Professional
Country:
Singapore