|
4 Apr 2003, 15:16
|
#1
|
Rawr rawr
Join Date: Dec 2000
Location: Upside down
Posts: 5,300
|
ARGH.... it's driving me nuts: calculate the binomial coefficient with recursion
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!)
|
|
|
4 Apr 2003, 15:18
|
#2
|
Darling
Join Date: Dec 2000
Location: Edinburgh
Posts: 890
|
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
|
|
|
4 Apr 2003, 15:28
|
#3
|
Ball
Join Date: Oct 2001
Posts: 4,410
|
Does it just mean to calculate the factorials with a recursive function?
|
|
|
4 Apr 2003, 15:37
|
#4
|
Rawr rawr
Join Date: Dec 2000
Location: Upside down
Posts: 5,300
|
Quote:
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:
Quote:
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.
|
|
|
4 Apr 2003, 15:40
|
#5
|
Ball
Join Date: Oct 2001
Posts: 4,410
|
That first equation looks good.
|
|
|
4 Apr 2003, 15:49
|
#6
|
Rawr rawr
Join Date: Dec 2000
Location: Upside down
Posts: 5,300
|
Quote:
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.
__________________
"Yay"
|
|
|
4 Apr 2003, 16:14
|
#7
|
Rawr rawr
Join Date: Dec 2000
Location: Upside down
Posts: 5,300
|
aha... I got it!
Code:
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.
\ /
|
|
|
4 Apr 2003, 17:20
|
#8
|
Ball
Join Date: Oct 2001
Posts: 4,410
|
Quote:
Originally posted by Structural Integrity
Code:
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...
Code:
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?
Last edited by queball; 4 Apr 2003 at 17:25.
|
|
|
4 Apr 2003, 17:21
|
#9
|
Gubbish
Join Date: Sep 2000
Location: #FoW
Posts: 2,323
|
int c(int n,int k){return n==k||k==0?1:c(n-1,k-1)+c(n-1,k);}
Last edited by W; 4 Apr 2003 at 18:14.
|
|
|
4 Apr 2003, 18:07
|
#10
|
∞+♪²
Join Date: Nov 2000
Location: :uo!te]o¯|
Posts: 428
|
int c(int n,int k){return n---k&&k?c(n,k-1)+c(n,k):1;} <- This one also works, but is clearer... The above doesn't have "k=0" either.
Last edited by Cyp; 4 Apr 2003 at 18:21.
|
|
|
4 Apr 2003, 18:11
|
#11
|
Gubbish
Join Date: Sep 2000
Location: #FoW
Posts: 2,323
|
Quote:
Originally posted by Cyp
int c(int n,int k){return n---k&&k?c(n,k-1)+c(n,k):1;} <- 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.
|
|
|
4 Apr 2003, 18:19
|
#12
|
∞+♪²
Join Date: Nov 2000
Location: :uo!te]o¯|
Posts: 428
|
Quote:
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.
|
|
|
4 Apr 2003, 18:22
|
#13
|
Gubbish
Join Date: Sep 2000
Location: #FoW
Posts: 2,323
|
Quote:
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.
|
|
|
4 Apr 2003, 18:28
|
#14
|
∞+♪²
Join Date: Nov 2000
Location: :uo!te]o¯|
Posts: 428
|
Quote:
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;}
|
|
|
4 Apr 2003, 18:42
|
#15
|
Gubbish
Join Date: Sep 2000
Location: #FoW
Posts: 2,323
|
Quote:
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.
|
|
|
4 Apr 2003, 18:47
|
#16
|
Rawr rawr
Join Date: Dec 2000
Location: Upside down
Posts: 5,300
|
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?
__________________
"Yay"
|
|
|
4 Apr 2003, 19:12
|
#17
|
Ball
Join Date: Oct 2001
Posts: 4,410
|
Quote:
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.
|
|
|
4 Apr 2003, 19:40
|
#18
|
∞+♪²
Join Date: Nov 2000
Location: :uo!te]o¯|
Posts: 428
|
int c(int n,int k){return n---k&&k?c(n,k-1)+c(n,k):1;}
Code:
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);}
Code:
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.
__________________
Structural Integrity for Creator - since he'll probably make PA turn 3D.
Wikipedia forum
Note to self - Don't write Chinese letters with bold and italics... 猫
<!--Last incarnation: Nov 2000-->
|
|
|
4 Apr 2003, 20:50
|
#19
|
Gubbish
Join Date: Sep 2000
Location: #FoW
Posts: 2,323
|
Quote:
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.
|
|
|
6 Apr 2003, 22:36
|
#20
|
Motherfracker
Join Date: May 2001
Posts: 2,985
|
This stuff is absolutely hideous
|
|
|
7 Apr 2003, 14:36
|
#21
|
Käptn Karacho
Join Date: Nov 2000
Posts: 1,360
|
Code:
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
__________________
at0mic.c0w - #strategy
Last edited by at0mic.c0w; 7 Apr 2003 at 16:45.
|
|
|
7 Apr 2003, 16:31
|
#22
|
Ball
Join Date: Oct 2001
Posts: 4,410
|
Quote:
Originally posted by at0mic.c0w
|
surely?
|
|
|
7 Apr 2003, 16:42
|
#23
|
Käptn Karacho
Join Date: Nov 2000
Posts: 1,360
|
Quote:
Originally posted by queball
surely?
|
no actually bin _ 0 is what i meant
that happens when the holidays are too long
edit: but yours is correct too
__________________
at0mic.c0w - #strategy
Last edited by at0mic.c0w; 7 Apr 2003 at 16:49.
|
|
|
7 Apr 2003, 17:47
|
#24
|
∞+♪²
Join Date: Nov 2000
Location: :uo!te]o¯|
Posts: 428
|
Quote:
Originally posted by at0mic.c0w
Code:
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
|
Code:
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!
__________________
Structural Integrity for Creator - since he'll probably make PA turn 3D.
Wikipedia forum
Note to self - Don't write Chinese letters with bold and italics... 猫
<!--Last incarnation: Nov 2000-->
|
|
|
7 Apr 2003, 18:09
|
#25
|
Ball
Join Date: Oct 2001
Posts: 4,410
|
heil scheme
Code:
(define (bin n k)
(cond ((= k 0) 1)
((= k n) 1)
(else (+ (bin (- n 1) k)
(bin (- n 1) (- k 1))))))
|
|
|
7 Apr 2003, 18:38
|
#26
|
Ball
Join Date: Oct 2001
Posts: 4,410
|
heil REFAL
Code:
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>>>;
}
|
|
|
7 Apr 2003, 18:46
|
#27
|
Guy next door
Join Date: Feb 2002
Location: The Netherlands
Posts: 4,745
|
wtf
__________________
..look
|
|
|
7 Apr 2003, 19:01
|
#28
|
∞+♪²
Join Date: Nov 2000
Location: :uo!te]o¯|
Posts: 428
|
Hail some language without a name, that I created as a school assignment
Code:
(# c n k
(? (<= k 0) 1
(? (>= k n) 1
(+
(c (- n 1) (- k 1))
(c (- n 1) k)
)
)
)
)
__________________
Structural Integrity for Creator - since he'll probably make PA turn 3D.
Wikipedia forum
Note to self - Don't write Chinese letters with bold and italics... 猫
<!--Last incarnation: Nov 2000-->
|
|
|
|
All times are GMT +1. The time now is 03:26.
| |