Slippery Rock University
Dr. Deborah Whitfield
Go Browns!
Recursion
Recursive Thinking
A list can be described as:
LIST: number comma LIST
LIST definition uses itself for the definition
A method can call itself
Programmer must provide a "stopping mechanism"
Otherwise infinite recursion
Run-time overhead
Algorithm sometimes difficult to see
Used for lots of mathematical formulas that calculate series or f(n) depends on f(n-1)
Fibonacci
Factorial -- N! = N * N-1 * N-2 * ... * 3 * 2 * 1
Summing
Fibonacci Example
Fractal (Koch)
Another Sample
Merge Sort
Another Merge Example
Recursive Programmimng
Determine recurrence relation
Fn (n) = expression relating to Fn (n - 1)
Write method named Fn receiving n as a paramter and returning correct type
Place code in the method that is the expression relating to Fn (n - 1)
Determine stopping condition
Place an if statement that checks for the stopping condition in the method
If the condition is true return the base value
Otherwise, make the recursive call. (Expression relating to FN(n - 1)
Consider summation
Recursion vs. Iteration
Sometimes recursion is more intuitive
Overhead not needed
Indirect recursion
Method 1 calls Method 2 and Method 2 calls Method 1
Using Recursion
Factorial
function Factorial(num) { if (num == 0) return 1; else return num * Factorial( num - 1 ); }