Remove all occurrences of character x from a given string recursively-CodePudding

I have written two solutions to this problem one with the head recursion and the other with the tail recursion. One with the head recursion passes all the test cases but the solution with tail recursion is missing one case. I am not able to figure out which case I am missing. Can someone please help me here?

One with head recursion

void removeX(char input[]) {
    if (input[0] == '\0')
        return;

    removeX(input 1);

    if (input[0] == 'x') {
        strcpy(input, input 1);
        removeX(input);
    }

}

One with tail recursion

void removeX(char input[]) {
    if (input[0] == '\0')
        return;

    if (input[0] == 'x') {
        strcpy(input, input 1);
        removeX(input);
    }

    removeX(input 1);
}

P.S. The program is supposed to remove all character 'x' from the input string.

Example test cases:

input -----------------> output

xxxxxss ----------------> ss

aaaxxx ----------------> aaa

Now these are simple test cases in which both the solutions with head and tail recurison gives correct answers. But, there are some test cases for which tail recursion fails and I am trying to figure out in what are those cases and why does it fail.

CodePudding user response：

Both functions have undefined behavior because the arrays passed to strcpy should not overlap: change strcpy(input, input 1); to

memmove(input, input   1, strlen(input   1)   1);

Furthermore, both functions have the same code, which is not tail recursion. They recurse twice on each occurrence of x, which is either redundant or incorrect if the last character in the string is an x.

Here is a modified version with tail recursion:

void removeX(char *input) {
    if (input[0] == '\0')
        return;

    if (input[0] == 'x') {
        memmove(input, input   1, strlen(input   1)   1);
        removeX(input);
    } else {
        removeX(input   1);
    }
}

Using recursion for this type of problem is not idiomatic in C. A simple loop is preferred, with linear time complexity instead of potential quadratic time for strings with long sequences of x:

void removeX(char *input) {
    char *p = input;
    while ((*p = *input  ) != '\0') {
        if (*p != 'x')
            p  ;
    }
}