Coder's Guild Mailing List

Recursive Palindrome String Solution

Posted by Ali Bhai on 1999-04-19

Hi,

I have seen the solution by Weasel to Eugene. The function given by Weasel
is not self sufficient. I mean that it's an algorithm, not an
implementation. In my opinion we can't write a function that checks for
Palindrome conditions recursively by following the given prototype, ie.

int isPalindrome (char *str);

The str parameter tells us where the string starts from, but it doesn't tell
us where it ends. In a recursive implementation we have to knock off one
element from each side of the string after testing both ends for equality.
This requires that we somehow keep track of the end. I have the following
prototype and implementation in my mind:

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

int isPalindrome (char *str, int length)
   {
   int i;
   if (length<1) return 1; // no more chars to compare, its palindrome

// you can remove the next 2 lines but
// they display what is actually being done

   for (i=0; i<length; i++) printf ("%c", str[i]);
   printf (" has length %d.\n", length);

   if (str[0] == str[length-1])                         // end chars same?
      return isPalindrome (str+1, length-2);    // check for next
   else return 0;                                         // not a plindrome
   }

void main (void)
   {
   int result;
   char str[256];
   printf ("Please type a string: ");
   gets (str);
   result = isPalindrome (str, strlen (str));
   if (result==1) printf ("Its a palindrome string.");
   else printf ("Not a palindrome");
   }
------------------------

There is another way to solve the same problem by using "static" data type.
But I think the implementation will not be portable to Pascal and other
languages. Anyhow, I will rewrite the function as:

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

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


void main (void)
   {
   int result;
   char str[256];
   printf ("Please type a string: ");
   gets (str);
   result = isPalindrome (str);
   if (result==1) printf ("Its a palindrome string.");
   else printf ("Not a palindrome");
   }
------------------------

Any queries?

Ali Bhai
BCS III - FAST Institute of Computer Science, Karachi
email: mashah@xxxxx.xxx.xx
web page: www.pak.org/mufta
<----------------------------------------->
[To err is human but to really mess up the things you need a computer.]

| | Timeline | Home