int isPalindrome(char str[])

This is a discussion on int isPalindrome(char str[]) within the C Programming forums, part of the General Programming Boards category; Hi, I have the following recursive implementation of a function that checks if a word is a palindrome. But i ...

  1. #1
    Registered User
    Join Date
    Oct 2008
    Posts
    28

    int isPalindrome(char str[])

    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?

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Use strlen()
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Registered User
    Join Date
    Oct 2008
    Posts
    28
    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;  
    }

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Lissa View Post
    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?
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Registered User
    Join Date
    Oct 2008
    Posts
    28
    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

  6. #6
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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.
    Last edited by MK27; 02-21-2009 at 04:41 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  7. #7
    Registered User
    Join Date
    Jan 2008
    Posts
    287
    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));
    }

  8. #8
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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.
    Last edited by MK27; 02-21-2009 at 04:55 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  9. #9
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,236
    Quote Originally Posted by Lissa View Post
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  10. #10
    Registered User
    Join Date
    Oct 2008
    Posts
    28
    I just modified the prototype and it worked fine thanks yall^^

  11. #11
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Lissa View Post
    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;
    }
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. memory leak
    By aruna1 in forum C++ Programming
    Replies: 3
    Last Post: 08-17-2008, 10:28 PM
  2. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  3. Working with random like dice
    By SebastionV3 in forum C++ Programming
    Replies: 10
    Last Post: 05-26-2006, 09:16 PM
  4. getting a headache
    By sreetvert83 in forum C++ Programming
    Replies: 41
    Last Post: 09-30-2005, 05:20 AM
  5. Quack! It doesn't work! >.<
    By *Michelle* in forum C++ Programming
    Replies: 8
    Last Post: 03-01-2003, 11:26 PM

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