Recursive Question

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

31 Replies - 1536 Views - Last Post: 11 December 2010 - 12:50 AM Rate Topic: -----

#1 golfgirl32  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 04-November 10

Recursive Question

Posted 08 December 2010 - 05:17 PM

How do I write a recursive function that counts the number of sequences that sum up to that number (user input)?
Is This A Good Question/Topic? 0
  • +

Replies To: Recursive Question

#2 dorknexus  Icon User is offline

  • or something bad...real bad.
  • member icon

Reputation: 1255
  • View blog
  • Posts: 4,618
  • Joined: 02-May 04

Re: Recursive Question

Posted 08 December 2010 - 05:56 PM

how many summations can be made? any number? in that case, infinite. integers only?
Was This Post Helpful? 0
  • +
  • -

#3 golfgirl32  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 04-November 10

Re: Recursive Question

Posted 08 December 2010 - 08:51 PM

Like say the number is 6 for example...

Then the number of sequences that sum up to 6 is 11 (including 6 itself). This is shown clearly below:

6
5+1
4+1+1
3+1+1+1
2+1+1+1+1
1+1+1+1+1+1
2+2+1+1
3+2+1
4+2
2+2+2
3+3

None of the numbers can be repeated. You can't have 2+2+1+1 and 1+1+2+2 as two different solutions
Was This Post Helpful? 0
  • +
  • -

#4 dorknexus  Icon User is offline

  • or something bad...real bad.
  • member icon

Reputation: 1255
  • View blog
  • Posts: 4,618
  • Joined: 02-May 04

Re: Recursive Question

Posted 09 December 2010 - 07:32 PM

show us what you've tried so far.
Was This Post Helpful? 0
  • +
  • -

#5 golfgirl32  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 04-November 10

Re: Recursive Question

Posted 10 December 2010 - 01:20 PM

I have most everything figured out except the loop. Any suggestions would be helpful

#include <iostream>

using namespace std;

int partition(int n, int max)
{
  if(n==0)
    return(0);
  int ret = 0;
  if(n<=max)
    ret=1;
  for()
  {

  }
  return(ret);
}

int main()
{
    cout << "Enter a number: "  << endl;
    cin >> n >> endl;
    return 0;
}


Was This Post Helpful? 0
  • +
  • -

#6 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Recursive Question

Posted 10 December 2010 - 01:51 PM

The loop is:
.
.
.


In other words, no loop. A loop is iteration. The essence of recursion is that iteration is replaced by a recursive function -- i.e. a function that calls itself.
Was This Post Helpful? 0
  • +
  • -

#7 golfgirl32  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 04-November 10

Re: Recursive Question

Posted 10 December 2010 - 04:16 PM

I know how to do the recursion. I'm not positive how to make it sum up the sequences without repeating. That is what I'm asking for help with.
Was This Post Helpful? 0
  • +
  • -

#8 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1298
  • View blog
  • Posts: 4,468
  • Joined: 19-February 09

Re: Recursive Question

Posted 10 December 2010 - 04:56 PM

Don't know if this pattern will help.

6
5+1
4+2
4+1+1
3+3
3+2+1
3+1+1+1
2+2+2
2+2+1+1
2+1+1+1+1
1+1+1+1+1+1
Was This Post Helpful? 0
  • +
  • -

#9 anonymous26  Icon User is offline

  • D.I.C Lover

Reputation: 0
  • View blog
  • Posts: 3,638
  • Joined: 26-November 10

Re: Recursive Question

Posted 10 December 2010 - 05:02 PM

I don't know why, but Pascal's Triangle came to mind. ;)
Was This Post Helpful? 0
  • +
  • -

#10 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Recursive Question

Posted 10 December 2010 - 05:07 PM

here's the basic idea, if you start with n, you have n choices to make on each step. If you hit a 0 then you have made good choices along the way, if you hit a value < 0 then you have chosen an invalid value somewhere.

int func(int n)
{
        if(n == 0)
            return 1;
        if(n < 0)
            return 0;
        int count = 0;
        for(int i = 1; i <= n; i++)
        {
            count += func(n-i);
        }
        return count;
    }



this will also count the repetitions though, think about how you can eliminate them :)
Was This Post Helpful? 0
  • +
  • -

#11 golfgirl32  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 04-November 10

Re: Recursive Question

Posted 10 December 2010 - 05:49 PM

So I can run the program successfully but after the user inputs the number nothing else happens. This is where I'm totally confused.
Was This Post Helpful? 0
  • +
  • -

#12 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Recursive Question

Posted 10 December 2010 - 05:51 PM

what do you mean by nothing happens. are you calling the method??, are you printing out the return value??
Was This Post Helpful? 0
  • +
  • -

#13 golfgirl32  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 04-November 10

Re: Recursive Question

Posted 10 December 2010 - 06:01 PM

The user is allowed to input the number but then the program ends. Here is my code...

#include <iostream>

using namespace std;

int func(int n)
{
    if(n == 0)
    return 1;
    if(n < 0)
    return 0;
    int count = 0;
    for(int i = 1; i <= n; i++)
    {
        count += func(n-i);
    }
    return count;
}

int main()
{
     int n;

    cout << "Please enter the number: ";
    cin >> n ;
    cout << "\n";

    return 0;
}


Was This Post Helpful? 0
  • +
  • -

#14 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Recursive Question

Posted 10 December 2010 - 06:06 PM

because you're not calling the method

#include <iostream>

using namespace std;

int func(int n)
{
    if(n == 0)
    return 1;
    if(n < 0)
    return 0;
    int count = 0;
    for(int i = 1; i <= n; i++)
    {
        count += func(n-i);
    }
    return count;
}

int main()

     int n;

    cout << "Please enter the number: ";
    cin >> n ;
    cout << func(n) << endl;

    return 0;
}


This post has been edited by mostyfriedman: 10 December 2010 - 06:07 PM

Was This Post Helpful? 0
  • +
  • -

#15 golfgirl32  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 04-November 10

Re: Recursive Question

Posted 10 December 2010 - 06:16 PM

I have just one more problem. I don't want to have multiple sequences counted twice. Like for 6 I don't want 2+2+1+1 and 1+1+2+2 counted as two different sequences. How do I fix that?
Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3