recursive function which invert a string

Question

I wanna make a recursive function which invert a string so i tried this code but it doesn't work correctly . I try to explain my code :

-I made a function which called 'concat' , this function took tow strings as arguments and return a string after the concatunation

-In the 'inv' function which is concerned to invert a string taken as an argument , i tried to concatinate in each loop the i-th caracter whith the previous .

#include <stdio.h>
#include <string.h>

char *concat(char *ch1, char *ch2)
{
  char *ch3 = malloc((strlen(ch1) + strlen(ch2) + 1) * sizeof(char));
  strcat(ch1, ch2);
  strcpy(ch3, ch1);

  return (ch3);
}

char *inv(char *ch1, int i, char *ch2)
{
  if (i == 0)
  {
    strncat(ch2, ch1, 1);
    return ch2;
  }

  if (i > 0)
  {
    return concat(&ch1[i], inv(ch1, i - 1, ch2));
  }
}

int main(int argc, char *argv[])
{
  char ch1[10];
  char ch2[10];
  strcpy(ch2, "");
  scanf("%s", ch1);
  printf("%s", inv(ch1, strlen(ch1) - 1, ch2));
  return 0;
}

"doesn't work correctly" is not a helpful description. What exactly is the problem? — Oliver Charlesworth
– Oliver Charlesworth, Commented Dec 28, 2013 at 13:36
@janisz But this is a void function and it makes the rversed string in a file , but i need a char * function which returns the string revesed — Fouad Wahabi
– Fouad Wahabi, Commented Dec 28, 2013 at 13:47

NPE · Accepted Answer · 2013-12-28 13:52:17Z

2

This is way more complicated than it needs to be. Simply pass two pointers to the function: one pointing to the first character, and one pointing to the last. In the function, swap the two pointed-to characters, and call the function recursively (obviously with a suitable base case to terminate the recursion).

P.S. If you just need to print out the string, and don't need to store it, then the solution is even simpler, and consists of two steps:

Print the reverse of the string excluding the first character;
Print the first character.

edited Dec 28, 2013 at 13:52

answered Dec 28, 2013 at 13:37

NPE

503k114 gold badges970 silver badges1k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Fouad Wahabi Over a year ago

Please sir can you more explain , and if you can give an example :)

Fouad Wahabi Over a year ago

The problems is that i need to store the reversed string :/

BLUEPIXY · Accepted Answer · 2013-12-28 15:19:49Z

0

I tried to rewrite correctly in your policy.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char *concat(char ch, char *str){
    char *cats = malloc(1 + strlen(str) + 1);
    *cats = ch;
    strcpy(cats + 1, str);
    free(str);//str is created by malloc

    return cats;
}

char *inv(char *str, int last){
/*
    if (last == 0)
        return concat(str[0], calloc(1, 1));//calloc(1,1) meant ""

    if (last > 0)
        return concat(str[last], inv(str, last - 1));
*/
    return concat(str[last], (last ? inv(str, last - 1) : calloc(1,1)));
}

int main(){
    char str[10], *p;
    scanf("%s", str);
    printf("%s", p=inv(str, strlen(str) - 1));
    free(p);
    return 0;
}

answered Dec 28, 2013 at 15:19

BLUEPIXY

40.2k7 gold badges37 silver badges73 bronze badges

3 Comments

el.pescado - нет войне Over a year ago

Everytime inv calls inv, you leak memory.

BLUEPIXY Over a year ago

@el.pescado no. where ?

el.pescado - нет войне Over a year ago

OK, now I see that concat frees its 2nd argument.

el.pescado - нет войне · Accepted Answer · 2013-12-28 17:58:18Z

If you want to reverse string in-place, you can just swap first and last character, then call your function recursively for the rest of characters:

[a b c d e]
 e[b c d]a
 e d[c]b a

Here is sample implementation:

/* Reverse a string, n is string length */
void reverse (char *str, size_t n)
{
    /* Terminate recursion - one character string
       is already reversed */
    if (n <= 1) {
        return;
    }

    /* swap first and last character */
    swap(str, 0, n-1); // TODO: implement

    /* Reverse "inner" string. "Inner" string
       starts one character after original string
       and ends one character before, thus is
       2 characters shorter */
    reverse (str+1, n-2);
}

If you want to return new string, you can either duplicate input string and perform reverse in-place, or modify function to operate on two distnct buffers, input and output.

Collectives™ on Stack Overflow

recursive function which invert a string

3 Answers 3

2 Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related