The Magic of Recursion in Programming
Discover the power of recursion in programming through insightful insights and examples. Explore recursive algorithms, methods, and the significance of believing in yourself as a programmer. Understand the crucial roles of arguments and parameters in methods, and delve into the intricacies of how methods perform their jobs. Unveil the beauty of fractal images and embark on a journey to master the art of recursive thinking.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Recursion The Magic of Believing in Yourself as a Programmer
Recursion Review of Methods Fractal Images What is Recursion Recursive Algorithms with Simple Variables Towers of Hanoi
Methods Named set of instructions name suggests what the instructions are for println print a line nextInt get the next int setName change the name what do you suppose these methods do? sort shuffle drawFern
The Job of the Method Every method has a job to do print a line, get the next int, draw a fern, (part of the job may be signalling errors) Call the method the job gets done that s what the method is there for How the method does the job the body/definition of the method is none of the caller s business!
Doing The Job The method does the job println( Hello ) Hello gets printed nextInt() next int appears sort(myArr) myArr gets sorted How? doesn t matter! tomorrow it could do it a different way just matters that the job gets done
Arguments and Parameters Methods often need extra information what do you want me to print on the line? what do you want me to change the name to? which array do you want to sort/shuffle? Extra information given as an argument buddy.setName( Buford ); Extra information received as a parameter public void setName(String newName) { }
Arguments and Parameters Assignment call is like assignment buddy.setName( Buford ); public void setName(String newName) { } String newName = Buford Arguments and parameters must match up String parameter needs a String argument int parameter needs an int argument argument order must match parameter order the computer cannot figure it out on its own!
Arguments and Parameters Different arguments in different calls printArr(arr1) prints arr1 printArr (arr2) prints arr2 Same parameter every time public static void printArr(int[] arr) int[] arr = arr1 on the first call int[] arr = arr2 on the second call Arguments live; parameters die
Methods and Arguments The method does its job with the arguments you gave it it sorts the array you told it to sort it prints the line you told it to print it draws the fern you told it to draw because that s its job! REMEMBER THAT!
A Fern Drawing in a graphics window Has a root Has an angle growing straight up Has a height height angle root
The drawFern Method A method to draw a fern drawFern(double x, double y, double angle, double size) say where we want the bottom of the fern to be how many pixels across (x) and down (y) say what angle we want the fern drawn at straight up = 180 , flat out to right = 90 say how big we want the fern to be how many pixels from base to tip This method draws a fern that s its job!
Drawing the Fern Window is 800 across by 600 down x,y = 400,600 angle = 180 size = 600 will be a bit shorter (room to grow) half way across full height of window (!) all the way down straight up (180 )
Drawing Another Fern Window is 800 across by 600 down x,y = 200,300 angle = 90 size = 400 1/4 way across half way down half width of window off to side (90 )
Exercise: Draw this Fern Window is 800 across by 600 down root is at centre of window angle is 120 degrees height is 40% of the window s height
One Fern is Part of the Other In order to draw the big fern, we need to draw the little fern In fact, we need to draw three little ferns, all rooted at the same place, all the same size, but at different angles
Drawing the Fern Draw the stem notice where it ends Draw each of the three fronds how to draw the fronds? we have a method that can do that! what s it called? frond STEM
Drawing the Fern Draw the stem of the fern end of the stem is the root of the fronds below Draw a smaller fern going up to the left Draw a smaller fern going straight up Draw a smaller fern going up to the right Stop drawing when the fern gets too small to see (say, 1 pixel tall)
Drawing Smaller Ferns Note where stem ended that s the start of each small fern double[] end = drawStem(x, y, angle, size*0.5); From that location draw smaller fern at new angle 40% of the original size drawFern(end[0], end[1], angle+60, size*0.4); drawFern(end[0], end[1], angle, size*0.4); drawFern(end[0], end[1], angle-60, size*0.4); We need to write this method. Returns new x,y in an array . What about this method?
drawFern Function public void drawFern(double x, double y, double angle, double size) { double[] end; double length = size * 0.5; // stem is 50% the (nominal) height end = drawStem(x, y, angle, length); // returns x,y of stem end if (size > 1.0) { double smaller = size * 0.4; // smaller ferns 40% of full size drawFern(end[0], end[1], angle+60, smaller); drawFern(end[0], end[1], angle, smaller); drawFern(end[0], end[1], angle-60, smaller); } } drawStem draws the stem, and says where it ended (so we can use that as the root of the other parts)
drawFern Function public void drawFern(double x, double y, double angle, double size) { double[] end; double length = size * 0.5; // stem is 50% the (nominal) height end = drawStem(x, y, angle, length); // returns x,y of stem end if (size > 1.0) { double smaller = size * 0.4; // smaller ferns 40% of full size drawFern(end[0], end[1], angle+60, smaller); drawFern(end[0], end[1], angle, smaller); drawFern(end[0], end[1], angle-60, smaller); } } What does this function call do? It draws a fern! That s its job! Different position, angle & size than the original .
Recursion A method that calls itself is said to be recursive drawFern method calls itself drawFern is a recursive method Each call to the method does the job using the arguments it s given! The computer does not get confused but you probably will!
Conditional Recursive Call Recursive call is always conditional usually inside an if or else control Need some condition to stop the recursion otherwise you get a stack overflow error never stops calling itself drawFern recursive call is conditional on size if (size > 1.0) if size <= 1.0, recursion stops
Recursive Calls Bottom out Draw 1 fern size 500 draws 3 ferns size 200 draws 9 ferns size 80 draws 27 ferns size 32 draws 81 ferns size 12.8 draws 243 ferns of size 5.12 draws 729 ferns of size 2.048 draws STEMS of 2187 ferns of size 0.8+ Each level is drawing smaller ferns eventually the ferns are less than 1 pixel tall just draws the stems of those ferns
Fractals See the pretty pictures! http://en.wikipedia.org/wiki/Fractal http://www.geocities.com/rerewhakaaitu/ XaoS viewer you can download this for yourself These are self-similar objects smaller pieces of self look like whole thing like our fern
What is Recursion Recursion is a kind of Divide & Conquer Divide & Conquer Divide problem into smaller problems Solve the smaller problems Recursion Divide problem into smaller versions of itself Smallest version(s) can be solved directly
Recursion in drawFern Problem of drawing large fern broken down into problem of drawing smaller ferns Smallest ferns too small to see draw the stem (a dot) but not the branches (no recursive calls)
Kochs Snowflake Fractal image Draw a triangle, except on each side draw a smaller triangle sticking out Keep going! see the animation on wikipedia http://en.wikipedia.org/wiki/Koch_snowflake
A Snowflake Edge To draw an edge from x1,y1 to x2,y2: draw an edge to 1/3 the distance turn 60 degrees left draw an edge 1/3 of the original distance turn 120 degrees right draw an edge 1/3 of the original distance turn 60 degrees left draw an edge 1/3 of the original distance But WAIT! Each of those edges do the same thing! And each of them too!
Recursion in the Snowflake Problem of drawing an edge is broken down into problem of drawing smaller edges recursion! Smallest lines just get drawn straight one or two dots no recursion base case
Drawing the Snowflake Edge Need to know how long the basic edge should be where to start (x, y) what direction to go in Return where we stop so we can start the next edge from there
Exercise show pseudo-code for this method to drawEdge(x, y, angle, length): 1) 2)
Definitions and Recursion Mathematicians like to define things Mathematicians like to define things recursively Recursive definition uses the thing being defined in its own definition! Step back: conditional definition
Conditional Definitions Definition with two (or more) cases x x if x >= 0 otherwise Math.abs(x) = 1.0 if x > 0 0.0 if x == 0 -1.0 if x < 0 Math.signum(x) =
Recursive Definitions One (or more) cases use the term being defined 1 n*(n-1)! if n > 0 if n == 0 n! = 0 1 Fib(n 1)+Fib(n 2) if n == 0 if n == 1 if n > 1 Fib(n) =
Understanding Recursive Defns How can you define something in terms of itself? Need a BASE CASE the small case that is defined directly there may be more than one Recursive case(s) must get smaller there may be more than one each case must be closer to some base case
Getting Smaller 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 1! 1! = 1 * 0! 0! = 1 Recursive Case Recursive Case Recursive Case Recursive Case Base Case 4 * 6 = 24 3 * 2 = 6 2 * 1 = 2 1 * 1 = 1 Base Case 1 n*(n-1)! if n > 0 if n == 0 n! = Recursive Case
Recursion in Factorial Problem of finding factorial of a number broken down into problem of finding factorial of smaller number factorial of n is n times the factorial of n 1 factorial of 0 is 1
Recursive Function Definitions public static int factorial( int n ) { if (n == 0) { // Base Case return 1; } else if (n > 0) { // Recursive Case return n * factorial(n-1); } else { throw new IllegalArgumentException(); } } n! = n*(n-1)! if n > 0 Base Case 1 if n == 0 Recursive Case
Calling a Recursive Function Just like calling any other function System.out.println( factorial(5) ); 120 The function returns the factorial of what you give it because that s what it does it returns the factorial every time you call it including when you call it inside its definition
Recursive Function Definitions public static int factorial( int n ) { if (n == 0) // Base Case return 1; else // Recursive Case return n * factorial(n-1); } This will calculate the factorial of n 1 It s what the factorial function does
Recursive Function Definitions public void drawFern(double x, double y, double angle, double size) { double[] end; double length = size * 0.5; end = drawStem(x, y, angle, length); if (size > 1.0) { double smaller = size * 0.5; drawFern(end[0], end[1], angle+60, smaller); drawFern(end[0], end[1], angle, smaller); drawFern(end[0], end[1], angle-60, smaller); } } This will draw a fern. It s what the drawFern function does.
Exercise Write a recursive function to calculate the (non-negative integer) power of an integer Hint: it ll look a LOT like the one for factorial 1 n*nk-1 if k == 0 if k > 0 nk =
Thinking Recursively Need to recognize smaller versions of same problem, maybe slightly changed these ferns are like those ferns, but smaller and different place and angle if I had (n 1)! I could just multiply it by n And think of the really easy version a one pixel tall fern is just a dot 0! is just 1
Coding Recursively Remember the two imperatives: SMALLER! when you call the method inside itself, one of the arguments has to be smaller than it was STOP! if the argument that gets smaller is very small (usually 0 or 1), then don t do the recursion
Towers of Hanoi Buddhist monks in Hanoi Set the task of moving golden disks (64) around diamond needles (3) all disks different sizes never put a bigger disk on a littler one When all 64 disks have been moved from the starting needle to the ending, the universe will end (In class demo 4 disks)
What Would be Easy? What if there were only one disk? Start Peg Extra Peg End Peg
A Little Less Easy What if there were two disks? 1) Move one disk out of the way 2) Move other disk to the end post 3) Move first disk to the end post Start Peg Extra Peg End Peg
More Disks? Get top disks out of the way (takes MANY moves) Start Peg (5) Start Peg (4) Extra Peg (5) End Peg (4) End Peg (5) Extra Peg(4)
Towers of Hanoi (5 disks) Move bottom disk (one move) Start Peg (5) Extra Peg (5) End Peg (5)
