Problem with a recursive partition (number theory) function

Question

Example: Let’s say your user input is 6. Then the number of sequences that sum up to 6 is 11 (including 6 itself). The problem I am having is that it works when the user enters 1 or 6, but if not it is way off and I can't figure out why.

I can give more info on the subject if needed.

#include <iostream>

using namespace std;

int sum(double number, int min, int & counter)
{
    int temp=0, n;
    n=number+temp;

    if (number>=(n/2.0)+.5 && (number!=1))
    {
        number --;
        temp ++;
        while (number>=(n/2.0))
        {
            number --;
            temp ++;
            counter ++;
        }
    }
    else if (number==1)
    {
        counter ++;
        return 0;
    }

    sum(n-1, 1,counter);

    return 0;
}

int main()
{
    int counter=1;
    double number;

    cout << "-------------------------------------------------------\n"
         << "Please enter the number: ";

    cin >> number ;
    cout << "\n";

    if (number!=1)
    {
        sum(number, 1, counter);
    }


    cout << "The total number of combinations that result in a sum of "
         << number << " is: " << counter
         << "\n-------------------------------------------------------\n";

    return 0;
}

possible duplicate of [trying to write a recursive function that counts the number of sequences that sum up to that number C++](http://stackoverflow.com/questions/4384021/trying-to-write-a-recursive-function-that-counts-the-number-of-sequences-that-sum) — Beta, Dec 10 '10 at 07:46

score 1 · Accepted Answer · answered Dec 10 '10 at 07:47

I read wiki article you pointed out, they give some instructions how to build recursive defined function. It looks different then your code. The code below works for me

#include <iostream>

using namespace std;

int sum(int k, int n)
{
    if(k == 1 || n == 1)
        return 1;

    if(k < n)
        return sum (k, k);
    else if (k == n)
        return 1 + sum (k, k-1);
    else
        return sum (k,n-1) + sum (k-n, n);
}

int main (void)
{
    int counter=1;
    double number;

    cout << "-------------------------------------------------------\n"
         << "Please enter the number: ";

    cin >> number ;
    cout << "\n";

    counter = sum(number, number);

    cout << "The total number of combinations that result in a sum of "
         << number << " is: " << counter
         << "\n-------------------------------------------------------\n";

    return 0;
}

You can test this code here

dang one problem is it has to be recursive. EDIT Oh wow i'm retarded link went weird sorry. It is! Thanks for they help this should get me on my way! Really appreciate it! — Zud, Dec 10 '10 at 07:54

Problem with a recursive partition (number theory) function

1 Answers1