Transcript Recursion - Southern Oregon University

Recursion
• Definition: A method that calls itself.
• Recursion can be direct or indirect. Indirect recursion
involves a method call that eventually recalls the original
method
• Examples
public factorial(int n)
{ if (n==1) return 1;
return n * factorial(n-1);
}
public hello(int n)
{ if (n>=0)
{ System.out.prinln("Hello"); hello(n-1);
} }
Example: do(9, -1);
Why does it work?
Method
• Java creates an activation record
for every method call
Definition: An activation record
is a block of memory on the Java
stack containing parameter
values, local variables, the return
address, and return value.
public int do(int n,int k)
{ String str = "abc";
int
num = 5;
return str.length()+num;
}
• The activation only exists while
the method executes
• Java releases all local storage
when the method returns
Activation Record
n: 9
k: -1
str: "abc"
value: 5
• A stack is a last-in first-out list
• A list is an ordered collection of
elements.
return:
instruction after the call
Another Example
• Simple Example:
Sum(int size, int[] x)
{ if size>0) return x[size]+sum(size-1);
return x[0];
}
• Notes:
– The 'if' statement is the non-recursive part (the base case)
– The 'second return' is the recursive step
– Infinite loop occurs if the base case never executes
• Question:
– What happens if size is negative?
Designing a recursive method
• Three are two requirements
– Define the base case
– Define the relationship between the problem and into one or more
smaller problems of the same kind
• When is recursion beneficial?
– Recursive algorithms are ALWAYS slower than their nonrecursive counterparts. Why?
– Recursive algorithms can often reduce a problem to just a few
statements.
– Non-recursive algorithms can be sometimes more difficult to
program and maintain.
– Recursion is useful when the recursion step significantly reduces
the problem size.
• Normally, static variables should not be modified by a
recursive method. Why?
Some more simple examples
Which are good uses of recursion?
• Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, …
– Base case: n<=2; Recursive step: f(n) <- f(n-2)+f(n-1)
• Greatest common denominator
– Base case: y%x = 0; Recursive step: gcd(x,y) <- gcd(y%x,x)
• Palindrome Tester
– Base case: length <=2 or first character <> last character
– Recursive step: Pal(s.substring(1,s.length()-1))<-Pals(s)
• Print a string (Question: How would you reverse a string?)
– Base case: length=1; Recursive step: print char 0 and call with remainder
• Count string characters, translate a string, sequential search,
print all head and tail outcomes
• Tower of Hanoi (How many moves to solve the 64 problem?)
– Base case: Number of pegs <=1
– Recursive step: H(n) <- Move n-1 from source to spare, move last peg to
destination, Move n-1 from spare to destination
Traversing a maze
• Base case
– Current location in the array is [n-1,n-1]
• Recursive step
– For each direction
• traverse maze in that direction.
• Return result if true returned as result of the recursive call
• Enhancement possibilities
–
–
–
–
Transform the problem to three dimensions?
How can the original maze be preserved?
How could we print the solution path?
How could we find the shortest path solution?
Graphics and Fractals
• Definition: A recursive geometric pattern
• Examples:
–
–
–
–
Drawing a tree visually
Sierpinski's triangles
Koch's Snowflake
Mandelbrot set
• Our lab4: Generate a recursive landscape