Transcript Recursion - mrkurz.ca

Recursion
“To understand recursion, one
must first understand recursion”
What is Recursion?
• “Recursion is the act of a function calling
itself”
• A form of repitition
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.
50% of the problems I had to solve in
university were recursive.
Parts of Recursive Algorithm
function name{
if (simplest case)
base case;
return( solution);
else
recursive call
}
An Example
trace(sum(5));
function sum (n:int):int{
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
2. If you are, return the answer.
3. If you’re not call the function on a smaller
problem.
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!
Lets do problem 0 on the assignment
together.