Recently I have been studying recursion; how to write it, analyze it, etc. I have thought for a while that recurrence and recursion were the same thing, but some problems on recent homework assignments and quizzes have me thinking there are slight differences, that 'recurrence' is the way to describe a recursive program or function.
This has all been very Greek to me until recently, when I realized that there is something called the 'master theorem' used to write the 'recurrence' for problems or programs. I've been reading through the wikipedia page, but, as usual, things are worded in such a way that I don't really understand what it's talking about. I learn much better with examples.
So, a few questions: Lets say you are given this recurrence:
r(n) = 2*r(n-2) + r(n-1);
r(1) = r(2) = 1
Is this, in fact, in the form of the master theorem? If so, in words, what is it saying? If you were to be trying to write a small program or a tree of recursion based on this recurrence, what would that look like? Should I just try substituting numbers in, seeing a pattern, then writing pseudocode that could recursively create that pattern, or, since this may be in the form of the master theorem, is there a more straightforward, mathematical approach?
Now, lets say you were asked to find the recurrence, T(n), for the number of additions performed by the program created from the previous recurrence. I can see that the base case would probably be T(1) = T(2) = 0, but I'm not sure where to go from there.
Basically, I am asking how to go from a given recurrence to code, and the opposite. Since this looks like the master theorem, I'm wondering if there is a straightforward and mathematical way of going about it.
EDIT: Okay, I've looked through some of my past assignments to find another example of where I'm asked, 'to find the recurrence', which is the part of this question I'm having the post trouble with.
Recurrence that describes in the best way the number of addition operations in the following program fragment (when called with l == 1 and r == n)
int example(A, int l, int r) {
if (l == r)
return 2;
return (A[l] + example(A, l+1, r);
}
A few years ago, Mohamad Akra and Louay Bazzi proved a result that generalizes the Master method -- it's almost always better. You really shouldn't be using the Master Theorem anymore...
See, for example, this writeup: http://courses.csail.mit.edu/6.046/spring04/handouts/akrabazzi.pdf
Basically, get your recurrence to look like equation 1 in the paper, pick off the coefficients, and integrate the expression in Theorem 1.