CODEWITHSUNDEEP
crecursion
Fouad Wahabi
Fouad Wahabi

Reputation: 804

recursive function which invert a string

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;
}

Upvotes: 0

Views: 226

Answers (3)

el.pescado - нет войне
el.pescado - нет войне

Reputation: 19236

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.

Upvotes: 0

BLUEPIXY
BLUEPIXY

Reputation: 40145

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;
}

Upvotes: 0

NPE
NPE

Reputation: 500683

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:

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

Upvotes: 2

Related Questions