Transcript my slides - WordPress.com

Recursion in Java
The answer to life’s greatest
mysteries are on the last slide
Recursion
 Recursion is a technique widely used in
programming
 In fact some programming languages
have no loops, only recursion
 Recursion is a key element to advanced
studies such as computational
intelligence
 Beginning programmers usually groan at
recursion… real programmers love it!
Recursion in Java
 A method is recursive if it calls itself.
 There are two key things in recursion
 Base step: ends the recursion
 Recursive step: breaks down the problem to
smaller sub problems
 Before you code anything, you need to
find those two steps… otherwise you
may not understand the problem properly
Example
 Here is a simple recursive java function
for called countdown:
public void countDown( int value )
{
if( value == 0 )
System.out.println( “Blast Off!!!” );//base case, no recursion
else
{
System.out.println( value );
countDown( value – 1);//recursive call of small problem
}
}
LETS TRACE countDown( 5 ) BY HAND
Why Recursion?
 Fact: All recursion can be re written as a
non recursive form with a loop
 Some algorithms are exceedingly
complex as a loop, yet very elegant in a
recursive form.
 Easier to understand  less “bugs” = better
programs
 Let’s take a look at Paint for a minute…
The Flood Fill Algorithm
 The recursion is tricky to follow, but look at how simple
the code is!
public void floodFill( int x, int y, Colour clicked, Colour change )
{
if( outOfBounds(x,y) || getColour(x,y) == change || getColour(x,y) != clicked )
return;//nothing to do – base case
setColour(x,y,change);//colour is the same as was clicked, change it
//Recursive call on neighbours
floodFill( x + 1, y, clicked, colour );
floodFill( x, y + 1, clicked, colour );
floodFill( x - 1, y, clicked, colour );
floodFill( x, y - 1, clicked, colour );
}
Getting the hang of it?
 Let’s try a couple together
 Base step
 Recursive step
 Sum of n numbers
 Ex. 1 + 2 + 3 + 4 + 5 = 15
 Factorials
 0! = 1
 3! = 3 x 2 x 1 = 3 x 2!
 100! = 100x99x98x..x3x2x1 = 100 x 99!
Still Need Practice?
 Here are two other famous recursive examples:
 Fibonacci numbers
 1st number is 1, 2nd number is 1
 Every number after 2 is the sum of the previous two:
1,1,2,3,5,8,13,…
 Euclid’s GCF (from ~300BC)
 http://en.wikipedia.org/wiki/Euclidean_algorithm




Take the larger of the two and divide it by the smaller
If the remainder is zero, return the smaller number
Otherwise take the GCF of smaller and remainder
Example let’s try 60 and 105
Pascal’s Triangle
1
1
1
1
1
1
2
3
4
1
3
6
…
1
4
1
Pascal’s Triangle Cont’
 What’s the recursive pattern in Pascal’s
triangle?
 Hint: Number each row and column
 What is/are the base case(s)?
 What is the recursive case?
Performance: Loops vs.
Recursion
 Why not always use recursion if it makes our code
easier to understand?
 The key reason is performance
 Recursion can quickly overflow the computer’s memory
 Each method call has its own “stack” in memory when
it is called (holds variables, loops, etc.)
 When you make a recursive call, another copy of the
method is stored in memory to preserve the state when
it returns.
 With loops, the variables are reused
 Last I had heard, Sun’s java compiler will translate tail
recursion into a loop for you
 Tail recursion means the recursive call is the last piece of code
in the method (nothing is computed after it returns)
Recursion in Memory
 Consider a call to factorial( 3 ):
 factorial(3)  3 * factorial(2)
 2 * factorial(1)
 1 * factorial(0)
1
Recursion ends, return to last caller:
1*1=1
2*1=2
3*2=6
Recursion in Memory
 With a loop it would look like this:
public int factorial( int n )
{
int fac = 1;
for( int counter = 2; counter <= n; counter++ )
fac *= counter;
return fac;
}
A call to factorial( 3 ) is now just:
1*2*3=6
The H-Fractal
 I’ll code a fractal with you so you can see
just how powerful recursion is for
problem solving
 It would probably take me all day to code
this with a loop
 I can do it with recursion in about 5 minutes
Exercises
 Create a recursive method to calculate
the sum of squares:
 For example, sumSquares( 3 )
 Is 1 + 4 + 9 = 14
Exercises
 Create a recursive method to calculate
positive integer exponents
 Ex.
 findExponent( 3, 2 )
 Returns 9
Exercises
 Create a recursive method to determine if
the values in an array are increasing
 You need an extra parameter telling you
which index to start testing from
 isIncr( int[] data, int start )
 isIncr( {1,3,5,9},0 ) returns true
 isIncr( {3,1,2,4},0 ) returns false
Exercises
 Create a recursive method to sum the
values in an array:
 sum( int[] data, int start )
 sum( {4,2,5}, 0 )
 Returns 11
Exercises
 Create a recursive method called reverse
that reverses the elements in an array
 Reverse( int[] data )
 Reverse( {1,3,5,2,7 } )
 {7,2,5,3,1}
Exercises – Reverse Cont’
 Sometimes when we are using recursion, we
will write a helper method to hold more
parameters.
 In the previous example to reverse an array
you should write a helper method called:
 ReverseHelper( int[] data, int start, int end )
 When you call Reverse( int[] data ) use the
helper method as follows (it does all the work)
 ReverseHelper( data, 0, data.length)
Exercises
 Create a recursive method to determine
whether or not a word is a palindrome or
not.
 A palindrome is a word spelled the same
forwards and backwards
 For example Ogopogo
 public boolean isPalidrome(String word)
Exercises
 To convert an integer to base 2 (binary)
here is an algorithm:
 public String toBinary( int n )
 If the number is zero, return 0
 Otherwise,
 Compute the quotient and remainder when
dividing by 2
 The binary value of the number given is the
binary value of the quotient followed by the
remainder
Binary Numbers
 Ex.
Binary value of 13:
Calculation Quotient
13/2
6
6/2
3
3/2
1
1/2
0
0
13 = 01101 in binary
Remainder
1
0
1
1
return 0
Bonus Graphics - Fractals
 Three fractals which can be created using
recursion are:
 Sierpinski’s Gasket
 Koch’s Snowflake
 Dragon Fractal
 Create a recursive graphics program to display
any of these fractals at a given level
 Demo will be done in class for each fractal and
how they can be obtained
Life’s Greatest Mysteries
Revealed!
 The answer to life’s greatest mysteries
are on the first slide