Recursive Palindrome

[timb89]

10 marks Write a RECURSIVE function which when passed a string s will
return true if s is a palindrome and otherwise false. A palindrome is a string
which is the same if reversed eg radar, rotor, noon, racecar.

past paper question which im doing at the moment as got be stuck?

bool isPalindrome (string s)
{
       if (s.empty())  
       {
             return true;
       }

}

im really unsre?

[Salem]

else if ( s.length() == 1 ) return true;

else do something to s, and do
return isPalindrome(s)

[timb89]

void reverseString(string s)
{
     if (!s.empty())
     {
        cout << s.at(s.length()-1);
        reverseString(s.substr(0,s.length()-1)); 
     }
}

i got it working for a void but the bool just confuses me?

[timb89]

bool isPalindrome(string s)
{
     if (s.length() == 1)
     {
     return true;
     }
     
     else if (!s.empty())
     {
          if (s.at(0) == s.at(s.length()-1))
          {
                isPalindrome(s.substr(1,s.length()-1));
          }
          else
          {
                return false;
          }
     }     
}

am i close?

[timb89]

bool isPalindrome(string s)
{
     if (s.length() == 1)
     {
     return true;
     }
     
     else if (!s.empty())
     {
          if (s.at(0) == s.at(s.length()-1))
          {    
                isPalindrome(s.substr(1,s.length()-2));
          }
          else
          {
                return false;
          }
     }     
}

i think i have it?

[Salem]

Close, but read my reply again.

[Sky Diploma]

Timb i guess you should

return isPalindrome(s.substr(1,s.length()-2));

[yun]

the best way to use Recursive function is.. use Wrapper Function, as in the below case CheckPalindrome is the Wrapper function.

bool isPalindrome(string str){
	return CheckPalindrome(str,0,str.length()-1);
}

bool CheckPalindrome(string str,int first,int last){
	if(first>=last){
		return true;
	}else {
		return (str[first]==str[last] && CheckPalindrome(str,first+1,last-1);
	}
}

and if u dont wanna use the wrapper function(which infact a best practice) then u can use the below function

bool isPalindrome(string str){
	int len = str.length();
	if(len<=1){
		return true
	}else {
		return (str[0]==str[len-1] && CheckPalindrome(str.substr(1,len-2)));
	}
}

[Stinomus]

the best way to use Recursive function is.. use Wrapper Function, as in the below case CheckPalindrome is the Wrapper function.

I can't say I'd agree with your example. It's just a function that calls another function, the wrapper is pointless as it does no translation.

Moreover the recursive function itself is inefficient as you pass the string by value yet you also pass the indexes you want to examine. Either create a new string - which excludes the first and last indexes - and have the function just check the first and last components or pass the indexes but pass the string by reference.

But I suppose the reality is that a recursive function is not the best solution for this problem anyway.

[siddhant3s]

Recursive functions is almost never a good idea if you are aiming for speed.
Recursive functions however, are easier to conceptualize than iterative functions. They goes with philosophy ``Developers time is far more important than machine time."

However, on languages such as C, C++ recursive functions are not 'so bad' since function calls are relatively cheap.

As far as this case is concerned, STL provide the reverse function do reverse a string, then checking for palindrome is a child's play:

bool isPalin(const std::string& s)
{
   std::string t(s);
   std::reverse(t.begin(),t.end());
   return s==t;
}

[Stinomus]

Alternatively the algorithmic version:

int length=str.length()-1;
for( int i=0; i<=length/2; ++i )
{
  if( str[i] != str[length-i] )
  {
    return false;
  }
}
return true;

Much more efficient than string copies and building up the stack with recursion.