473,219 Members | 1,838 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,219 software developers and data experts.

questions about combination using recursion

As we know, c(n, k) = c(n-1, k) + c(n-1, k-1).

Also, c(n, 0) = c(n, n) = 1

Therefore, I write down the following function.

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

However, the size of the return value is limited.

If 0 <= n, k <= 1000, the maximum will be c(1000, 500).

Even unsigned long is not enough for c(1000, 500).

How can I improve it?
Nov 13 '05 #1
2 4817
On Wed, 29 Oct 2003 04:54:40 -0800, Larry Niven wrote:

Nice to meet you Larry. Good to see you're programming
these days...
Even unsigned long is not enough for c(1000, 500).
How can I improve it?


unsigned long long may get you a bigger integer type. After
that you have to use a "bignum" library. One such library is:

http://www.swox.com/gmp/

-Sheldon

Nov 13 '05 #2
Sheldon Simms <sh**********@yahoo.com> wrote in message news:<pa****************************@yahoo.com>...

unsigned long long may get you a bigger integer type. After
that you have to use a "bignum" library. One such library is:

http://www.swox.com/gmp/

-Sheldon


Thanks for your suggestion.

If I turn to BigNum, the function will become

BigNum * c(int n, int k){
if(n == k || k == 0){
/* Let BigNum = 1 */
return BigNum;
}else{
return BigNumAdd(c(n-1, k) + c(n-1, k-1));
/* The prototype of the function BigNumAdd will be
* BigNum * BigNumAdd(BigNum *a, BigNum *b) */
}
}

If I want to write my own BigNum for this particular program, which
will make this program small and clear for my other classmates to
discuss, then the BigNum stucture and the function BigNumAdd are the
only two things I need to worry about.

So, can someone tell me how to implement those?
Nov 13 '05 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

8
by: pembed2003 | last post by:
Hi all, As an exercise, I am trying to come up with a function to count the length of a char* string using recursion. I came up with this: int count_length(char* s){ if(s == 0) return 0;...
5
Rooro
by: Rooro | last post by:
For the List class, add a Boolean-valued function that determines whether the data items in the linked list are arranged in ascending order. How can i do this using recursion
3
by: greek | last post by:
Hi! I hav to generate fibonaaci series using recursion: 0,1,1,2,3,5,8,18,21... whr fibonacci(0)=0 fibonacci(1)=1 fibonacci(n)=fibonacci(n-1)+fibonacci(n-2) ive witten the code but having 2...
13
by: Raman | last post by:
Hi All, Could any one tell me How to concatenate two strings using recursion. And also how to trim a string using recursion.(in C, offcourse) Regards, Raman Chalotra
3
by: greek | last post by:
the question is to calculate x^n(x power n) (whr n can be +ve or -ve) by using recursion. the algorithm is x= 1, n=0 1/x^n, n<0 x*x^(n-1), n>0 ...
6
by: Suyash Upadhyay | last post by:
Hi All, As a beginner in Computer Programming, I decided to create Linked List using recursion, but I am not getting right answer. I think it is fundamentally correct, but I am stuck. ...
2
by: guneet bhatia | last post by:
please help with fibonacci series using recursion..
2
by: wagn31 | last post by:
new to python and I have this assingment: I need to write a recursive function that takes paramaters (aString,nTimes) and it needs to print the aString parameter the number of times specified by...
3
by: hemanthappala | last post by:
hello for every body of this network,if any one konw c-program of sum of n terms using recursion please post it
1
isladogs
by: isladogs | last post by:
The next online meeting of the Access Europe User Group will be on Wednesday 6 Dec 2023 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, Mike...
0
by: VivesProcSPL | last post by:
Obviously, one of the original purposes of SQL is to make data query processing easy. The language uses many English-like terms and syntax in an effort to make it easy to learn, particularly for...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
2
by: jimatqsi | last post by:
The boss wants the word "CONFIDENTIAL" overlaying certain reports. He wants it large, slanted across the page, on every page, very light gray, outlined letters, not block letters. I thought Word Art...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.