# Recursion (programming or math)

**URL:** <https://boards.straightdope.com/t/recursion-programming-or-math/658961>\
**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:** 18\
**Page:** 2

<div class="post-metadata">

**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:13am UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/21 "2013-05-22T01:13:50Z")

</div>

Senegold, thank you. Fibonacci is obvious to me, but problems like this trip me up.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [May 22, 2013, 1:25am UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/22 "2013-05-22T01:25:21Z")

</div>

> [@babygoat666](#):
>
> So, C(n, r) seems to be equal to C(n-1, r) + C(n-1, r-1). Why does that work??

Think about it in terms of the hints that I posted earlier.

---

<div class="post-metadata">

**Author:** ![md2000](https://avatars.discourse-cdn.com/v4/letter/m/73ab20/32.png) [@md2000](https://boards.straightdope.com/u/md2000)\
**Post date:** [May 22, 2013, 3:00pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/23 "2013-05-22T15:00:42Z")

</div>

I think they’re getting there in the posts above, but the ultimate result is to have a definition for C(1,1) or C(n,1) as your stopping condition and work from there…

---

<div class="post-metadata">

**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\
**Post date:** [May 22, 2013, 3:37pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/24 "2013-05-22T15:37:07Z")

</div>

> [@md2000](#):
>
> I think they’re getting there in the posts above, but the ultimate result is to have a definition for C(1,1) or C(n,1) as your stopping condition and work from there…

Wouldn’t you have to start at 0, not 1?

---

<div class="post-metadata">

**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 22, 2013, 3:49pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/25 "2013-05-22T15:49:38Z")

</div>

C(n,0) is undefined, so isn’t a useful place to base things. Essentially it is “how many ways can you choose zero items from n where the order of picking zero things isn’t important”

---

<div class="post-metadata">

**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\
**Post date:** [May 22, 2013, 4:00pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/26 "2013-05-22T16:00:37Z")

</div>

It’s perfectly well-defined. I can choose {}. I don’t have any other options besides {}. The cardinality of {{}} is 1.

---

<div class="post-metadata">

**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\
**Post date:** [May 22, 2013, 4:19pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/27 "2013-05-22T16:19:53Z")

</div>

> [@babygoat666](#):
>
> So, C(n, r) seems to be equal to C(n-1, r) + C(n-1, r-1). Why does that work??

Here’s the explanation, for anyone who can’t figure it out from the already-given hints.[SPOILER]C(n, r) = the number of ways to choose r objects from among n (if order doesn’t matter), or the number of subsets with r members from a set of n elements.

Assume r \<= n, since the subset can’t contain more elements than the larger set it’s a subset of.

If r = 0, the answer is 1: there is 1 possible subset (the empty set).

Otherwise, consider C(n, r) where n and r are both at least 1.

Suppose one of the n members of the set you’re choosing from is Spongebob Squarepants. When you’re looking at possible subsets, they consist of all subsets that **do** include Spongebob plus all subsets that do not include Spongebob.

There are C(n-1, r-1) subsets that do include Spongebob, since you have to choose the r-1 non-Spongebob members of the subset from among the n-1 non-Spongebob elements of the big set.

There are C(n-1, r) subsets that do not include Spongebob, since you have to choose all r members of the subset from among the n-1 non-Spongebob elements of the big set.

Add these together, and you get the total number of subsets: those that do and those that do not include Spongebob as a member.[/SPOILER]

---

<div class="post-metadata">

**Author:** ![md2000](https://avatars.discourse-cdn.com/v4/letter/m/73ab20/32.png) [@md2000](https://boards.straightdope.com/u/md2000)\
**Post date:** [May 22, 2013, 5:22pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/28 "2013-05-22T17:22:44Z")

</div>

> [@Thudlow\_Boink](#):
>
> Wouldn’t you have to start at 0, not 1?

It would be natural to start at 1, but wholly understandable to include 0.

Of course 0! is defined as 1 in violation of the default definition (“product of all positive integers less than or equal to itself and greater than or equal to 1”)

It’s been decades since I did this math, but IIRC the C(n,r) was for n\>=1, r\>=1

---

<div class="post-metadata">

**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\
**Post date:** [May 22, 2013, 5:58pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/29 "2013-05-22T17:58:25Z")

</div>

> [@md2000](#):
>
> It would be natural to start at 1, but wholly understandable to include 0.

To me, it seems more natural to start at 0, because:  
(0) When you’re dealing with sets, the empty set makes a natural starting point or base case.  
(1) The C(n,0) values are included in Pascal’s triangle.  
(2) It preserves the symmetry: the C(n,0) case is the natural counterpart of the C(n,n) case.  
(3) If you think of C(n,r) as giving coefficients in a binomial expansion (as per the binomial theorem), you need to start at 0 to get the complete set.

---

<div class="post-metadata">

**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, 7:04pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/30 "2013-05-22T19:04:54Z")

</div>

Okay, I’ll divulge. If you need the answer, here it is. (Coded in C. Deal with it.)

[spoiler]Made ya look!

Okay, here it is, the full monty. Only look if you’re really at your wits end!

[spoiler]

```auto

/* pascal.c */
/* Generate Pascal's Triangle via recursive function C(n,r) */

#include <stdio.h>
#include <stdlib.h>

int main ( int argn, char* argc[] )
{
    int i, j ;

    for ( i = 0 ; i <= 5 ; i++ ) {
        for ( j = 0 ; j <= i ; j++ ) {
            printf ( "%5d", c(i, j) ) ;
        }
        printf ( "
" ) ;
    }

    exit ( 0 ) ;
}

int c ( int n, int r )
{
    if ( n == 0 || r == 0 || n == r )
        return 1 ;
    else
        return c( n-1, r-1 ) + c( n-1, r ) ;

}

```

[/spoiler][/spoiler]Note, BTW, that this algorithm starts at 0.

ETA: Let the obligatory One True Brace Style Wars commence!

---

<div class="post-metadata">

**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\
**Post date:** [May 22, 2013, 7:55pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/31 "2013-05-22T19:55:49Z")

</div>

Shouldn’t that be in Pascal, **Senegoid**? 🙂

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [May 22, 2013, 8:04pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/32 "2013-05-22T20:04:31Z")

</div>

> [@Senegoid](#):
>
> 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. )

There’s lots of things you can do. You can use C(n, r) = n/(n - r) \* C(n - 1, r), or you can use C(n, r) = (n - r + 1)/r \* C(n, r - 1). Or you can use C(n, r) = n/r \* C(n - 1, r - 1), which, of the “non-branching” recursive approaches, seems simplest to me.

[The nice thing about the branching approach, though, is that you don’t have to deal with division, making it obvious that the outputs will always be whole numbers. The un-nice thing is that you need to use some sort of memoization in the recursion to avoid exponential blow-up in duplicated work. And even with memo-ization, you end up doing quadratically much work compared to the non-branching approach.]

---

<div class="post-metadata">

**Author:** ![md2000](https://avatars.discourse-cdn.com/v4/letter/m/73ab20/32.png) [@md2000](https://boards.straightdope.com/u/md2000)\
**Post date:** [May 22, 2013, 8:20pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/33 "2013-05-22T20:20:43Z")

</div>

> [@md2000](#):
>
> It would be natural to start at 1, but wholly understandable to include 0.

> [@Thudlow\_Boink](#):
>
> To me, it seems more natural to start at 0, because:…

they say a good comedian never explains his jokes…

Natural numbers start at 1 (at least, the way I learned it.)  
Whole numbers start at 0.  
Integers include whole numbers and negative whole numbers.

Logically, your definition, if it depends on recursion, should start at either C(1,1) or C(0,0) depending on whether you want to start whole or au naturel. Then build from there.  
If you were programming your solution, then you have a fixed test (n=1 AND r=1?) to be your stop condition.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [May 22, 2013, 8:28pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/34 "2013-05-22T20:28:11Z")

</div>

Different people use different terminology on this point. As far as I’m concerned, it’s a silly terminology that says “natural” numbers don’t include zero, but “whole” numbers do. Many, many mathematicians, computer scientists, etc., take “natural numbers” to include zero, as this is the set of much more frequent relevance to them than the one excluding zero.

---

<div class="post-metadata">

**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\
**Post date:** [May 22, 2013, 8:31pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/35 "2013-05-22T20:31:07Z")

</div>

With a two-dimensional recursion, you probably don’t want to use a single point as your foundation case. What happens if you miss that point? You can design your recursion branchings so that doesn’t happen, but it’s an extra layer of complication. The formula C(n, r) = n/r \* C(n - 1, r - 1) , for instance, will never reach C(1,1) or C(0,0), except in the trivial case where n = r to start with. It’s usually simpler to define a whole set of foundation cases, such as C(n,0) or C(n,1), which it’s much easier to ensure that you’ll eventually reach.

---

<div class="post-metadata">

**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, 9:00pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/36 "2013-05-22T21:00:41Z")

</div>

> [@Thudlow\_Boink](#):
>
> Shouldn’t that be in Pascal, **Senegoid**? 🙂

There were various bodies of opinion as to what should have been written in Pascal. I always went with the body of opinion that NOTHING should EVER have been written in Pascal.

Of course, those who held that opinion were obviously biased, as they tended to be the same people as those who thought that Pascal was the worst abomination of a programming language ever imagined. There are those, no doubt, who would rather we all program in [Befunge](http://esolangs.org/wiki/Befunge) than Pascal.

---

<div class="post-metadata">

**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\
**Post date:** [May 22, 2013, 9:46pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/37 "2013-05-22T21:46:59Z")

</div>

> [@md2000](#):
>
> they say a good comedian never explains his jokes…
> 
> Natural numbers start at 1

:smack: Yeah, I did miss that.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [May 22, 2013, 9:59pm UTC](https://boards.straightdope.com/t/recursion-programming-or-math/658961/38 "2013-05-22T21:59:02Z")

</div>

> [@Senegoid](#):
>
> There were various bodies of opinion as to what should have been written in Pascal. I always went with the body of opinion that NOTHING should EVER have been written in Pascal.
> 
> Of course, those who held that opinion were obviously biased, as they tended to be the same people as those who thought that Pascal was the worst abomination of a programming language ever imagined. There are those, no doubt, who would rather we all program in [Befunge](http://esolangs.org/wiki/Befunge) than Pascal.

You’re gonna kick yourself when you realize you missed **Thudlow** ’s joke.

[Previous page](https://boards.straightdope.com/t/recursion-programming-or-math/658961.md?page=1)