Recursive function - checking for palindromes

[Sin-da-cat]

Can somebody help me with this? I'm not sure if this is the right forum section, so if it's not, please let me know. The problem goes like this:

I need to create a program that has a recursive function which checks whether or not the given string is a palindrome. Spaces (' ') are to be ignored and the program is not to be case-sensitive.


In short terms, I'm lost. Doing this without recursion is easy, but with?

Thanks in advance.

[iamthwee]

http://forums.devshed.com/c-programming-42/palindrome-recursion-36299.html

[~s.o.s~]

Hmm.. recursive palindrome checker.

As far as the ignoring spaces part is concerned, it would be better if you purged your string of spaces or newline characters before passing it to the Palindrome checker function. That way it would be cleaner and easier.

As far as the algo for recursive implementation is concerned, the logic is same as the recursive one, but you just need to write the function so as it can be called recursively.
Create a function "is_palindrome()" which accepts the C style string which has to be checked for and the size of the string.
During the first pass, the function would be supplied with the pointer to the start of the string and the original string length.
Check if the strign length is less than one, if yes then the given string is a palindrome and return 1 or success. This is one way in which the function will be terminated.
Now check if the first char of the string is the same as the last character. If yes then call the function again but this time with the character pointer incremented by one (to point to the next character under consideration) and the size parameter decreased by 2 ( since we have tackled two characters already-- the first and the last)
If the first character is not equal to the last character, there is no point in continuing the function. Return failure or 0. This is the second terminating condition of hte program
Hope it helped, bye.

[Sin-da-cat]

Alright, I used what you told me and made my own attempt, slightly different from what you suggested. Yet, my program always says the string is not a palindrome. Here's the code, can you see why it does that?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char palindrome(char *,int);
main(){
char x[50],y[50];
int i=0,j=0,r=0;
printf("Type the string\n");
gets(x);
while (x[j]!='\0'){
if (x[j]>='A' && x[j]<='Z') /*turning CAPS into lowercase*/
y[r++]=x[j]+('A'-'a'); 
else if (x[j]!=' ') /*removing spacesfrom the string*/
y[r++]=x[j];
j++;
}
if (palindrome (y,i)==1)
printf("Palindrome\n");
else printf ("Not a palindrome\n");
getchar();
}
char palindrome(char a[],int i){ /*'k' is set as the length of our string*/
int k;
k=strlen(a);
if (k<2) return 1;
else if (a[i]!=a[k-i]) return 0; /*comparing first and last char*/
else return palindrome(a,i+1); /*increasing 'i' by 1*/
}

[~s.o.s~]

Ok that is a very good effort on your part.
I will write a crude code for you and will let you do the research on the inbuilt functions of C which i have used in achieveing the task.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char palindrome(char *,int);

/**
 * This function is used to remove the trailing new line which is normally present at the end of the string accepted from the user
 * using fgets( ).
 */
 void remove_newline( char* input )
{
    // loook up this func also at www.cppreference.com
    char* p = 0 ;
    if( p = strrchr( input, '\n' ) )
        *p = '\0' ;
}

char palindrome( char my_string[], int length )
{
    if( length < 2 )
        return 1;

    if( my_string[0] != my_string[length - 1] )
        return 0;
    else
        return palindrome( my_string + 1, length -2 );
}

void make_lower( char* input )
{
    // make string lowercase
    int i = 0 , string_length = strlen( input );
    while( input[i] != '\0' )
    {
        input[i] = tolower( input[i] ) ; // use std function to make string lowercase
        ++i ;
    }
}

char* format_string( char* input )
{
    // look up the function strtok, fgets, strcat and calloc at www.cppreference.com
    char* result = NULL ;
    char delimiter[] = " "  ;
    char* new_string = (char*) calloc( strlen( input ) + 1, sizeof( char ) ) ;

    result = strtok( input, delimiter ) ;
    while( result != NULL )
    {
        printf( "\ntoken: %s", result ) ;
        strcat( new_string, result ) ;
        result = strtok( NULL, delimiter ) ;
    }

    printf( "\nNew string in format functions is %s", new_string ) ;
    return new_string ;
}

int main()
{
    char my_string[BUFSIZ] = {'\0'} ; // initialize the string array to all '\0'
    printf("Type the string: ");
    fgets( my_string, BUFSIZ, stdin ) ; // dont use gets() , instead use fgets(). Its much safer.
    remove_newline( my_string ) ;
    make_lower( my_string ) ;

    char* new_string = format_string( my_string ) ;
    printf( "\n%s", new_string ) ;

    int string_length = strlen( new_string ) ;
    if( palindrome ( new_string, string_length ) == 1 )
        printf("\nPalindrome\n");
    else
        printf ("\nNot a palindrome\n");


    return 0 ;
}

Study the various aspects of this code and tell me if there is any difficulty. Any one of the MODS would be ableto help you out.

Hope it helped, bye.

[Sin-da-cat]

Ok, thanks very much. It's 22.50 PM here now so I'm too sleepy to think, but I'll definitely do my research tommorow and mark this solved if I understand everything.

P.S. Sorry about not using the code thing in my last post, I didn't know how to.

Oh, and if you (or anyone else) can pinpoint the mistake in the code I wrote, I'd appreciate it.

[~s.o.s~]

Dont worry about the code tags, its our daily routine to correct posts. Remember it though for the next time.

BTW just wanted to tell you that its 03.30 here :P ( so its never too late to code)

[WaltP]

My first reaction is why bother with strtok()? This is a simple program of characters, not tokens.

Next, C has a function called tolower() and toupper() that will return the character passed in as an upper or lower case value. Good for comparing case insensitive values. It also doesn't affect non-alphabetic values.

Third, if all you are concerned with is letters, the function isalpha() is ready made for you. If letters and number, it's isalnum().

strlen() will return the length of the string to it's end, not to where you want to stop, so taking the string length in the palindrome() function is not doing you any good.

And using gets() is a recipe for disaster. Best to convert
gets(x) tofgets():
fgets(x, 50, stdin);

My take on this ispalindrome() should take 3 parameters
1) The string
2) Index to the first character in the string
3) Index to the last character in the string

Then palindrome(str, ch1, ch2) can process the string in this manner:

Set len to length of str (so you don't run off the end of the string)
While isalpha(str[ch1]) is false: 
    Increment ch1. 
    Return if ch1 > len.  
    -- pass back true or false, you get to figure out which.
While isalpha(str[ch2]) is false:
    Decrement ch2. 
    Return if ch2 < 0.  
    -- pass back true or false, you get to figure out which

// At this point you are looking at 2 alphabetic characters.
Test if ch1 >= ch2.  If true you've crossed the midpoint of the string.
    Return TRUE, you've got palindromism

If LowerCase(str[ch1]) == LowerCase(str[ch2])
    call palindrome() again with ch1+1 and ch2-1

// If you get to this point, the two characters are different.
Return FALSE

[~s.o.s~]

Hmm.. I think there is some kind of misunderstanding here Mr. WaltP. His requirement is that the palindrome should be case insensitive as well as "ignore whitespace characters".

My first reaction is why bother with strtok()? This is a simple program of characters, not tokens.

Okay now i will try explaining my logic behind this. The OP wants the algo to ignore whitespace characters. So suppose your string is A (50 spaces) b (\n\t\t) B (100 spaces) a

Trying to loop through the whole string to ignore whitespace characters is not feasible, would jsut result in reinventing the wheel when we have good inbuilt functions to handle such kind of situations. strtok is just the kind of thing we need here IMHO. Comments are welcome.

[Sin-da-cat]

I worked it out this morning by slightly altering my previous code and without using any functions I didn't use originally. I will get to know the functions you suggested as soon as I find the time needed. Here's the code that works:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char palindrome(char *,int,int);
main(){
char x[50],y[50];              /*I wrote it without using any functions I wasn't previously familiar with*/
int i=0,j,r=0,k,len;           /*will try to use the functions when I find time*/
printf("Type your string\n");
gets(x);
len=strlen(x);
for (j=0;j<len;j++){
 if (x[j]>='A' && x[j]<='Z')     /*turning caps into lowercase*/
        y[r++]=x[j]-('A'-'a');      /*making new string stripped of everything but letters*/
    if (x[j]>='a' && x[j]<='z')     /*did this to simplify slightly, my task wasn't worded very clearly anyway*/
        y[r++]=x[j];
        }
k=r-1;
if (palindrome (y,i,k)==1)
 printf("You've got yourself a palindrome\n");
else if (palindrome (y,i,k)==0) printf ("Not a palindrome\n");
getchar();
}                                     /*Works perfectly. Overall, a combination of everything you guys suggested*/
char palindrome(char a[],int i,int k){
if (i>=k) return 1;
else if (a[i]!=a[k]) return 0;
else if (a[i]==a[k]) return palindrome(a,i+1,k-1);
else return 0;
}

Thanks for answering, everyone.

[WaltP]

Hmm.. I think there is some kind of misunderstanding here Mr. WaltP. His requirement is that the palindrome should be case insensitive as well as "ignore whitespace characters".

No misunderstanding. My algorithm does exactly that.

While isalpha(str[ch1]) is false: 
    Increment ch1. 
    Return if ch1 > len.  
    -- pass back true or false, you get to figure out which.
...
If LowerCase(str[ch1]) == LowerCase(str[ch2])
    call palindrome() again with ch1+1 and ch2-1

Which says

While the current character is not a letter, 
    go to the next character
    verify we still have characters still in the string
...
If the two characters converted to lower case are identical
    call the function again with the next and prev characters

Trying to loop through the whole string to ignore whitespace characters is not feasible, would jsut result in reinventing the wheel when we have good inbuilt functions to handle such kind of situations. strtok is just the kind of thing we need here IMHO. Comments are welcome.

It's perfectly feasible. That's what a palindrome parser does is test characters, not tokens. Please explain what is not feasible about my post.

[~s.o.s~]

Bah... I agree. I completely missed out your algorithm, my bad.

But still if the requirement also consists of reading palindrome data from a input file and then writing the actual palindrome string devoid of whitespace characters and which is case insensitive....
*how i wish* :D

Anyways thanks for pointing it out, maybe i am just growing senile in young age...

[farooqiumar]

yes there is a soln of this pelindrome

#include<stdio.h>
#include<ctype.h>
int n=0;
int peli(char *b,int t)
{
if(*b!=*(b+t-1-n))
return 0;
else
{if(t==1)
return 1;
else{
n++;
return peli(++b,--t);
}
}
}
int main()
{
char *a;
int j,m=0,k=0;
clrscr();
for(j=0;j<80;j++)
{
scanf("%c",a+j);
if(*(a+j)==',')
break;
*(a+j-k)=*(a+j);
if(*(a+j)==' ')
{k++;
continue;
}
m++;
}
for(j=0;j<m;j++)
{if(islower(*(a+j)))
*(a+j)=toupper(*(a+j));
}
if(peli(a,m)==1)
{
printf("the string is pelindromic\n");
}
else
printf("The string is not pelindromic");
return 0;
}