Transcript Recursion

Recursion
Pepper
Recursion Definition
• English
– procedure that can repeat a version of itself
indefinitely – such as mirrors looking at each
other.
• Math
– defining an object in terms of itself
• Factorials:
•
• Fibonacci:
Recursion in Nature
• Snowflakes
• http://en.wikipedia.org/wiki/Recursive_defi
nition
Java Recursion Definition
• A method calls itself
• Another way to repeat code
Add Up Example
Call yourself repeatedly until you say to stop.
Example:
add up 4 numbers using addUp.
-- Input – number to count
-- Ouput – total of all those numbers added up
Logic:
If the number I am counting is 0, just return 0.
If the number I am counting is anything else, return the number I have +
the total of all the rest (the number I have – 1)
Requires:
• Trust the function will do its job
• A stopper
• A way to reach the stopper (decrement or increment)
Code the addUp method and call it to addUp(4)
Start by trusting it will work
Create a method that assumes it will do the job it says it will:
Return the number you have + everything else that needed to be done
public static int addUp(int numberToCount)
{
// something that is NOT numberToCount will have to be put here
return __________________;
}
}
Then, write the stopping code
When should it stop calling itself?
What should it do in that last case?
public static int addUp(int numberToCount)
{
if (numberToCount == 1) // stop when you are down to #1
{
// last called case work
return __________________;}
else
{
// normal work
return numberToCount + addUp(numberToCount-1);
}
}
addUp Solution
public class AddUp
{
public static void main()
{
System.out.println(addUp(4);
}
public static int addUp(int numberToCount)
{
if (numberToCount == 1)
{
return numberToCount;}
else
{
return numberToCount + addUp(numberToCount-1);
}
}
}
*This can be acted and traced in class.
Alternative: For
public static int addUp(int numberToCount)
{
int sum = 0;
for (int count =1; count <= numberToCount;count++)
{
sum = sum + count;
}
return sum;
}
Create a string of stars
YOU TRY:
starString routine
-- Input – number of stars needed
-- Ouput – String of that many stars
Logic:
If the number I am counting is 1, just return 1 star.
If the number I am counting is anything else, return one star + all the rest of the
stars (the number I have – 1)
Requires:
• Trust the function will do its job
• A stopper
• A way to reach the stopper (decrement or increment)
Code the starString method and call it to create starString(10)
String of Stars
public static String starString (int numberStars)
{
if (numberStars == 0)
{
return("");
}
else
{
return "*" + starString(numberStars-1);
}
}
Using Pictures
• Book uses Drawing Panel, We can use
PictureIt
• Libraries:
– javalib.worldimages.*
– java.awt.Color;
• Classes:
– WorldImage
• show() method
• place(WorldImage, x, y) – x,y is center
– AImage
• makeRectangle(length, width, mode)
Work with shapes
• Make a Rectangle keep getting smaller
until it is size 5 wide.
• The goal is:
Work with shapes
First code without recursion:
– create a method that takes in the size of the
square. Code it to return 1 slightly smaller
square outline on a square.
– Call that method from your main method to
see one square on your canvas.
Code of just the one square
import javalib.worldimages.*;
import java.awt.Color;
public class Test7
{
public static void main()
{
WorldImage myWorld = printInsideSquares ( 600);
myWorld.show();
}
public static WorldImage printInsideSquares( int size)
{
WorldImage mainSquare = AImage.makeRectangle(size,size,Mode.OUTLINED);
WorldImage littleSquare = AImage.makeRectangle(size/10*9,size/10*9,
Color.RED, Mode.OUTLINED);
mainSquare = mainSquare.place( littleSquare, size/2, size/2);
return mainSquare;
}
}
Work with shapes
Code the base case:
– Add an if statement to return just one square
of the given size when the size is < 5.
• Code the recursion:
• Instead of placing the slightly smaller square on
the big square, place a call to your method with
that slighly smaller size.
Work with shapes
import javalib.worldimages.*;
import java.awt.Color;
public class Test6
{ public static void main() {
WorldImage myWorld = printInsideSquares ( 600);
myWorld.show();
}
public static WorldImage printInsideSquares( int size) {
if (size <= 5)
{
return AImage.makeRectangle(size,size,Mode.OUTLINED);
}
else
{
WorldImage mainSquare = AImage.makeRectangle(size,size,Mode.OUTLINED);
// WorldImage littleSquare = AImage.makeRectangle(size/2,size/2,Color.RED,
Mode.OUTLINED);
mainSquare = mainSquare.place(
printInsideSquares( size/10*9), size/2, size/2 );
return mainSquare;
}
}
}