Compare 2 string using recursion....HEADACHE...PAINFUL

This is a discussion on Compare 2 string using recursion....HEADACHE...PAINFUL within the C Programming forums, part of the General Programming Boards category; How can i compare 2 string using recursion... If string1 is started with string2 then return 1 else return 0 ...

  1. #1
    Registered User
    Join Date
    Mar 2012
    Location
    Hong Kong
    Posts
    13

    Post Compare 2 string using recursion....HEADACHE...PAINFUL

    How can i compare 2 string using recursion...

    If string1 is started with string2 then return 1
    else return 0
    (assume both of strings are in same case and valid.)

    e.g. string1 = hello guy; string2 = hello; <<< return 1
    string1 = hello guy; string2 = ello; <<< return 0;

    here is my recursion segment... I tried many times but still headache... I have no idea...

    Code:
    int compareStr(char string1[], char string2[]) {
       int s1Found, s2Found;
    
    
       if (string1 == NULL || string2 == NULL){
          printf("NULL pointer !\n");
          return -2;
       }
       else if (string1[0] == '\0' || string2[0] == '\0'){
          return -1;
          printf("Empty String !\n");
       }
       else{
          return s1Found = 1 + compareStr(&(string1[1]), &(string2[1])); 
       }
    }

  2. #2
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    How about you stop coding and start thinking beforehand. You will then notice that the human brain does a recursive comparison of strings.
    If I give you:
    string1 = "alskdjqwoiejhqwoejqweoqwjeqwlekqwjeoqwiej"
    string2 = "alskweqwoejqwioejqwoejqweoqwjieqwoiejqwie"

    How would you logically go about checking if they are the same? Describe the steps.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,258
    Since you are allowed to assumed that both of the strings are valid, you can ditch the comparison with NULL for now to simplify.

    Think: what are the base cases? What should you return for the recursive step?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Mar 2012
    Location
    Hong Kong
    Posts
    13
    1. start comparing from left to right
    2. if match, then check next one until not match "alsk"
    3. return the result

    right?

  5. #5
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Well yes, but that is not broken down enough.


    Step1: You start by looking at the first letter in both strings.

    Step2: If it is not the same, strings are not equal.

    Step3: If they are the same:

    Step 3a: Are there more characters?

    If not then they are equal.

    Otherwise go to step 4.
    Step4: Then consider your strings from the next character (i.e. these are your new strings). Go to Step1.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,258
    It sounds like you are thinking iteratively.

    I would expect something like:
    If the first character of string2 is the null character, return 1.
    Else, if the first character of string1 is not equal to the first character of string2, return 0.
    Else, return the result of a call this function with the substrings of string1 and string2 that exclude their first characters.

    Notice that the first two sentences come directly from the base cases, and the third is the recursive step.

    claudiu's algorithm outline is also more iterative in description, which is normally fine (and usually even better), except that you're here for recursion.

    EDIT:
    Well, claudiu does say that "these are your new strings", so that does have a recursive aspect to it.
    Last edited by laserlight; 04-17-2012 at 10:21 AM.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Mar 2012
    Location
    Hong Kong
    Posts
    13
    i understand it, but i dont know how to code it since there are 2 parameters, i dont know how to call only first char for each string...anymore hints or example for me?

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,258
    Quote Originally Posted by Oscar Wong
    i dont know how to call only first char for each string
    Eh, but that is something that you have somewhat correct in your code. You used string1[0] to access the first character of string1. That's correct. You called compareStr(&(string1[1]), &(string2[1])). That's correct too, though I would have written it as compareStr(string1 + 1, string2 + 1). What is wrong/missing is the other parts that make up the algorithm, e.g., you are not actually returning 0 or 1, and then you add 1 to the recursive call when you shouldn't.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Mar 2012
    Location
    Hong Kong
    Posts
    13
    i cant solve it....please help...

  10. #10
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    You are not going to get code from us until you provide your own attempts. You have been told what to do, I basically spoonfed the pseudo-code to you, now you just need to translate it in C. Specific questions are welcome, requests like "Make it all work for me" are needy and are not welcome.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  11. #11
    Registered User
    Join Date
    Mar 2012
    Location
    Hong Kong
    Posts
    13
    is this right for the requirement?

    return 0; if string1 is not started with string2
    return 1; if string1 is started with string 2
    return -2; if any NULL Pointer
    return -1; if empty



    Code:
    int compareStr(char string1[], char string2[]) { int result; if (string1 == NULL || string2 == NULL){ printf("NULL pointer !\n"); return -2; } else if (string1[0] == '\0' || string2[0] == '\0'){ return -1; printf("Empty String !\n"); } else{ if(string1[0] == string2[0]){ result = compareStr(&(string1[1]), &(string2[1])); } else{ result = 0; } } }

  12. #12
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    It is starting to look more sensible. What do you get if you try to run that? Give it a few test cases, post them here together with the results.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  13. #13
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
       else if (string1[0] == '\0' || string2[0] == '\0'){
          return -1;
          printf("Empty String !\n");
       }
    The problem with this is that eventually, you will run into the case where you are at the end of the string. So that's not an error, and it's really not an error if s1 == s2 == \0.


    Quzah.
    Hope is the first step on the road to disappointment.

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,258
    Quote Originally Posted by Oscar Wong
    is this right for the requirement?

    return 0; if string1 is not started with string2
    return 1; if string1 is started with string 2
    When comparing only the first characters of the strings, how do you know if string1 does or does not start with string2?

    In my post #6, I observed that any string starts with an empty string. So, if I see that string2 is an empty string, I conclude that string1 starts with string2. How do I know string2 is an empty string? Well, the first character of an empty string is a null character.

    Quote Originally Posted by claudiu
    I basically spoonfed the pseudo-code to you
    I note that claudiu's pseudocode is for comparing the strings for equality rather than comparing to see if string1 starts with string2.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #15
    Registered User
    Join Date
    Mar 2012
    Location
    Hong Kong
    Posts
    13
    Yeah, i have solve this problem by myself, thanks all of you !!!!!!!!!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unable to compare string with 'getter' returned string.
    By Swerve in forum C++ Programming
    Replies: 2
    Last Post: 10-30-2009, 06:56 PM
  2. String Compare
    By almo89 in forum C Programming
    Replies: 1
    Last Post: 11-04-2005, 08:13 PM
  3. string compare
    By IceBall in forum C Programming
    Replies: 4
    Last Post: 10-12-2003, 06:26 PM
  4. Recursion = headache;
    By RoD in forum C++ Programming
    Replies: 9
    Last Post: 12-20-2002, 09:34 PM
  5. need help on string compare
    By Unregistered in forum C Programming
    Replies: 9
    Last Post: 06-07-2002, 09:55 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21