int isPalindrome(char str[])

**Lissa** · 02-21-2009

Hi,

I have the following recursive implementation of a function that checks if a word is a palindrome. But i actually need it with this prototype (recursive as well) :
int isPalindrome(char str[])

Code:

int isPalindrome (char *str, int length){
int i;
   if (length<1) 
         return 1;
  if (str[0] == str[length-1])                                 
         return isPalindrome (str+1, length-2);    
   else 
         return 0;                                         
   }

I dont know how to get rid of the length in the protoype and include it inside the function. Can anybody help?

**MK27** · 02-21-2009

Use strlen()

**Lissa** · 02-21-2009

I know this is what i tried to do but it doesnt seem to work:

Code:

int isPalindrome (char *str){
int length=strlen(str);
int i;
   if (length<1) 
   		return 1;
	if (str[0] == str[length-1]){
	    length -=2;                    
      	return isPalindrome (str+1); }  
   else 
   		return 0;  
}

**MK27** · 02-21-2009

Originally Posted by Lissa

I know this is what i tried to do but it doesnt seem to work:

It should. How doesn't it work -- or rather, if you printf("%d",length) after your strlen call, what is incorrect about that number?

**Lissa** · 02-21-2009

It prints all the words as not palindrome. I added the printf u said, and for those who actually are: it prints the actual length and (lenght-1). :s:s

**MK27** · 02-21-2009

Have you tried doing this iteratively (with a loop inside the function) instead of recursively -- or do you have to use recursion?

You cannot control the length of the string by changing "length". If you don't mind destroying the original string, just use

Code:

string[len-1]='\0';

before the recursion call.

**arpsmack** · 02-21-2009

In order to check for a palindrome, your recursive function checks the first character in the string against the last character in the string, and then "discards" both of them. So the comparisons look like this:

Code:

STEP 1   STEP 2   STEP 3
abcddcba _bcddcb_ __cddc__
^      ^  ^    ^    ^  ^

You accomplished "discarding" the first character by incrementing your string pointer by 1 when you passed the string to the recursive call. And to "discard" the last character you adjusted the length value when you passed it to the recursive call.

Unfortunately, since you modified the function to use strlen(), you are recalculating the length each recursive call and not adjusting it to discard the characters at the end that you've already checked. Basically, you're doing this:

Code:

STEP 1   STEP 2   STEP 3
abcddcba _bcddcba __cddcba
^      ^  ^     ^   ^    ^

(of course this would actually fail at STEP 2)

To handle situations like these, I usually write 2 functions. One has a very simple signature that is easy to use, and the other is the recursive function that does all the work and has a more complicated signature. In your case:

Code:

int isPalindrome_r(char *str, int length) {
   if (length<1)
      return 1;
   if (str[0] == str[length-1])
      return isPalindrome (str+1, length-2);
   else
      return 0;
}
int isPalindrome(char *str) {
   return isPalindrome_r(str, strlen(str));
}

**MK27** · 02-21-2009

You don't need two functions. I just did it with one (recursively) in eight lines, respecting the prototype from the Original Post.

You increment the pointer, and then you change the last charater to a null terminator, which shortens the length by two. When the length reaches <=2, you return TRUE.

That means, like I said, destroying the original string. So if you want to keep it, keep a copy before you first call the palindrome function.

If you ask for it, I can give you an answer...just don't tell anyone.

**brewbuck** · 02-21-2009

Originally Posted by Lissa

I dont know how to get rid of the length in the protoype and include it inside the function. Can anybody help?

You could call strlen(), but that multiplies your complexity by a factor of N for completely no reason.

**Lissa** · 03-02-2009

I just modified the prototype and it worked fine thanks yall^^

**MK27** · 03-02-2009

Originally Posted by Lissa

I just modified the prototype and it worked fine thanks yall^^

Yay! Here was my answer:

Code:

#include <stdio.h>
#include <string.h>

int palindrome (char *string) {
	char *ptr=string;
	int len=strlen(string), i=0;
	if (len<=1) return 1;
	if (string[i]==string[len-1]) {
		string[len-1]='\0';
		return palindrome(++ptr);
	}
	return 0;
}

int main (int argc, char *argv[]) {
	printf("%d\n",palindrome(argv[1]));
	return 0;
}

Thread: int isPalindrome(char str[])

Thread Tools

Search Thread

Display

int isPalindrome(char str[])

Similar Threads

memory leak

Screwy Linker Error - VC2005

Working with random like dice

getting a headache

Quack! It doesn't work! >.<