Recursion and Permutations
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 userentered number.
* @param n An int type userentered 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 precondition, 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 = nk;
count++;
count+= recursion(k); //Recursive Call
} // end for
return count;
} // end recursion
int main() //Used to get userinput and call recursion function
{
int number; //Userentered 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
Thanks in advance for your help! :happy:
