Transcript Recursive Thinking - Arizona State University

Recursive Thinking
Anshuman Razdan
Div of Computing Studies
[email protected]
http://i3dea.asu.edu/razdan
Recursion
• Recursion is seen when one of the subtasks
is a simpler/smaller version of the same
problem you are trying to solve in the first
place.
• Java supports recursion by allowing a
method to invoke itself.
• Recursion is intimately tied to mathematical
induction…
CST230 - Razdan et al
2
Example: stack vertically
• problem: given a non-negative integer, write
the individual digits of the integer “stacked
vertically” on the screen.
• example: if input is 2406
output is 2
4
0
6
CST230 - Razdan et al
3
Example cont…
• Can break this into smaller problem:
– stack 240 vertically
– write 6
• Can stack 240 by:
– stack 24
– write 0
• Can stack 24 by:
– stack 2
– write 0
• Can stack 2 by:
– trivial…
CST230 - Razdan et al
4
General Form of Recursion
if( base case condition 1 ){
base case action 1
}
else if( base case condition 2 ){
base case action 2
}
…
else{
break problem into smaller pieces; make recursive call
}
CST230 - Razdan et al
5
stack vertical example
import java.io.*;
import java.lang.*;
public class StackVertical{
public static void main( String[] args ){
System.out.println( "Enter non-negative integer --> " );
BufferedReader in =
new BufferedReader( new InputStreamReader( System.in ) );
try{
String input = in.readLine();
int x = Integer.parseInt( input );
writeVertical( x ); // call to recursive routine
}
catch( IOException e ){
System.out.println("Error reading input...");
}
}
CST230 - Razdan et al
6
stack vertical cont…
public static void writeVertical( int number ){
if(
) // base case
else{ //recursive case
}
}
}
CST230 - Razdan et al
7
Managing recursion
• The computer keeps track of method
activation using “activation records”
• each invocation of a method results in an
activation record FOR THAT
INVOKATION to be pushed onto the
system stack.
• Activation record:
– information about where to return
– parameters
– local variables
CST230 - Razdan et al
8
Example
• trace execution stack for StackVertical with
input 2406
CST230 - Razdan et al
9
Infinite recursion
• If every recursive call results in another
recursive call, the method will
(theoretically) run forever (infinitely)
– this would require that we push an infinite
number of activation records onto the stack…
– the stack is not infinite…
– so we’d get a StackOverflowError
• The base case is ESSENTIAL for recursion
to work. (just like a basis is essential for
mathematical induction to work…)
CST230 - Razdan et al
10