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

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.

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?

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.

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.

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.

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.

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.

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.

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.

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.