Recursive Functions
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7

Thread: Recursive Functions

Hybrid View

  1. #1
    Join Date
    Sep 2007
    Posts
    10

    Smile Recursive Functions

    Hi Guys...

    I am trying to write a recursive function that has two inputs, first and second, which both are strings(from ). The function should print all rearrangements of letters in first, followed by second. For example, if first is the string “CAT” and second is the string “MAN”, then the function would print the strings TACMAN, ATCMAN, CTAMAN, TCAMAN, ACTMAN, and CATMAN.

    And the stopping case of the function occurs when the length of first has zero characters. There are two string members are useful in the program. The following is the precondition and postcondition of these two string functions.

    Code:
     
    void string::instert(size_typr position, size_type number_of_copies, char c);
    postcondition: The specified number of copies of c have been inserted into the string at the indicated position.

    -Existing characters that used to be at or after the given position have been shifted right one spot.

    Code:
    void string::erase(size_type position, size_type n);
    postcondition: n characters have been removed from the string, beginning at the specified position.


    Any ideas how to do this? Thanks for the help.

  2. #2
    Join Date
    Apr 1999
    Location
    Altrincham, England
    Posts
    4,471

    Re: Recursive Functions

    Please demonstrate that you have at least attempted an answer, or ask a specific question if you are stuck. We don't do homework here: we will give specific help, though.
    Correct is better than fast. Simple is better than complex. Clear is better than cute. Safe is better than insecure.
    --
    Sutter and Alexandrescu, C++ Coding Standards

    Programs must be written for people to read, and only incidentally for machines to execute.

    --
    Harold Abelson and Gerald Jay Sussman

    The cheapest, fastest and most reliable components of a computer system are those that aren't there.
    -- Gordon Bell


  3. #3
    Join Date
    Sep 2007
    Posts
    10

    Re: Recursive Functions

    Recursive Thinking

    --------------------------------------------------------------------------------

    Hello All.. Thanks for the Admins and all of your help on this website!

    I am trying to write two recursive functions involving two strings, 1)CAT & 2)MAN.

    My function needs to print out:
    TACMAN
    ATCMAN
    CTAMAN
    TCAMAN
    ACTMAN
    CATMAN

    Two functions are:
    1) void string::insert(size_type position, size_type number_of_copies, char c);
    2) void string::erase(size_type position, size_type n)

    My code with some thinking. I need your help with C++ in coding the part where I have put my logic thinking.


    Code:
    using namespace std;
    
    void string::insert(size_type position, size_type number_of_copies, char c)
    {
    	string s1 = "CAT";
    	string s2 = "MAN";
    	if c[5] == NULL
    
    	//if array c[5] is NULL,
    		//add or insert CAT to first 3
    		//add or insert MAN to last 3
    			//then...
    				//...add TA and insert with CMAN = "TACMAN"
    				//..replace TA with AT and insert with CMAN = "ATCMAN"
    				//..call erase c();
    				//add CT and insert with AMAN = "CTAMAN"
    					//..replace CT with TC and insert with AMAN = "TCAMAN"
    						//..call erase c();
    						//add AC and insert with TMAN = "ACTMAN"
    						//..replace AC with CA and insert with TMAN = "CATMAN"
    
    
    //postcondition: The specified number of copies of c have been 
    //inserted into the string at the indicated position. 
    //Existing characters that used to be at or after the given position have been shifted right 
    //one spot 
    }
    void string::erase(size_type position, size_type n)
    {
    
    	// delete c[]; or c[] = NULL;
    }
    
    
    int main()
    {
    	char c[5];
    
    
      insert(,,); //First function call, so it starts at one        
    }

    Please give me ideas and suggestions. I am looking for specific ideas that can help me put my thinking comments to C++ code.

    Thank you.
    Last edited by GaganW18; November 11th, 2007 at 08:14 PM.

  4. #4
    Join Date
    Apr 1999
    Location
    Altrincham, England
    Posts
    4,471

    Re: Recursive Functions

    OK, first hint: you're going to make life very difficult for yourself if you try to handle the whole string as a unit. Handle them separately and only combine the result when you have to. Even though your approach may well (eventually) work for this one case, you need to be thinking in terms of generalising the problem - what if you change the string lengths? What if you need to permute both strings? A good design choice now can really simplify changes that may be needed in the future.

    so:

    Code:
    string string1 = "CAT";
    string string2 = "MAN";
    
    for each permutation of string1
         print string1 + string2
    Now you only have to figure out how to permute the n characters of string1. Try looking up "permutation algorithms".

    Should you need to extend it to permute string 2 as well, then it becomes:
    Code:
    string string1 = "CAT";
    string string2 = "MAN";
    
    for each permutation of string1
        for each permutation of string2
             print string1 + string2
    See how simple it becomes to extend the original problem?
    Correct is better than fast. Simple is better than complex. Clear is better than cute. Safe is better than insecure.
    --
    Sutter and Alexandrescu, C++ Coding Standards

    Programs must be written for people to read, and only incidentally for machines to execute.

    --
    Harold Abelson and Gerald Jay Sussman

    The cheapest, fastest and most reliable components of a computer system are those that aren't there.
    -- Gordon Bell


  5. #5
    Join Date
    Sep 2007
    Posts
    10

    permute two strings using recursion? help!!!

    I have figured out the "permutation" for one part and I need help with "printing" part.

    Here are the conditions for my functions:

    1) the stopping case of the function occurs when the length of first has zero characters

    2) for void string::insert :
    -The specified number of copies of c have been inserted into the string at the indicated position.
    -Existing characters that used to be at or after the given position have been shifted right one spot.

    3) for void string::erase :
    -n characters have been removed from the string, beginning at the specified position.


    --------------------------------------------------------------------------------
    Last edited by GaganW18; November 15th, 2007 at 09:34 AM. Reason: update my work

  6. #6
    Join Date
    Sep 2007
    Posts
    10

    Thumbs up permute two strings using recursion? (insert & erase)

    Anyone know how I can permute two strings using recursion functions: insert & erase).

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center