Transcript Recursion - mrkurz.ca

Recursion
“To understand recursion, one
must first understand recursion”
What is Recursion?
• “Recursion is the act of a method calling
itself”
Benefits
• Many problems can only be solved with
Recursive algorithms.
• Recursive methods are often much
sleeker and more elegant then clumsy
iterative equivalents.
• Extremely powerful tool!
Note: Iteration is using a loop.
Draw Backs
1. Hard to understand at first.
2. Not always the most efficient.
Uses of Recursion
1.
2.
3.
4.
5.
6.
All Artificial Intelligence
Fractal designs.
Efficient Sorting and searching.
Data Structure processing
Matrix Multiplication.
At least 50% of the problems I had to
solve in university were recursive.
Parts of Recursive Algorithm
Method name{
if (simplest case)
base case;
return( solution);
else
recursive call
}
An Example
c.print(sum(5));
public static int sum (int n){
if(n<1) //base case
return(1);
else
return (sum(n-1)+n); //recursive call
}
//What does this do?
//Draw A picture
Steps:
1. Check if you in the base case
1. If you are, return the answer.
2. If you’re not call the method on a smaller
problem.
2. call your method from the main program.
Stack Overflows
• Happens when your base case is never
reached and you make too many recursive
calls.
• Each recursive call makes a new method
in memory and if there are too many calls
you run out of memory!
Try this:
Make a recursive algorithm which makes the
following pattern of squares:
Your Method declaration should look like this:
public static void rect (int size,int
x, int y){