# Recursion and Permutations

Discussion in 'C++' started by neox08, Sep 1, 2009.

1. ### neox08New Member

Joined:
Sep 1, 2009
Messages:
1
0
Trophy Points:
0
Hi, I need some serious help with permutations and recursion. I understand how both work together, but I need some help with the following.

Basically the main function asks for a user entered number, and the recursion function takes that number and sees how many combinations of sums add up to that number. It then returns that number, which is count in my program below, and prints it out. I have it working to print all the numbers including permutations such as:

user entered number = 3 so with permutations (1,2) = 3, (2,1) = 3, (1,1,1) = 3. So the returned count would be 3.

What I also need the program to do is, without taking out the permutations, have it also find without permutations and return that number as well as with permutations. For example:

user entered number = 3 so without permutations (1,2) = 3, (1,1,1) = 3. So the returned count would be 2.

I must be able to do all this within a single function called recursion and output both permutations and without permutations in the main function.

Here is the working code I have for 'with permutations':

Code:
```#include <iostream>
using namespace std;

/**Recursive function which checks the of numbers (permutations included) to
* count how many choices of sums add to the user-entered number.
* @param n An int type user-entered number from the main function
* @pre The main function prompts the user for an integer and stores it as number.
*      The function recursion takes that input and finds all possible sums, including
*      permutations. The recursion function has two base cases that return set answers,
*      and the rest is calculated through recursion by putting k into the function
*      call. It goes through the for loop and counts each one while using the count+=
*      to keep track of the count.
* @post After the pre-condition, it returns the number of sums that add up to the user
*       inputed number, which is equal to count. The main function then prints out
*       the returned number equal to count in the recursion function.
*/

int recursion(int n) //Recursion Function
{
int count = 0; // Counter with Permutations
int count2 = 0; // Counter without Permutations

if(n == 1)  //Base Case:1
{
return 0;
}  // end if

if(n == 2)  //Base Case:2
{
return 1;
}  // end if

for(int k = 1; k < n; k++)
{
int x = n-k;
count++;
count+= recursion(k); //Recursive Call
}  // end for

return count;
}  // end recursion

int main()  //Used to get user-input and call recursion function
{
int number; //User-entered number

cout << "Please choose a number: ";
cin >> number;

int returnedValue = recursion(number); // Function Call to recursion

cout << "There are " << returnedValue << " possible sums." << endl; //Display Number

}  // end main

```

Joined:
Aug 6, 2004
Messages:
3,009