Recursive method for checking palindrome
Is it even possible to define a recursive method to test a palindrome with the following list of arguments?
int testPalindromeRecursive(char* str, int len) { ... }
Note: external sub-functions or global variables should not be used
I think this is not possible because you have to remember the last (front) index position somehow.
source to share
As for me, I would declare a function like
int testPalindromeRecursive( const char *s, size_t n );
In this case, the function will contain only one return statement.
int testPalindromeRecursive( const char *s, size_t n )
{
return ( n < 2 ) ||
( s[0] == s[n-1] && testPalindromeRecursive( s + 1, n - 2 ) );
}
However, this feature can be viewed as follows, as shown in the demo below
#include <stdio.h>
int testPalindromeRecursive( char *str, int len )
{
if ( len < 0 ) return 0;
return ( len < 2 ) ||
( str[0] == str[len-1] && testPalindromeRecursive( str + 1, len - 2 ) );
}
int main( void )
{
char s[] = "abbcccbba";
printf( "testPalindromeRecursive( \"%s\" ) is %s\n",
s, testPalindromeRecursive( s, sizeof( s ) - 1 ) ? "true" : "false" );
return 0;
}
Program output
testPalindromeRecursive( "abbcccbba" ) is true
Note that you can follow the general convention that string functions do not check whether a passed character is a NULL pointer. It is the responsibility of the programmer to program before calling the function.
source to share
My solution is capable of missing spaces:
int test_palindrom_recursive(char* str, int len)
{
if (len < 1) return 0;
int frontIndexToPass = 0, endIndexToPass = 0;
if (str[0] == ' ')
{
for (int front = 0; front < len - 1; front++)
{
if (str[front] == ' ') frontIndexToPass++;
else break;
}
}
if (str[len - 1] == ' ')
{
for (int end = len - 1; end >= 0; end--)
{
if (str[end] == ' ') endIndexToPass++;
else break;
}
}
if (tolower(str[0 + frontIndexToPass]) == tolower(str[len - endIndexToPass - 1]))
{
if (len <= 2) return 1;
else
test_palindrom_rekursiv(str + frontIndexToPass + 1,
len - endIndexToPass - frontIndexToPass - 2);
}
else return 0;
}
source to share
With the help C#
I was able to get the following:
int testPalindromeRecursive(string str, int len)
{
if (len <= 1)
return 0;
if (str[0] == str[len - 1])
{
str = str.Substring(1, len - 2);
return testPalindromeRecursive(str, str.Length);
}
return -1;
}
ref
does almost the same job as *
here. => Removed ref
because it was not the best option as it did not allow the use ofconst
source to share
This works great for me:
#include <stdio.h>
#include <string.h>
int testPalindromeRecursive(char* str, int len)
{
if (len <= 1)
return 1;
if (str[0] != str[len-1])
return 0;
return testPalindromeRecursive(str+1, len-2);
}
int main()
{
int i;
char *strs[5] = { "test", "tvt", "a", "palindrome", "racecar" };
for (i = 0; i < 5; i++)
printf("%s = %d\n", strs[i], testPalindromeRecursive(strs[i], strlen(strs[i])));
}
Edit: fix as per comments for checking length == 0 also
source to share
[EDIT2]
This is the correct answer in C. Although it has been omitted three times, I am saving it as the ONLY correct answer in C on this page.
[EDIT]
corrected my answer.
In C:
#include <stdio.h>
#include <string.h>
int testPalindromeRecursive(char* str, int len)
{
if (len <= 1)
return 0;
if (str[0] != str[len-1])
return 1;
return testPalindromeRecursive(str+1, len-2);
}
int main(int argc, char **argv)
{
if (argc < 2)
{
printf("Usage: %s <string>\n", argv[0]);
return 1;
}
if (!testPalindromeRecursive(argv[1], strlen(argv[1])))
printf("Palindrom\n");
else
printf("Not palindrom\n");
return 0;
}
Running the example for the case mentioned in kdopen's comment (base case fails when testPalindromeRecursive ("a", 1):
./palind a Palindrom
Additional examples mentioned by kdopen:
./mine \ "a <- the \ is to avoid" Not a palindrome
./mine \ "\" Palindrom
source to share