# Recursion (programming or math) **URL:** \ **Category:** Factual Questions\ **Created:** [May 21, 2013, 9:38pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961 "2013-05-21T21:38:39Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![babygoat666](https://avatars.discourse-cdn.com/v4/letter/b/2acd7d/32.png) [@babygoat666](https://boards.straightdope.com/u/babygoat666)\ **Post date:** [May 21, 2013, 9:38pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/1 "2013-05-21T21:38:39Z")
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! ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [May 21, 2013, 9:51pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/2 "2013-05-21T21:51:21Z")
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. ---
**Author:** ![md2000](https://avatars.discourse-cdn.com/v4/letter/m/73ab20/32.png) [@md2000](https://boards.straightdope.com/u/md2000)\ **Post date:** [May 21, 2013, 9:56pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/3 "2013-05-21T21:56:07Z")
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 ---
**Author:** ![babygoat666](https://avatars.discourse-cdn.com/v4/letter/b/2acd7d/32.png) [@babygoat666](https://boards.straightdope.com/u/babygoat666)\ **Post date:** [May 21, 2013, 10:01pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/4 "2013-05-21T22:01:38Z")
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. ---
**Author:** ![babygoat666](https://avatars.discourse-cdn.com/v4/letter/b/2acd7d/32.png) [@babygoat666](https://boards.straightdope.com/u/babygoat666)\ **Post date:** [May 21, 2013, 10:03pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/5 "2013-05-21T22:03:30Z")
md2000, what made you increment _r_ rather than _n_? Should I think of n as a constant, and if so, why? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [May 21, 2013, 10:44pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/6 "2013-05-21T22:44:03Z")
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? ---
**Author:** ![Senegoid](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/senegoid/32/6606_2.png) [@Senegoid](https://boards.straightdope.com/u/Senegoid)\ **Post date:** [May 21, 2013, 10:49pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/7 "2013-05-21T22:49:00Z")
Are you familiar with [Pascal’s Triangle](https://en.wikipedia.org/wiki/Pascal%27s_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](http://en.wikipedia.org/wiki/Ackerman%27s_function). ---
**Author:** ![Senegoid](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/senegoid/32/6606_2.png) [@Senegoid](https://boards.straightdope.com/u/Senegoid)\ **Post date:** [May 21, 2013, 10:55pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/8 "2013-05-21T22:55:17Z")
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. ) ---
**Author:** ![Senegoid](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/senegoid/32/6606_2.png) [@Senegoid](https://boards.straightdope.com/u/Senegoid)\ **Post date:** [May 21, 2013, 11:06pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/9 "2013-05-21T23:06:14Z")
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. ---
**Author:** ![babygoat666](https://avatars.discourse-cdn.com/v4/letter/b/2acd7d/32.png) [@babygoat666](https://boards.straightdope.com/u/babygoat666)\ **Post date:** [May 21, 2013, 11:15pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/10 "2013-05-21T23:15:11Z")
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. ---
**Author:** ![babygoat666](https://avatars.discourse-cdn.com/v4/letter/b/2acd7d/32.png) [@babygoat666](https://boards.straightdope.com/u/babygoat666)\ **Post date:** [May 21, 2013, 11:18pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/11 "2013-05-21T23:18:09Z")
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. ---
**Author:** ![Francis\_Vaughan](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/francis_vaughan/32/3093_2.png) [@Francis\_Vaughan](https://boards.straightdope.com/u/Francis_Vaughan)\ **Post date:** [May 21, 2013, 11:25pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/12 "2013-05-21T23:25:32Z")
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. ---
**Author:** ![Topologist](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/topologist/32/3208_2.png) [@Topologist](https://boards.straightdope.com/u/Topologist)\ **Post date:** [May 21, 2013, 11:30pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/13 "2013-05-21T23:30:46Z")
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? ---
**Author:** ![babygoat666](https://avatars.discourse-cdn.com/v4/letter/b/2acd7d/32.png) [@babygoat666](https://boards.straightdope.com/u/babygoat666)\ **Post date:** [May 21, 2013, 11:36pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/14 "2013-05-21T23:36:05Z")
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. ---
**Author:** ![Francis\_Vaughan](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/francis_vaughan/32/3093_2.png) [@Francis\_Vaughan](https://boards.straightdope.com/u/Francis_Vaughan)\ **Post date:** [May 21, 2013, 11:40pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/15 "2013-05-21T23:40:11Z")
> [@babygoat666](#): > > What I feel like you’re hinting at is a recursive call within a recursive call? Am I on the right track? That is indeed exactly what a recursive function is. > [@](#): > > Anyway, I’m still totally baffled as to what the stopping case is. How many ways can you pick no objects from n objects? ---
**Author:** ![babygoat666](https://avatars.discourse-cdn.com/v4/letter/b/2acd7d/32.png) [@babygoat666](https://boards.straightdope.com/u/babygoat666)\ **Post date:** [May 21, 2013, 11:42pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/16 "2013-05-21T23:42:09Z")
> [@](#): > > If you have picked one object from the pool, what is the expression for picking the rest? C(n-1,r-1), but how do I combine that number with the fact that I just picked one object already? ---
**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\ **Post date:** [May 21, 2013, 11:58pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/17 "2013-05-21T23:58:18Z")
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? ---
**Author:** ![Francis\_Vaughan](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/francis_vaughan/32/3093_2.png) [@Francis\_Vaughan](https://boards.straightdope.com/u/Francis_Vaughan)\ **Post date:** [May 21, 2013, 11:58pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/18 "2013-05-21T23:58:35Z")
> [@babygoat666](#): > > C(n-1,r-1), but how do I combine that number with the fact that I just picked one object already? 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. ---
**Author:** ![Senegoid](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/senegoid/32/6606_2.png) [@Senegoid](https://boards.straightdope.com/u/Senegoid)\ **Post date:** [May 22, 2013, 12:34am UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/19 "2013-05-22T00:34:28Z")
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. ---
**Author:** ![babygoat666](https://avatars.discourse-cdn.com/v4/letter/b/2acd7d/32.png) [@babygoat666](https://boards.straightdope.com/u/babygoat666)\ **Post date:** [May 22, 2013, 1:11am UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/20 "2013-05-22T01:11:05Z")
So, C(n, r) seems to be equal to C(n-1, r) + C(n-1, r-1). Why does that work?? [Next page](https://boards.straightdope.com/t/recursion-programming-or-math/658961.md?page=2)