Thread: 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.

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.

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.

Hint: store the original size of the string in a local variable that retains its value between function calls.

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.

Originally Posted by w2look

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.