How to reverse a char array with single traversal in place and in memory?
Hint: Use of recursion
How to reverse a char array with single traversal in place and in memory?
Hint: Use of recursion
Hint: Do your own homework. Post code and specific questions if you get stuck.
My solution program:
I am looking for the best solution possible for the question. I was thinking the use of recursion and let compiler use the stack internally. This will also make solution in memory. Can anyone try this approach?Code:void reverse_string(char str[]) { char c; char *p, *q; p = str; if (!p) return; q = p + 1; if (*q == '\0') return; c = *p; reverse_string(q); while (*q != '\0') { *p = *q; p++; q++; } *p = c; return; }
If the char array is of a known length then you don't need recursion for it as it can be solved with a trivial loop over half the items performing swaps as you go. That would make the hint stupid, as you don't need (or bennefit from) recursion.
If however the length is unknown then I'm going to suggest that this technically isn't possible as you first traverse the array in one direction looking for the end, and then you perform a second traversal to perform the reversing. Whether there is recursion involved or not, it's still two passes, no matter how you look at it. You just cant call a pass over the array one direction then the other, a single traversal IMHO.
I therefore declare the question to be faulty.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
I prefer using two pointers or indexes, and a single return line, when startIndex >= endIndex. With every recursion, the values of the array that startIndex and endIndex point to, (or reference), are swapped, and startIndex incremented Also, endIndex is decremented with every recursive call.
Then you are reversing the string, in one pass, and the code is crystal clear. Try that.
Code://before this function is called, startIndex and endIndex refer to the first and last char's void reverseString(char *string, startIndex, endIndex) { //if the index variables have met or crossed, then return, here reverseString(string, startIndex+1, endIndex-1); }
In place, one pass, unknown size.Code:size_t rev( char s[], size_t x ) { if( s && s[x] ) { size_t y = rev( s, x+1 ); if( x < y / 2 ) { char t = s[x]; s[x] = s[y-1-x]; s[y-1-x] = t; } x = y; } return x; } ... rev( myarray, 0 );
Quzah.
Hope is the first step on the road to disappointment.