The C Programming Language, 2nd Edition, by Kernighan and Ritchie
Exercise 4.13 on page 88
Write a recursive version of the function reverse(s) , which reverses the string s in place.
Solution by David Moscoso
#include<stdio.h> #include<string.h> void reverse(char[], int, int); //function prototype int main(void){ char s[] = "hello"; //example string reverse(s, 0, (strlen(s)-1)); //reverse the complete word printf("%s\n", s); return 0; } void reverse(char s[], int l, int r){ //reverse from l(left) to r(right) in array s int c; if (l < r) { reverse(s, l+1, r-1); c = s[l]; s[l] = s[r]; s[r] = c; } }
Solution by Gregory Pietsch
/* EXERCISE 4-13 Gregory Pietsch */ static void swap(char *a, char *b, size_t n) { while (n--) { *a ^= *b; *b ^= *a; *a ^= *b; a++; b++; } } void my_memrev(char *s, size_t n) { switch (n) { case 0: case 1: break; case 2: case 3: swap(s, s + n - 1, 1); break; default: my_memrev(s, n / 2); my_memrev(s + ((n + 1) / 2), n / 2); swap(s, s + ((n + 1) / 2), n / 2); break; } } void reverse(char *s) { char *p; for (p = s; *p; p++) ; my_memrev(s, (size_t)(p - s)); }
Solution by Jesse Weinstein
/* Recursive string reverse function, without using any setup-wrapper function. Released by Jesse Weinstein, Tue Jul 10 12:37:50 2007 */ void shift(char *s); void reverse(char *s); void reverse(char *s) { int len; for (len = -1; s[++len] != '\0'; ) ; if (s[len-1] == '\n') len--; #ifdef DEBUG printf("len:%i, s:%s\n", len, s); #endif if (len > 0) { reverse(&s[1]); } if (len > 1) { shift(s); } #ifdef DEBUG printf("<= len:%i, s:%s\n", len, s); #endif } void shift(char *s) { int i; char tmp; tmp = s[0]; for (i = 0; s[i+1] != '\0'; i++) { s[i] = s[i+1]; } s[i] = tmp; /* i is set to the character before the \0; the last time through the loop sets s[i] to '\0' */ } int main(void) { char in[] = "Hello, world!"; printf("Input: \"%s\"\n", in); reverse(in); printf("Reversed: \"%s\"\n", in); reverse(in); printf("Twice reversed: \"%s\"\n", in); return 0; }
Solution by David Kachlon
These examples are far too complex, here is my basic submission
#include <stdio.h> #include <string.h> int reverse(char v[], int i, int j) { int temp; if(j == 1) return 1; temp = v[i]; v[i] = v[j]; v[j] = temp; reverse(v, ++i, --j); } main() { char test[] = "David"; reverse(test, 0, strlen(test)-1); printf("%s", test); }
Solution by Cheng Qi
Added my simple method
#include <stdio.h> #include <string.h> int reverse(char v[], int index, int length); main(){ char test[] = "iqgnehc"; reverse(test, 0, strlen(test) - 1); printf("reversed string is %s\n: ", test); return 0; } int reverse(char v[], int index, int length){ if(2 * index > length) return 0; char temp; temp = v[index]; v[index] = v[length - index]; v[length - index] = temp; reverse(v, ++index, length); }
Solution by Jesus Alvarez (Category 0)
#include <stdio.h> #include <string.h> void reverse(char [], int); int main() { char tstr[] = "Hello, world!"; printf("%s\n", tstr); reverse(tstr, 0); printf("%s\n", tstr); return 0; } /* I don't really like having the "left" argument, but it is all I * could come up with without putting too much effort into the problem. * and remaining a category 0 solution. */ void reverse(char s[], int left) { int slen = strlen(s)-1; /* -1 is to compensate for \0. */ char buf = s[left]; if (left < slen) { reverse(s, left+1); } if (buf != '\0') { s[slen-left] = buf; } if (left == 0) { /* Once execution reaches this point, it is at the end of the * first recursion and the terminating char must be set to * close the string. */ s[slen+1] = '\0'; } }
Solution by Jose G. López (Category 0)
My modest solution.
/* Recursive version of the funtion reverse, which reverses a string in place. */ #include <stdio.h> #include <string.h> void reverse(char s[], int i, int j); int main(void) { char s[] = "terminal"; int len = (int)strlen(s); printf("original string: %s\n", s); printf("length: %d\n", len); reverse(s, 0, len - 1); printf("reversed string: %s\n", s); return 0; } void reverse(char s[], int i, int j) { char c; if (i < j) { c = s[i]; s[i++] = s[j]; s[j--] = c; printf("i = %d, j = %d\n", i, j); reverse(s, i, j); } }
Solution by Alex Hoang (Category 0)
#include <stdio.h> #include <string.h> /* I noticed the previous Cat 0 solutions relied on supplying extra index * parameters to the function call. In my opinion, a function for reversing * a string should not have any other parameters other than the string itself. * This function relies on static variables to keep track of indices as the * function recurses through the levels. The main routine is for testing only. */ void myreverse(char s[]) { static int start = 0; static int end; int temp; if (start == 0) end = strlen(s) - 1; /* initialize end only when no recursive calls have been made */ if (end - start > 2) { start++; end--; myreverse(s); start--; /* Unwind start and end to start reversing from middle of string. */ end++; /* Start will eventually wind back to 0 to get ready for next string.*/ } /* Swap letters */ temp = s[start]; s[start] = s[end]; s[end] = temp; } main() { char test1[] = "Hello World!"; char test2[] = "abcd"; char test3[] = "ab"; char test4[] = ""; printf("input: \"%s\"\n", test1); myreverse(test1); printf("reversed: \"%s\"\n", test1); myreverse(test1); printf("twice reversed: \"%s\"\n", test1); printf("input: \"%s\"\n", test2); myreverse(test2); printf("reversed: \"%s\"\n", test2); myreverse(test2); printf("twice reversed: \"%s\"\n", test2); printf("input: \"%s\"\n", test3); myreverse(test3); printf("reversed: \"%s\"\n", test3); myreverse(test3); printf("twice reversed: \"%s\"\n", test3); printf("input: \"%s\"\n", test4); myreverse(test4); printf("reversed: \"%s\"\n", test4); myreverse(test4); printf("twice reversed: \"%s\"\n", test4); return 0; }
Solution by Sander Goos (cat 0)
A shorter solution
void reverse(char s[]) { static int i = 0, n; int c = s[i]; if (c) { i++; reverse(s); s[n-i] = c; i--; } else { n = i; } }
Solution by Jrun
Sander Goos's solution above is a beauty. I'm just changing the last bit where the null terminator is found. we don't need to copy null into c; in fact we don't even need to initialise c at the top.
void reverse(char s[]) { static int i = 0, len; if (s[i]) { int c = s[i++]; reverse(s); s[len-i] = c; i--; } else { len = i; } }
- Clever solution, and your changes are helpful, just a warning though that this function isn't thread-safe unless access to len is protected via a mutex. --Laird (talk) 00:03, 11 March 2016 (UTC)
Solution by gbar
This is another take on Sander Goos's solution. I made a slight modification that makes it easier to understand in my mind. (Although others will disagree).
void reverse(char s[]) { static int i,j; if (s[i]) { int c = s[i++]; reverse(s); s[j++] = c; } if (i==j) i=0,j=0; }
Solution by Xggggg
Another version of Sander Goos's solution in which only one static variable is used by harnessing the pointer nature of "s".
void reverse(char* s) { static int i; if (*s) { i++; char c = *s; reverse(s + 1); *(s - i + 1) = c; i -= 2; if (!*(s - i)) i = 0; } }
Solution by Ukolka
Solution using macro
#include <stdio.h> #include <string.h> #define reverse(S) doreverse(S, 0, strlen(S) - 1) /** * doreverse: reverses string s in place * Yes, supplying indexes to "reverse" function is ugly. * But the fact can be hidden with the macro . */ void doreverse(char s[], int first, int last) { char tmp = s[first]; if (first >= last) return; s[first] = s[last]; s[last] = tmp; doreverse(s, first + 1, last - 1); } int main(int argc, char* argv[]) { #define NUM_TESTS 4 char s1[] = ""; char s2[] = "1"; char s3[] = "12"; char s4[] = "Goodbye Cruel World"; char* s[NUM_TESTS] = {s1, s2, s3, s4}; int i = 0; for (i = 0; i < NUM_TESTS; i++) { printf("Original:\t\"%s\"\n", s[i]); reverse(s[i]); printf("Reversed:\t\"%s\"\n", s[i]); reverse(s[i]); printf("Reversed Twice:\t\"%s\"\n", s[i]); } return 0; }
Solution by Kwanghoon Choi
My code is similar to a functional one, which does not use any extra parameters of reverse nor any static variables.
reverse("") = ""
reverse(c) = c
reverse(c+s) = s'+c by
1) reverse the string from the second character
s ' = reverse s
2) shift s' to the left by 1
3) copy the first character c to the last position
#include <stdio.h> #include <string.h> #define MAX_LEN 100 void reverse(char s[]); char tests[][MAX_LEN] = { "abc", "", "Republic of Korea", "Yonsei University" }; int main() { char str[MAX_LEN]; int i; for(i=0; i<sizeof(tests)/MAX_LEN; i++) { strcpy(str, tests[i]); printf("[%s] => ", str); reverse(str); printf("[%s] \n", str); } return 0; } void reverse(char s[]) { int len = strlen(s); if (len == 0) return; else if (len == 1) return; else { // len > 1 int i; char s0 = s[0]; reverse(&s[1]); // shift s[1]~s[len-1] to s[0]~s[len-2] for(i=1; i<len; i++) { s[i-1] = s[i]; } // copy s0 to s[len-1] s[len-1] = s0; } }
Solution by Mohammed Atanane
Since the examples in here are too complex, I thought I would drop my simple solution here
#include <string.h> void swap(int i, int j, char s[]) { int c = s[i]; s[i++] = s[j]; s[j--] = c; if(!(i > j)) swap(i, j, s); } void reverse(char s[]) { int c, i, j; i = 0; j = strlen(s) - 1; swap(i, j, s); }
Solution by menonsahab
/* The criteria used to decide what arguments to send to a function is "All arguments must be uniquely important", i.e. 1) Never send an argument that is not used by the function 2) Never send an argument that can be deduced by making use of other arguments The non-recursive solution given in K&R is the best and most efficient, yet simple way of reversing a string in place. Using recursion in problems where it simply doesn't "belong" is not recommended. So in this question the user should only have to send one argument, a pointer to the first element of the string. Life becomes easy when we try to send the length of the string as well. But since it is deducible from the first argument it should not be sent. I have written three solutions highlighting a different concept in each */ /* Soultion 1: User passes 2 pointers, one to the first element of the string and one to the last. This solution obviously violates the second rule because the pointer to the last element can be deduced by the pointer to the first element. */ #include <stdio.h> #include <string.h> void reverse(char *p, char *q) { if(q + 1 == p || p == q) return; int c; c = *p; *p = *q; *q = c; reverse(p+1, q-1); } int main() { char str[] = "abc"; reverse(str, str + strlen(str) - 1 ); printf("%s\n", str); return 0; } /* Solution 2: User passes 2 arguments. Pointer to first element of string and length of string. This solution also violates the second rule because the length of the string can be deduced by the pointer to the first element. */ #include <stdio.h> #include <string.h> void reverse(char *p, int len) { if(len <= 0) return; char *q; q = p + len - 1; int c; c = *p; *p = *q; *q = c; reverse(p+1, len - 2); } int main() { char str[] = "abc"; reverse(str, strlen(str)); printf("%s\n", str); return 0; } /* Solution 3: User passes just the pointer to the first element of the string. This solution complies with both rules.*/ #include <stdio.h> #include <string.h> void reverse(char *s) { static int left = 0, right; if(left == 0) right = strlen(s) - 1; if(right - left <= 1) return; int temp; temp = s[left]; s[left] = s[right]; s[right] = temp; left++; right--; reverse(s); } int main() { char str[] = "abc"; reverse(str); printf("%s\n", str); return 0; }
Full program, strictly conforming C90; public domain; past reviewers: none; current reviews:
Laird 
(failed behaviour inspection, compilation);
Solution by Sam Smolkin
/* Solution to 4.13: reverse a string in place using a recursive function. This simple solution uses a static internal variable to avoid the need to call reverse() with additional arguments or to write helper functions (as one might do in other languages, like Scheme), because you can't hide them in other functions in C. */ #include <stdio.h> #include <string.h> #define MAXLEN 100 void reverse(char []); int main(void) { char input[MAXLEN]; while (fgets(input, MAXLEN, stdin) != NULL) { if (input[strlen(input) - 1] == '\n') { input[strlen(input) - 1] = '\0'; /* cut off terminating \n */ } printf("\"%s\" in reverse is ", input); reverse(input); printf("\"%s\"\n", input); } return 0; } void reverse(char s[]) { size_t len = strlen(s); static int offset = 0; char tmp; if (offset < (int) len / 2) { tmp = s[offset]; s[offset] = s[len - (offset + 1)]; s[len - (++offset)] = tmp; reverse(s); } else { offset = 0; /* After last recursive call, reset for calls on new strings */ } }
Laird's explanation of review failing menonsahab's third solution
menonsahab, I've given your third solution a failed review because your use of "static" is inappropriate: it makes this function usable only once. This can be seen if you edit the contents of your main function to be this:
char str[] = "abc"; char str2[] = "xyz"; reverse(str); printf("%s\n", str); reverse(str2); printf("%s\n", str2); return 0;
This program will now output:
cba xyz
i.e. the second string is not reversed. Why not? Because the static variables do not get reset for the second call of reverse from main. So, it seems that string length cannot be deduced from a pointer alone when the function is recursive, and your solutions #1 and #2 are the way to go.
Solution by Amrgrn
This is the most succinct category 0 solution I was able to come up with. It maintains "reverse(s)" that the book asks for and resets i and j at the end to 0 to avoid the "static" problem menonsahab is having with subsequent function calls.
#include <string.h> void reverse(char s[]) { static int i = 0, j = 0; char c; if (j == 0) j = strlen(s) - 1; if (i < j) { c = s[i]; s[i++] = s[j]; s[j--] = c; reverse(s); } i = 0; j = 0; }
menonsahab's original remarks (prior to the review)
/* (menonsahab's) Remarks on solutions by other authors that I could understand: Alex Hoang: My solution 3 is basically an updated version of your solution. Why are you going to the middle and then beginning the swapping operation and going towards the ends, rather than just start swapping from the ends and going to the middle? Ukolka: I love your solution. The function that you've written does not satisfy both rules because you're sending in the length of the string when it can be deduced by the pointer to the first element, but you hide that detail behind your macro making the user think that they are supplying only the argument that is necessary. Smart move. David, Cheng, Jose, Atanane: Ideally this function should have just one argument. My solution 3 uses just one argument. My solution 1 and solution 2 use two arguments each. This methodology is inefficient. What's common in all of your solutions is that you are using three arguments. You simply don't need that many arguments. But I respect the effort. I think this question was a good academic exercise and the take away is that recursion should only be used where it "belongs". Quoting K&R(Chapter 4 Pg 88) "Recursion may provide no saving in storage, since somewhere a stack of the values being processed must be maintained. Nor will it be faster." I usually use recursion only when there is a clear logical link that the function can not move forward unless it invokes itself on a smaller input (so that it converges). In fact right now the only time I can remember using recursion is when I was writing a function to compute the determinant of a square matrix. The determinant of a square matrix is directly dependent on the determinant of its co-factors. It's the kind of question where recursion is the only way to go. */
Solution by TheoKows
int _reverse(char s[], int i); void reverse(char s[]) { _reverse(s, 0); return; } //returns the pointer at which the next char is to be written int _reverse(char s[], int i) { char save = s[i]; //base case: \0 if(save == '\0') return 0; //make recursive call int write_on = _reverse(s, i + 1); //write char s[write_on] = save; return write_on + 1; }
Solution by Roberto Kok
void reverse(char s[]) { char c; static int i = 0, len = NULL; if (i == 0) len = strlen(s); int j = len - (i+1); if (i < j) { // Swap outer letters and move further inwards c = s[i]; s[i++] = s[j]; s[j] = c; reverse(s); } else { // Reset for next call i = 0; len = NULL; } }
Solution by Wulf
Not using any extra arguments or the strlen function
size_t reverse(char *s) { char c = *s; // Remember first char if (! c) return 0; // don't reverse empty string size_t l = reverse(s + 1); // recurse for (size_t i = 0; i < l; ++i) s[i] = s[i + 1]; // shift string one to left s[l] = c; // add last char after shifting return l + 1; // return number of reversed chars }
Solution by anonymous
It turns out my code is very similar to Amrgrn's solution... I guess great minds think alike.
#include <stdio.h> #include <string.h> // for strlen /* Exercise 4-13. Write a recursive version of the function reverse(s), which reverses the string s in place. */ void reverse(char s[]); int main() { char s[] = "Step on no pets!"; printf("%s\n", s); reverse(s); printf("%s\n", s); reverse(s); printf("%s\n", s); return 0; } // reverse strings in place void reverse(char s[]) { static int i = 0, j = 0; // static vars are tricky in recursion. Don't forget to reset them when the original function call is about to end! if (j == 0) // since you can't set a static variable to a dynamic value, this if statement is necessary j = strlen(s) - 1; if (i < j) // once i is >= j, string is reversed so don't call reverse anymore and let everything return { int temp = s[i]; // hold temp value s[i++] = s[j]; // swap i with j then increment i s[j--] = temp; // swap j with original i then decrement j reverse(s); // swap the next chars in s } i = j = 0; // resets i and j for future calls to reverse }
