# Recursive Question

• (3 Pages)
• 1
• 2
• 3

## 31 Replies - 2199 Views - Last Post: 11 December 2010 - 12:50 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=204444&amp;s=0746a35a4ad09a76c1719e6136d6d43b&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 golfgirl32

• New D.I.C Head

Reputation: 0
• 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

Reputation: 1272
• Posts: 4,625
• 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?

### #3 golfgirl32

• New D.I.C Head

Reputation: 0
• 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

### #4 dorknexus

Reputation: 1272
• Posts: 4,625
• Joined: 02-May 04

## Re: Recursive Question

Posted 09 December 2010 - 07:32 PM

show us what you've tried so far.

### #5 golfgirl32

• New D.I.C Head

Reputation: 0
• 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;
}

```

### #6 r.stiltskin

• D.I.C Lover

Reputation: 2032
• Posts: 5,435
• 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.

### #7 golfgirl32

• New D.I.C Head

Reputation: 0
• 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.

### #8 #define

• Duke of Err

Reputation: 1853
• Posts: 6,671
• 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

### #9 anonymous26

• D.I.C Lover

Reputation: 2
• 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.

### #10 mostyfriedman

• The Algorithmi

Reputation: 729
• 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

### #11 golfgirl32

• New D.I.C Head

Reputation: 0
• 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.

### #12 mostyfriedman

• The Algorithmi

Reputation: 729
• 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??

### #13 golfgirl32

• New D.I.C Head

Reputation: 0
• 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;
}

```

### #14 mostyfriedman

• The Algorithmi

Reputation: 729
• 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

### #15 golfgirl32

• New D.I.C Head

Reputation: 0
• 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?