Article Categories
Tag Cloud
For those who don't know what recursion is (and like a good laugh), click on this link: Google search: Recursion and click on the "did you mean..." item.
Hopefully you've finally figured out that recursion is anything that refers to itself (if not, then you may be stuck browsing google forever trying to find out what recursion is!). A fairly common example of recursion is the Fibonacci numbers. The pattern for Fibonacci numbers is to add the 2 previous terms together for the next term, starting with one and one.
Below is the recurrence relationship for Fibonacci numbers:
F(1) = F(2) = 1
F(n) = F(n-1)+F(n-2)
A recurrence relationship is any relationship where the original function refers to itself. So how do we find F(5)?
F(5) = F(4) + F(3)
F(5) = [F(3)+F(2)] + [F(2)+F(1)]
F(5) = [F(2)+F(1)] + 1 + 1 + 1
F(5) = 1+1+1+1+1
F(5) = 5
Seem like a lot of work? Well, to the computer it's fairly fast most of the time. Later on, I'll tell you about Dynamic Programming so we can speed this up when you want to compute large Fibonacci numbers.
So what are all the parts of a recursive function? First of all, what is a recursive function? A recursive function is any function that calls itself (either directly or indirectly). Here's a simple example in Java:
public static void doIt()
{
doIt();
}Of course, this will eventually cause a stack-over flow error, so it's not recommended you try this code for real.
All useful recursive functions have this general property: reduce the problem until it's so easy the computer can solve it. To fulfill this, recursive functions must have:
1. Base cases defined (cases where the solution is obvious, and can't be reduced any further)
2. Reduction step (place to simplify the given problem)
3. Recursion call to itself (basically solve the simpler case)
In the Fibonacci recursive function above, you can see that it was recursing until it was just adding up 1's. This is because in the Fibonacci sequence 1 is the base case, so we just had to add up 1 some number of times to get F(n).
In theory, all recursive functions can be written iteratively, and all iterative functions can be written recursively. However, in practice you'll find that one or the other of these philosophies will work better depending on the case.
Let's look at the Factorial function recursively, and compare it to its iterative relatives.
Factorial(N) = 1*2*3*...*N
Basically, multiply all the integers from 1 to N to get the factorial of N.
Implemented iteratively, your code would look something like this:
public static int iterativeFactorial(int n)
{
int answer = 1;
for (int i = 1; i < n; i++)
{
answer *= i;
}
return answer;
}We can also write the recursive equivalent of this function:
F(1) = 1
F(N) = F(N-1)*N
can you see how this would yield the same results as the iterative factorial? Here's the code to compute factorials recursively:
public static int recursiveFactorial(int n)
{
if (n == 1)
{
return 1;
}
else
{
return n * recursiveFactorial(n-1);
}
}So, in terms of performance, how does recursion stack up against the iterative solution here? Sadly, the answer is quite poorly. Recursive function here requires lots of memory to store the method stack and keep track of all the variables in each recursive call, while iterative solutions only have to keep track of the current state. So why even bother with recursion? Because many times when recursion is used correctly it's performance can out-strip that of iterative solutions, and recursive functions can also be easier to write (sometimes).
Dynamic Programming
Dynamic programming is a form of recursion, but it's implemented iteratively. Remember our Fibonacci computer above?
F(5) = F(2) + F(1) + F(2) + F(2)+F(1)
F(5) = 3 * F(2) + 2 * F(1)
We have quite a few "over-computations" here. It was only necessary to compute F(2) once, and F(1) once. In this case, it wasn't too computationally tasking to compute these few terms, but there will be some situations where it will become almost impossible to recompute the solutions hundreds of times. So instead of re-computing, we store the answer away.
public static int dynamicFibonacci(int n)
{
int[] prevSolutions = new int[n];
if (n == 1 || n == 2)
{
return 1;
}
prevSolutions[0] = 1;
prevSolutions[1] = 1;
for (int i = 2; i < prevSolutions.length; i++)
{
prevSolutions[i] = prevSolutions[i-1] + prevSolutions[i-2];
}
return prevSolutions[n-1];
}So, take F(5) again. If we did it the recursive way, it would have been 8 calls to recursiveFibonacci. However, here we only computed F(1),F(2),F(3),F(4), and F(5) once. This gain of 3 less calls may not seem like much, but what if we tried computing F(50)? dynamicFibonacci will only compute 50 numbers, but recursiveFibonacci could take over 1000 (of course, I haven't counted so I don't know if it's over 1000 or not).
The last note on dynamic programming is that it only helps in cases were we have tons of over-lap. Remember the recursiveFactorial function? If we called recursiveFactorial(50) and dynamicFactorial(50), they will take roughly the same time to run because we're making the same number of computations. This is because there's no over-lap what-so ever. This is also why sorting algorithms are a poor choice to implement with dynamic programming: if you analyze most sorting algorithms, they have almost no overlapping solutions, thus is a poor candidate for dynamic programming.
Here are some questions about recursion and dynamic programming:
1. Implement the recursiveFactorial method (and you thought I had forgotten to put this in there
)For problems 2-5, use this recursive relationship:
F(1) = 1
F(N) = F(N-1) + N
2. For the given recursive relationship, write a recursive method that will find F(N)
3. What does this recursive relationship mean in iterative terms? Write an iterative solution to this problem.
4. Is this recursive relationship a good candidate for dynamic programming? Why/why not?
5. Is there a better way to solve this problem than the iterative or recursive solutions? What is it (if there is one)? Hint: think of Carl Gauss
Answers are to come
Happy coding