Recursion w/ strings

[Gagless]

I want to recursively check if two strings are equal, not in size, but character by character. I am unallowed to use loops and the == operator.

I tried to use two parallel arrays, but when testing my function I got undesired results.

Here's what I came up with:

int main()
{
cout << "Checking equivalence of two strings using recursion." << endl << endl;

	cout << "For two strings of size 2: ";
	char ArrayA[ 100 ] = { 't', 'a', 'r' };
	int SizeA = 2;
	char ArrayB[ 100 ] = { 't', 'a', 'r' };
	int SizeB = 2;
	cout << String1EqualString2( ArrayA, SizeA, ArrayB, SizeB );

	HoldScreen();

}

bool String1EqualString2( char ArrayA[], int SizeA, char ArrayB[], int SizeB )
{
	
	if ( SizeA <= 1 && SizeB <= 1 )
		return true;
	else if ( ArrayA[0] != ArrayA[1] && ArrayB[0] != ArrayB[1] )
		return false;

	return String1EqualString2( ArrayA+1, SizeA-1 , ArrayB+1, SizeB-1 );

}

[shankhs]

I want to recursively check if two strings are equal, not in size, but character by character. I am unallowed to use loops and the == operator.

I tried to use two parallel arrays, but when testing my function I got undesired results.

Here's what I came up with:

int main()
{
cout << "Checking equivalence of two strings using recursion." << endl << endl;

	cout << "For two strings of size 2: ";
	char ArrayA[ 100 ] = { 't', 'a', 'r' };
	int SizeA = 2;
	char ArrayB[ 100 ] = { 't', 'a', 'r' };
	int SizeB = 2;
	cout << String1EqualString2( ArrayA, SizeA, ArrayB, SizeB );

	HoldScreen();

}

bool String1EqualString2( char ArrayA[], int SizeA, char ArrayB[], int SizeB )
{
	
	if ( SizeA <= 1 && SizeB <= 1 )
		return true;
	else if ( ArrayA[0] != ArrayA[1] && ArrayB[0] != ArrayB[1] )
		return false;

	return String1EqualString2( ArrayA+1, SizeA-1 , ArrayB+1, SizeB-1 );

}

hey could you plz make your prob a bit more clear?????

[William Hemsworth]

This will return true if the characters are equal up to the minimum length of the two strings. And it does not use the == operator.

bool Compare(char *str1, char *str2) {
	if (!(*str1 || *str2)) return true; // End of string
	bool match = (*str1 >= *str2) && (*str1++ <= *str2++); // Check char
	if (match) return Compare(str1, str2);
	return false;
}

[Radical Edward]

> bool String1EqualString2( char ArrayA[], int SizeA, char ArrayB[], int SizeB )
There's no need to pass the size of each string. C strings are always terminated by the '\0' character or they aren't legal strings. You can use that character as the base case for recursion. Since you can't use the == operator, you have to use a bit more convoluted logic for the test:

bool Equals(const char *a, const char *b)
{
  // Base case: at '\0' for both strings, they're equal
  if (*a != '\0' || *b != '\0') {
    ...
  }

  return true;
}

If either of the characters is not '\0', the base case hasn't been hit. That's not a problem because the equality test for non-base case characters will catch if one of the characters is '\0' but the other isn't. That means the strings are different lengths. The equality test is simple:

bool Equals(const char *a, const char *b)
{
  // Base case: at '\0' for both strings, they're equal
  if (*a != '\0' || *b != '\0') {
    if (*a != *b)
      return false;

    ...
  }

  return true;
}

That's all of the computational logic in the algorithm, now all that's left is the recursion. For linear recursion there's nothing to think about, so you can just call Equals with the next two characters:

bool Equals(const char *a, const char *b)
{
  // Base case: at '\0' for both strings, they're equal
  if (*a != '\0' || *b != '\0') {
    if (*a != *b)
      return false;

    // Characters are equal, go to the next two
    return Equals(a + 1, b + 1);
  }

  return true;
}

[shankhs]

hey am i wrong with the c++ version of the code :

#include<iostream>

using namespace std;
bool rec(string a,string b,int i)
{
	if(a[i]!='\0'||b[i]!='\0')
	{
		if(a[i]!=b[i])
			return false;
		else return rec(a,b,i+1);
	}
	else return true;

}
int main()
{
	string str1="shankhs1";
	string str2="shankhs";
	cout<<rec(str1,str2,0);
	return 0;
}

is it good to end up string with '\0' or it should be '\n'???

[William Hemsworth]

is it good to end up string with '\0' or it should be '\n'???

All strings should finish with a '\0', known as a NULL Terminator. Without it, Problems may appear, for example:

char str[] = {'a','b','c','d'}; // has no NULL Terminator
cout << str; // Will print "abcd" but may also print a load of random characters after it.

char str[] = {'a','b','c','d','\0'}; // Contains a NULL Terminator and therefore will stop printing characters when it reaches '\0'.
cout << str;

Also it is used in many standard C++ functions like strlen.

You could rewrite the strlen function like this:

size_t strlen(const char *str) {
	size_t len = 0;
	while (*str++) len++;
	// Terminates when the NULL character is reached
	/*
	Same as:
	 while (*str++ != 0) len++;
	*/
	return len;
}

When you assign a string like this:

char str[] = "Hello";

The NULL Terminator is automaticly placed at the end.

[Duoas]

@shankhs
You've got the right idea (for one way of doing it).

You might as well give the last argument a default value: bool rec(string a,string b,int i=0) You also need to watch your termination condition. If a and b have different lengths you may get an access violation.

[edit] I was going to give a nice, simple recursive version, but then I realized that this is Gagless's homework, so I'll just give him something to think about.

Recursive functions must always have a termination condition for every possible branch. Your current function doesn't (it leaves one branch open).

Since (as way already noted) all char[] strings must end with '\0', you can use that as a EOS signal, but explicitly passing a size count is fine also. Also remember, you don't want to compare elements in the same string, you want to compare elements in one string with those in another string at the same indices.

There is no rule that says that you have to traverse the strings in a forward direction. It is fine to go backwards. So, given that a string must end with '\0', and the argument values giving the lengths of the strings, you can immediately write the following conditions:

sizeA != sizeB --> strings not equal (they have different sizes)
ArrayA[ sizeA ] != ArrayB[ sizeB ] --> strings not equal

Now you must add one more condition to check to see if the strings are equal. What is it?

? == ? --> strings are equal

And you must add your recursive part if none of the tests are definitive:

String1EqualString2( ?, ?, ?, ? );

Don't modify too many things at once.

Good luck.

[shankhs]

All strings should finish with a '\0', known as a NULL Terminator. Without it, Problems may appear

Also it is used in many standard C++ functions like strlen.

You could rewrite the strlen function like this:

size_t strlen(const char *str) {
	size_t len = 0;
	while (*str++) len++;
	// Terminates when the NULL character is reached
	/*
	Same as:
	 while (*str++ != 0) len++;
	*/
	return len;
}

When you assign a string like this:

char str[] = "Hello";

The NULL Terminator is automaticly placed at the end.

hey just give a look on vmanes idea on c++ strings in:
http://www.daniweb.com/forums/thread124696.html
it said:

Two points:
C++ string is not required to have NULL terminator ('\0'), but you will find it present under many compilers. One should not use this as a limit on the extent of the string, use the .length() or .size( ) methods.

C-style strings end with '\0', not '\n'. The newline is a character that may be embedded within a string.

now I am confused whether it is good to use '\0' or string.size() for the check condition in recursion!!!

[William Hemsworth]

Using std::string does not require a Null Terminator because it keeps track of the length as you add characters into the vector, but when you call std::string::c_str(), it will return the characters in the string along with a '\0' at the end.