Another String Problem

This is a discussion on Another String Problem within the C Programming forums, part of the General Programming Boards category; I am not looking for a coded solution! Please just point me in the direction of how to fix what ...

  1. #1
    Registered User w2look's Avatar
    Join Date
    Nov 2008
    Posts
    31

    Another String Problem

    I am not looking for a coded solution!

    Please just point me in the direction of how to fix what I am doing wrong if you can.

    I am working on a project for class to reverse a string. I have already written the
    iteration version of the function and it works great. However, I now have to write it
    using recursion and I am stuck!

    I know how to simply use recursion to print out the string in reverse, but we need
    to actually reverse the string in memory using recursion not just print it in reverse.

    Here is the code I have so far:

    Code:
    //prototypes 
    void Reverse(char *ptrA);
    void RecursiveReverse(char *ptrA);
    
    //call in main
    Reverse(Array1);
    RecursiveReverse(Array2);
    
    /* Reverse the contents of a char array
    Input: a pointer to a char array
    Output: the contents of the array in reverse order
     */
    void Reverse(char *ptrA)
    {
       char temp;
       char  *pStart = ptrA;
       char  *pEnd = ptrA;
    
       while ( *pEnd != NULL)	// assume char *pEnd ends with '\0'
       {
          pEnd ++;				// count the values in the array
       }
       pEnd--;					// determine the proper length of the array because indexes start at zero
       
       while ( pStart < pEnd )	// this loop swaps the values and reverses the array
       {
          temp = *pStart;
          *pStart = *pEnd;
          *pEnd = temp;
          pStart ++;
          pEnd--;
       }
    
    }
    
    /* Reverse the contents of a char array using recusion
    Input: a pointer to a char array
    Output: the contents of the array in reverse order
     */
    void RecursiveReverse(char *ptrA)
    {
    	char temp;
    	int size;
    	char *pStart;
    	char *pEnd;
    	
    	pStart = ptrA;
    	size = strlen(pStart);
    	pEnd = pStart + (strlen(pStart)-1);
    
    	if(pStart >= pEnd)	/* base case */
    	{
    	return;
    	}
    	else				//we want to swap
    	{
    		temp = *pStart;
    		*pStart = *pEnd;
    		*pEnd = temp;
    		pStart = pStart + 1;
    		RecursiveReverse(pStart);	/* recursive call */
    	}
    }

    Right now, it is only moving the last value in the char array to the front.

    All Help is appreciated.

  2. #2
    Registered User w2look's Avatar
    Join Date
    Nov 2008
    Posts
    31

    A little more Info

    This is what the constraints of the project are:

    Write a function called Reverse that accepts as a parameter a char array (or char pointer)
    and returns a void. The function reverses the contents of the array (or string) being passed.
    Example: the string "Hello" will be reversed to "olleH". You have to be careful about the '\0'
    symbol to keep it at the end of the array and watch out for odd and even length strings.

    Test your function and display the string (array) before and after it is reversed.

    Repeat this function using recursion. Name your function RecursiveReverse.

    IMPORTANT: The function does NOT print the string in reverse, it actually reverses it in memory.

  3. #3
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    As a first step spend time in preparing the algorithm. Once you have the algorithm down, coding the recursive function becomes a much easier task.

  4. #4
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Hint: store the original size of the string in a local variable that retains its value between function calls.

  5. #5
    Registered User w2look's Avatar
    Join Date
    Nov 2008
    Posts
    31
    Sometimes you just have to walk away from the computer and clear your head.

    The solution came to me as I was cooking breakfast this morning.

    You have to pass it two pointers. One to the start and one to the end.

    Do the swap, increment the start, decrement the end and pass them back.

    Code:
    /* prototypes */
    void RecursiveReverse(char *ptrA, char *ptrB);
    
    //call in main
    RecursiveReverse(Array2, (Array2 + (strlen(Array2) - 1)));
    
    /* Reverse the contents of a char array using recusion
    Input: a pointer to a char array and a pointer to the end of that array
    Output: the contents of the array in reverse order
     */
    void RecursiveReverse(char *ptrA, char *ptrB)
    {
    
        char temp;            //needed for the swap
        char *pStart;        //pointer to start of array
        char *pEnd;            //pointer to end of array
    
        pStart = ptrA;
        pEnd = ptrB;
    
        if(pStart >= pEnd)    // base_case if the pointers meet or overlap we're done
        {
        return;
        }
        else                //we want to swap
        {
            temp = *pStart;        //perform the swap
            *pStart = *pEnd;
            *pEnd = temp;        
            pStart++;            //increment the start position
            pEnd--;                //decrement the end position
            RecursiveReverse(pStart, pEnd);        //recursive call with the new pointer values
        }
    }
    It works great! Thanks to everyone who gave advice and tried to help.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,749
    That is good. Now, simplify it. Note that you never use ptrA and ptrB in the function other than to assign their values to pStart and pEnd. Perhaps you can do with just one pair of pointers? Instead of the if block in which you return, could you just have an if block in which you perform the swap and recursive call? Instead of incrementing pStart and decrementing pEnd, could you just call RecursiveReverse() with the appropriate arguments?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Quote Originally Posted by w2look View Post
    You have to pass it two pointers. One to the start and one to the end...
    IIRC the requirement was to pass a single char pointer as an argument to the recursive function.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 8
    Last Post: 04-25-2008, 02:45 PM
  2. String issues
    By The_professor in forum C++ Programming
    Replies: 7
    Last Post: 06-12-2007, 09:11 AM
  3. Custom String class gives problem with another prog.
    By I BLcK I in forum C++ Programming
    Replies: 1
    Last Post: 12-18-2006, 02:40 AM
  4. Compile Error that i dont understand
    By bobthebullet990 in forum C++ Programming
    Replies: 5
    Last Post: 05-05-2006, 09:19 AM
  5. Replies: 4
    Last Post: 03-03-2006, 01:11 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21