I’m trying to practice my recursion skills and I’m having a bit of trouble framing the following problem:
The formula for computing the number of ways of choosing r different things from a set of n things is the following:
C(n, r) = n!/(r! * (n - r)!)
Discover a recursive version of the C(n, r) formula, and write a recursive method that computes the value of the formula. Embed the method in a program to test it.
So factorials are very easy to understand recursively, but how do you set up your base case(s) and increment when there are 2 variables like this? It should be pretty easy to write, I just can’t wrap my head around the recursive solution to something as complex as this. Any help would be greatly appreciated!
It’s hard to give hints without giving the problem away, but I think this should do it:
Let’s say that the elements of your original set are denoted by x[sub]1[/sub], x[sub]2[/sub], …, x[sub]n[/sub]. You’re looking at a given set. Is x[sub]1[/sub] in or out?
Spend some time thinking about that and you should see how it works and why it’s relevant eventually.
What do you have to do to C(n-1,r) to get C(n,r)?
Do you need to consider (r-1)? Does that make the definition simpler?
Of course, in recursion you need a stopping condition - like a simple definition of f(1) or f(0) that does not involve recursion.
the simplest example, as you mentioned, is:
n! = (n) (n-1)!
1! =1
I understand how the C(n, r) problem/formula works, what I’m trying to do is solve it with a recursive method. In many recursive solutions, it is obvious what is being incremented, and when you have reached a stopping point. In this case, neither is obvious to me.
md2000, what made you increment r rather than n? Should I think of n as a constant, and if so, why?
Again, think of the process of choosing r items to include from a set of n. If you decide to include the first item, what do you have to do make your set? What if you decide not to include the first item?
Are you familiar with Pascal’s Triangle?
If not, read up on it. If yes, think more about how its numbers are derived from other numbers in the triangle that you already have.
Also, you’ve made clear that your problem is specifically developing a recursive function with TWO recursive variables. Without giving away too much of a hint on that, consider studying a different example of that.
Read up on Ackerman’s Function.
A further thought. (Are you doing this for your own practice, or is this a class assignment?)
There are actually TWO ways you might develop a recursive formula for a given C(n, r).
One way is to generate numbers in any given row from the row just above it. (That is the method I hinted at in the above post.)
But you can also do it another way: You can generate any individual row of Pascal’s Triangle from left to right, without referring to the row above it. That is, to compute C(n, r), you must first compute C(n, r-1), but you can develop a whole row without having to compute any C(n-1, anything). This is the method that md2000 appears to have in mind, a few posts above.
(ETA: Sort of. md2000 seems to be saying that you can compute C(n, r) from C(n-1, r), which is the number just above and to the left in Pascal’s Triangle. Whereas, I’m saying you can compute C(n, r) from C(n, r-1), which is the number directly to the left in the same row. I think that’s probably what md2000 meant to write. )
BTW, what programming language are you using?
Modern languages (meaning, a great many high-level languages in the last 40 years or so) spoil you, with support for recursion built in. Do you know anything about how that has to be implemented in the compiled program, with stacks for local variables and return addresses and arguments, and how to deal with function that call themselves.
When I first learned to write recursive functions, it was in an assembly language class. So we had to code all that stuff explicitly. And this was on a computer that had no hardware support for stacks, as all modern computers do.
It was like learning to start a fire by rubbing two sticks together, or doing chemical and engineering computations with pencil-and-paper and some log tables in the back of the book.
Senegold,
Yes I’m familiar with Pascal’s triangle… this gives me a bit more to think about, thank you!
It is not for an assignment. I’m trying to work through a book on data structures and this is the first thing I got hung up on so I wanted to understand all of the exercises before I move on to trees.
It is java, and so far the book seems to be doing a pretty good job of explaining how the call stack works and the memory cost and everything.
As ultrafilter says it is hard to frame a reply without giving the game away.
A combination is how many ways you can pick r objects from a pool of n objects when order doesn’t matter. All you need do is frame the recursion relationship from this.
If you have picked one object from the pool, what is the expression for picking the rest? That gives you the recursion relationship. How you manage the requirement that order is not important adds a little spice to things. You may find working out P(n,r) before tackling C(n,r) helps.
If I’m understanding you correctly, you know what the recursion formula is, but you don’t know how to implement it in a function. You keep referring to incrementing variables, but when implementing the function you should really be thinking of decrementing. Your routine wants to compute C(n,r). What does it need to compute first in order to do that computation? What values of n and/or r would be the base cases where it can just return a known value?
What I feel like you’re hinting at is a recursive call within a recursive call? Am I on the right track?
Anyway, I’m still totally baffled as to what the stopping case is.
That is indeed exactly what a recursive function is.
How many ways can you pick no objects from n objects?
C(n-1,r-1), but how do I combine that number with the fact that I just picked one object already?
Try it experimentally. You know from the principles of recursion that you have to get to a smaller base case. There are two variables here, so see what happens when you plug in C(n-1, r) or C(n, r-1). Try to express C(n, r) in terms of one of those and see what happens. Does C(n, r) equal C(n-1, r) times some quantity? Maybe C(n, r) equals C(n, r-1) plus some quantity? Try different operations and see what the result is. Maybe one of them is simpler than another.
Also, try different base cases. What does C(0, r) equal? How about C(n, 0)? Do you need to go to C(0, 0), or can you stop earlier than that?
Well, you might guess it is the same as say, calculating factorial - which is the same as how many ways there are of picking all n objects from the pool where order matters.
Here’s a simpler case to work out:
Try computing Fibonacci numbers, using a recursive algorithm.
This is a notch more complicated than the recursive method of computing factorials. Think about that.
So, C(n, r) seems to be equal to C(n-1, r) + C(n-1, r-1). Why does that work??