CODEWITHSUNDEEP
cstringfunctionrecursion
chan
chan

Reputation: 29

Recursive function to compare strings without library functions

I'm supposed to write a recursive function in C programming language that checks if string 1 is greater than or equal or less than string 2, and thus returning 1, 0, -1 respectively.

Below is my code that I've written. The program cannot terminate and I cannot figure out the reason. Please give me some advice. Thank you.

int revisedStrcmp(char *s1, char *s2) {
    int i = 0, n = 0, p = 0;

    if (s1[i] == '\0' && s2[i] != '\0') //s1 shorter than s2
        return -1;

    else if (s1[i] != '\0' && s2[i] == '\0') //s1 longer than s2
        return 1;

    else if (s1[i] != '\0' && s2[i] != '\0')  //both not equal to null
    {
        if (s1[i] > s2[i])  n += 1; //s1
        else if (s1[i] < s2[i]) p += 1; //s2
        else
        {
           n += 1; //s1
           p += 1; //s2
        }
        i += 1;
        return revisedStrcmp(s1, s2);
    }
    else    //if s1[i] & s2[i] are null
    {
        if (n > p) //s1 > s2
            return 1;
        else if (n < p)
            return -1;
        else
            return 0;
    }
}

Upvotes: 1

Views: 1848

Answers (5)

user5550963
user5550963

Reputation:

Reason is that s1 and s2 are the same in recursion. What I mean: if you have char *s1 = "Hello"; and char *s2 == Elloh, your recursive calls are the same. you start at the same point, always, you do not pass increments in any way (n, p) so you are basically starting from same point every recursive call. What you can do is increment pointer and here is short solution:

int revisedStrcmp (char *s1, char *s2) {
    if (*s1 == *s2)
        return *s1 == '\0' ? 0 : revisedStrcmp(s1 + 1, s2 + 1);

    return (*s1 > *s2) ? 1 : -1; 
}

or you can do following:

return revisedStrcmp(s1+i, s2+i);

Upvotes: 1

chqrlie
chqrlie

Reputation: 144770

The main problem in your function is you do not pass updated pointers in the recursive call to revisedStrcmp, causing an infinite loop and a potential Stack overflow.

Here is a corrected and simplified version:

int revisedStrcmp(const char *s1, const char *s2) {
    if (*s1 < *s2)
        return -1;
    if (*s1 > *s2)
        return +1;
    // *s1 == *s2
    if (*s1 == '\0')
        return 0;
    return revisedStrcmp(s1 + 1, s2 + 1);
}

There is no need to make special cases for shorter strings because the null terminator can be used in the comparisons.

This particular style of recursion is called tail recursion and will be compiled into a loop by modern compilers.

Note however that for revisedStrcmp() to return the same order as strcmp, the comparisons must be performed on unsigned char values instead of plain char, which can be signed by default on many architectures:

int revisedStrcmp(const char *s1, const char *s2) {
    unsigned char c1 = *s1, c2 = *s2;
    if (c1 < c2)
        return -1;
    if (c1 > c2)
        return +1;
    // c1 == c2
    if (c1 == '\0')
        return 0;
    return revisedStrcmp(s1 + 1, s2 + 1);
}

Upvotes: 2

raijin
raijin

Reputation: 198

Just change the return rStrcmp(s1, s2); to return rStrcmp(s1+i, s2+i);. So that way you are storing the increments of your array position.

Upvotes: 0

Paul Ogilvie
Paul Ogilvie

Reputation: 25286

In the part:

    else if (s1[i] !='\0' && s2[i] !='\0')  //both not equal to null
    {
        if (s1[i]>s2[i])  n+=1; //s1
        else if (s1[i]<s2[i]) p+=1; //s2
        else
        {
           n+=1; //s1
           p+=1; //s2
        }
        i+=1;
        return rStrcmp(s1,s2);

you call rStrcmp(s1,s2); with s1 and s2, however, you have just processed a character. Call rStrcmp(s1+1,s2+1);.

Note: since your function processes only one character per call, you don't need to index the strings with i. It is always 0 except before a return statement, so its value is never used:

int rStrcmp(char *s1, char *s2)
{
    if (*s1 =='\0' && *s2 !='\0') //s1 shorter than s2
        return -1;

    else if (*s1 !='\0' && *s2 =='\0') //s1 longer than s2
        return 1;

    else if (*s1 !='\0' && *s2 !='\0')  //both not equal to null
    {
        if (*s1>*s2)  return 1; //s1
        else if (*s1<*s2) return -1; //s2
        else
            return rStrcmp(s1+1,s2+1);
    }
    else    //if s1[i] & s2[i] are null
    {
        // since both are null, they are the same length and each
        // character was the same: equal
        return 0;
    }
}

Upvotes: 0

Kenyskrachor
Kenyskrachor

Reputation: 21

You are not passing to the function the i, n, p variables. In that way your function will not end, because it will start every time with the counter variables at 0.

Upvotes: 0

Related Questions