Jump to: navigation, search

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
}
Personal tools