Comparing string recursively

[nizbit]

I wrote a function that compares the characters of two strings recursively. If the characters of the strings are all equal the function returns 0. If the character from string1 is smaller ie-"a" to "l" it returns the negative difference of their ASCII vaules. If the character from string2 is larger ie-"l" to "a" it returns the positive difference of their ASCII vaules. I can see that my code will stop when two different characters are reached, but a zero is always returned. The code:

int str_compare(const char *str1, const char *str2)
{

    if (*str1 != '\0' || *str2 != '\0')
    {
        if (*str1 != *str2)
	{
		if (*str1 > *str2)
		{
		cout << "str1= " << str1 << " " << "str2= " << str2 << endl;
		return *str1 - *str2;
		}
		else if (*str1 < *str2)
		{
		cout << "str1 " << str1 << " " << "str2 " << str2 << endl;
		return *str1 - *str2;
		}
	}
	str_compare(str1 + 1, str2 + 1);
        else return 0;
}

[Ancient Dragon]

worked ok for me, after I fixed the bug

int str_compare(const char *str1, const char *str2)
{
    if (*str1 != '\0' || *str2 != '\0')
    {
        if (*str1 != *str2)
        {
            if (*str1 > *str2)
            {
                cout << "str1= " << str1 << " " << "str2= " << str2 << endl;
                return *str1 - *str2;
            }
            else if (*str1 < *str2)
            {
                cout << "str1 " << str1 << " " << "str2 " << str2 << endl;
                return *str1 - *str2;
            }
        }
        str_compare(str1 + 1, str2 + 1);
    }
    else return 0;
}

[nizbit]

I saw my error and fixed it. Although it is still returning 0.

[Ancient Dragon]

I pass "Hella" and "Hello" as the two parameters, and it returned -14. The "Hello" for both and it return 0. "Hello" and Helloa" return 14.

What two strings did you pass it from main() ?

[nizbit]

apple and apparel

[Ancient Dragon]

This is the output for apple and apparel

str1= le str2= arel
11
Press any key to continue . . .

BTY: I used VC++ 2008 Express compiler.

If you don't get the above output then you probably don't have the same program that I posted. Copy this, compile and run it to see what you get.:

#include <iostream>
using namespace std;

int str_compare(const char *str1, const char *str2)
{
    if (*str1 != '\0' || *str2 != '\0')
    {
        if (*str1 != *str2)
        {
            if (*str1 > *str2)
            {
                cout << "str1= " << str1 << " " << "str2= " << str2 << endl;
                return *str1 - *str2;
            }
            else if (*str1 < *str2)
            {
                cout << "str1 " << str1 << " " << "str2 " << str2 << endl;
                return *str1 - *str2;
            }
        }
        str_compare(str1 + 1, str2 + 1);
    }
    else return 0;
}	

int main(int argc, char* argv[])
{
	int x = str_compare("apple", "apparel");
	cout << x << "\n";
	return 0;
}

[dougy83]

are you sure you don't mean:

int str_compare(const char *str1, const char *str2)
{
    if (*str1 != '\0' || *str2 != '\0')
    {
        if (*str1 != *str2)
        {
            if (*str1 > *str2)
            {
                cout << "str1= " << str1 << " " << "str2= " << str2 << endl;
                return *str1 - *str2;
            }
            else if (*str1 < *str2)
            {
                cout << "str1 " << str1 << " " << "str2 " << str2 << endl;
                return *str1 - *str2;
            }
        }
        
    }
    else return 0;
    
    return str_compare(str1 + 1, str2 + 1);
}

Otherwise the return value is undefined (where it is not explicitly 0).

[nizbit]

I got:

str1 a str2 o
1

with this code:

#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>
using namespace std;

int str_compare(const char *str1, const char *str2)
{
    if (*str1 != '\0' || *str2 != '\0')
    {
        if (*str1 != *str2)
        {
            if (*str1 > *str2)
            {
                cout << "str1= " << str1 << " " << "str2= " << str2 << endl;
                return *str1 - *str2;
            }
            else if (*str1 < *str2)
            {
                cout << "str1 " << str1 << " " << "str2 " << str2 << endl;
                return *str1 - *str2;
            }
        }
        str_compare(str1 + 1, str2 + 1);
    }
    else return 0;
}	

int main ()
{
	char array[]="hella";
	char array2[]="hello";
	int i=str_compare(array, array2);
	cout << i <<endl;
	return 0;
}

[Ancient Dragon]

What compiler do you have? And what operating system. Your program gives me the same as the code I posted. It must be a compiler and/or os difference. Also, my computer has 5 Gig RAM.

str1 a str2 o
-14
Press any key to continue . . .

[nizbit]

Sorry Dougy83, I didnt see your post before I posted. The code works now. Thanks for all the help.

[Ancient Dragon]

are you sure you don't mean:

Otherwise the return value is undefined (where it is not explicitly 0).

No its not undefined -- the last else statement will take care of that case. The line you added will never get executed.

[nizbit]

gcc version 4.3.0 20080428 (Red Hat 4.3.0-8)

Ancient Dragon, that is weird. Prob more compiler differences.

[Ancient Dragon]

No its not undefined -- the last else statement will take care of that case. The line you added will never get executed.

This statement isn't correct. Using Dev-C++ the function returns an undefined value without the return statement Dougy83 added.

[dougy83]

What compiler do you have? And what operating system. Your program gives me the same as the code I posted. It must be a compiler and/or os difference.

I use dev-c++ - so mingw compiler. You'll see that the code you posted doesn't have an explicit return statement for every possible path; i.e. the function can hit the end brace '}' without executing a return xx; statement. I'm assuming that it works for you because your compiler doesn't modify the return register (EAX isn't it?) as drills back up through the nested function calls.

I would have thought it unacceptable to leave a function return value uninitialised/unset.

Also, my computer has 5 Gig RAM.

Big-noter!! Size isn't everything!

[dougy83]

Geez, I must typ slow. In case you haven't found it, see the exit point in your code below (marked with '###'):

int str_compare(const char *str1, const char *str2)
{
    if (*str1 != '\0' || *str2 != '\0')
    {
        if (*str1 != *str2)
        {
            if (*str1 > *str2)
            {
                cout << "str1= " << str1 << " " << "str2= " << str2 << endl;
                return *str1 - *str2;
            }
            else if (*str1 < *str2)
            {
                cout << "str1 " << str1 << " " << "str2 " << str2 << endl;
                return *str1 - *str2;
            }
        }
        str_compare(str1 + 1, str2 + 1);   // ### this is the last line executed     if (*str1 != '\0' || *str2 != '\0') ###
        
    }
    else return 0;
}

[Ancient Dragon]

I use dev-c++ - so mingw compiler. You'll see that the code you posted doesn't have an explicit return statement for every possible path; i.e. the function can hit the end brace '}' without executing a return xx; statement. I'm assuming that it works for you because your compiler doesn't modify the return register (EAX isn't it?) as drills back up through the nested function calls.

It worked for me only because I was lucky, not because the code was correct.

Line # 18 of the code quoted in previous post should have had a return statement to make it correct.

Big-noter!! Size isn't everything!

The only reason I mentioned it was because possibly the OP was running out of memory. recursion does that on computers with small ram.

[ArkM]

Yet another way to go from A to B:
1. Dress, provide with boots.
2. Make a step.
3. Undress, take your shoes off
4. OK, ready to go from A' to B
5. Is A' == B?
6. No: see #1
...
The same algorithm.
What's a wonderful example to study recursion!..