ARGH.... it's driving me nuts: calculate the binomial coefficient with recursion

[Structural Integrity]

This is some sort of weird school assignment I can't figure out. My brain is about to overheat.
How can I calculate the binomial coefficient with a recursive function? I have a good idea of how to do it in a normal function, but this recursive thing is breaking me up.

binomial coefficient = n! / ((n-k)! * k!)

[BesigedB]

that sounds like something someone in my maths class would say when the teacher is out of the room and he decides to bull**** the class

[queball]

Does it just mean to calculate the factorials with a recursive function?

[Structural Integrity]

Originally posted by queball
Does it just mean to calculate the factorials with a recursive function?

That's what I've been thinking about too, but the assignment isn't clear in that:

Write a recursive function nOverk() that calculates (n Over k) by using recursion.

Further information:
n Over k = (n over (k-1)) * (n-k+1) / k

n Over k = n! / ((n-k)! * k!)

If I read that very litterally I have to write a recursive function nOverk that does the whole trick. However, the second part of the sentence implies I only have to USE recursion, which would mean that using it to calculate factorials would be good enough.

[queball]

That first equation looks good.

[Structural Integrity]

Originally posted by queball
That first equation looks good.

The only problem I see now is when to stop the recursion, and what to return.
Statistics has never been my strongest point.

[Structural Integrity]

aha... I got it!

double nOverK(int n, int k)
{
	if (k == 0)
		return 1;
	else if (n == k)
		return 1;
	else
		return nOverK(n,k-1) * (n-k+1)/k;
}

n has to be bigger than k, else it gives an endless recursion.

\/

[queball]

Originally posted by Structural Integrity

double nOverK(int n, int k)
{
	if (k == 0)
		return 1;
	else if (n == k)
		return 1;
	else
		return nOverK(n,k-1) * (n-k+1)/k;
}

I'd prefer something like...

int nCr_help(int n, int r, int num, int den)
{
	if (k==0 || k==n)
		return num/den;
	else
		return nCr_help(n, k-1, num*(n-k+1), den*k);
}

int nCr(int n, int r)
{
	return nCr_help(n, r, 1, 1);
}

Then you get tail recursion, and only a single division, and no doubles needed!

Edit: actually, yours doesn't really need doubles either.

Edit: why do I always edit my posts?

[W]

int c(int n,int k){return n==k||k==0?1:c(n-1,k-1)+c(n-1,k);}

[Cyp]

int c(int n,int k){return n---k&&k?c(n,k-1)+c(n,k):1;} &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <- This one also works, but is clearer... The above doesn't have "k=0" either.

[W]

Originally posted by Cyp
int c(int n,int k){return n---k&&k?c(n,k-1)+c(n,k):1;} &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <- This one should actually work... The above has "k=0"...??!

Well, not anymore. And I prefer not to obfuscate. I just make it short and sweet and clear.

[Cyp]

Originally posted by W
Well, not anymore. And I prefer not to obfuscate. I just make it short and sweet and clear.

I agree, I prefer not to obfuscate either.

[W]

Originally posted by Cyp
I agree, I prefer not to obfuscate either.

That's not agreeing, that's disagreeing, I was implying yours was obfuscated. The modification of parameters and combined testing with nonobvious precedence of operators makes yours much harder to understand.

[Cyp]

Originally posted by W
That's not agreeing, that's disagreeing, I was implying yours was obfuscated. The modification of parameters and combined testing with nonobvious precedence of operators makes yours much harder to understand.

Well, ok then, a space to avoid any possible confusion...
And I often modify parameters like that, so the computer only has to decrement it once, instead of twice.

int c(int n,int k){return n-- -k&&k?c(n,k-1)+c(n,k):1;}

[W]

Originally posted by Cyp
Well, ok then, a space to avoid any possible confusion...
And I often modify parameters like that, so the computer only has to decrement it once, instead of twice.

int c(int n,int k){return n-- -k&&k?c(n,k-1)+c(n,k):1;}

The computer, if it has any brains at all, should be able to figure that out. My computer does. Worse off, if you have such a stupid computer, perhaps it's too stupid to use registers for the parameters too, and thus you end up decrementing a memory location once, instead of loading and decrementing a register twice, which would be faster.

[Structural Integrity]

eh.... one question.... do you lot write REAL code like that too?
If so, doesn't your head spin around or does you brain start boiling when you are debugging it?

[queball]

Originally posted by W
The computer, if it has any brains at all, should be able to figure that out. My computer does. Worse off, if you have such a stupid computer, perhaps it's too stupid to use registers for the parameters too, and thus you end up decrementing a memory location once, instead of loading and decrementing a register twice, which would be faster.

And Cyp's decrements even for the "leaf" cases where k is n or 0, on a terribly naive compiler.

[Cyp]

int c(int n,int k){return n---k&&k?c(n,k-1)+c(n,k):1;}

00401000 53                   push        ebx
00401001 8B 5C 24 0C          mov         ebx,dword ptr [esp+0Ch]
00401005 57                   push        edi
00401006 8B 7C 24 0C          mov         edi,dword ptr [esp+0Ch]
0040100A 8B C7                mov         eax,edi
0040100C 2B C3                sub         eax,ebx
0040100E 4F                   dec         edi
0040100F 85 C0                test        eax,eax
00401011 74 23                je          00401036
00401013 85 DB                test        ebx,ebx
00401015 74 1F                je          00401036
00401017 8D 4B FF             lea         ecx,[ebx-1]
0040101A 56                   push        esi
0040101B 51                   push        ecx
0040101C 57                   push        edi
0040101D E8 DE FF FF FF       call        00401000
00401022 53                   push        ebx
00401023 57                   push        edi
00401024 8B F0                mov         esi,eax
00401026 E8 D5 FF FF FF       call        00401000
0040102B 83 C4 10             add         esp,10h
0040102E 03 F0                add         esi,eax
00401030 8B C6                mov         eax,esi
00401032 5E                   pop         esi
00401033 5F                   pop         edi
00401034 5B                   pop         ebx
00401035 C3                   ret
00401036 5F                   pop         edi
00401037 B8 01 00 00 00       mov         eax,1
0040103C 5B                   pop         ebx
0040103D C3                   ret

int c(int n,int k){return n==k||k==0?1:c(n-1,k-1)+c(n-1,k);}

00401000 8B 44 24 04          mov         eax,dword ptr [esp+4]
00401004 53                   push        ebx
00401005 8B 5C 24 0C          mov         ebx,dword ptr [esp+0Ch]
00401009 3B C3                cmp         eax,ebx
0040100B 74 27                je          00401034
0040100D 85 DB                test        ebx,ebx
0040100F 74 23                je          00401034
00401011 56                   push        esi
00401012 57                   push        edi
00401013 8D 78 FF             lea         edi,[eax-1]
00401016 8D 43 FF             lea         eax,[ebx-1]
00401019 50                   push        eax
0040101A 57                   push        edi
0040101B E8 E0 FF FF FF       call        00401000
00401020 53                   push        ebx
00401021 57                   push        edi
00401022 8B F0                mov         esi,eax
00401024 E8 D7 FF FF FF       call        00401000
00401029 83 C4 10             add         esp,10h
0040102C 03 F0                add         esi,eax
0040102E 8B C6                mov         eax,esi
00401030 5F                   pop         edi
00401031 5E                   pop         esi
00401032 5B                   pop         ebx
00401033 C3                   ret
00401034 B8 01 00 00 00       mov         eax,1
00401039 5B                   pop         ebx
0040103A C3                   ret

Conclusion: Compiler doesn't make sensible code with either, so should just go for the version which is easier to read, due to the code being shorter, and therefore less code to read.

[W]

Originally posted by Structural Integrity
eh.... one question.... do you lot write REAL code like that too?
If so, doesn't your head spin around or does you brain start boiling when you are debugging it?

The way you write code is just easier for you to understand out of habit.


BTW, doing this with recursion is damn silly. You'll reach the leaf c(n,k) times, in effect adding 1 to a sum until you get the answer All just to avoid worrying about overflow and loss of presision.

[KaneED]

This stuff is absolutely hideous

[at0mic.c0w]

bin :: Int -> Int -> Int
bin _ 0 = 1
bin n k
      | n == k    = 1
      | otherwise = (bin (n-1) k) + (bin (n-1) (k-1))

all hail teh haskell

[queball]

Originally posted by at0mic.c0w

bin n _ = 1

bin n 0 = 1

surely?

[at0mic.c0w]

Originally posted by queball

bin n 0 = 1

surely?

no actually bin _ 0 is what i meant

that happens when the holidays are too long

edit: but yours is correct too

[Cyp]

Originally posted by at0mic.c0w

bin :: Int -> Int -> Int
bin _ 0 = 1
bin n k
      | n == k    = 1
      | otherwise = (bin (n-1) k) + (bin (n-1) (k-1))

all hail teh haskell

fun c(_, 0)=1
  | c(n, k)=if n=k then 1
                   else c(n-1, k)+c(n-1, k-1);

All hail the SML!

[queball]

(define (bin n k)
   (cond ((= k 0) 1)
	 ((= k n) 1)
         (else (+ (bin (- n 1) k)
		  (bin (- n 1) (- k 1))))))

[queball]

Binomial {
s.1 0 = 1;
s.1 s.1 = 1;
s.1 s.2 = <+ <Binomial <- s.1 1> s.2>
             <Binomial <- s.1 1> <- s.2 1>>>;
}

[SilverSmoke]

wtf

[Cyp]

(# c n k
  (? (<= k 0) 1
    (? (>= k n) 1
      (+
        (c (- n 1) (- k 1))
        (c (- n 1) k)
      )
    )
  )
)