Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/forums/cpp/)
-   -   Recursion and Permutations (http://www.go4expert.com/forums/recursion-and-permutations-t19263/)

 neox08 2Sep2009 01:14

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 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```