Recursion and Permutations

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

  1. neox08

    neox08 New Member

    Joined:
    Sep 1, 2009
    Messages:
    1
    Likes Received:
    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
    
    
    
    
    Thanks in advance for your help! :happy:
     
  2. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    Try starting the k loop at n instead of 1.
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice