A recursive algorithm for palindrome testing

Question

This is a normal method for palindrome testing that I made but I need a recursive function that checks if a number is palindrome.

int number, firstnumber, lastnumber, secondnumber, fourthnumber;

readingnumber:

Console.Write("Please enter your palindrome number(5 digits) :" );
//reading the integer number entered
number = Int32.Parse(Console.ReadLine());
//making condition if the number is less than 5 digits
if (number / 100000 != 0)
    goto readingnumber;
else
{
    //we are taking each element alone 
    firstnumber = number / 10000;
    lastnumber = number % 10;
    fourthnumber = (number % 100) / 10;
    secondnumber = (number % 10000) / 1000;

    //making if condition to verify if the number is palindrom or not
    if (firstnumber == lastnumber && secondnumber == fourthnumber)
        Console.WriteLine("\n\nthe number you've enter is palindrom");
    else
        Console.WriteLine("\n\nthe number you've enter is not palindrom");

    //end of program
    Console.WriteLine("\n\n\n\t\tPlease enter any key to exit ...");
}

Console.ReadLine();

While I was editing this I doubted it was C# when I saw `readingNumber:` on its own as a line, then I saw the [goto statement](https://msdn.microsoft.com/en-us/library/13940fs2.aspx). You might want to read something like this SO question: ["*What is the best way to avoid goto?*"](http://stackoverflow.com/q/12493505/1364007). Avoid using `goto` at all costs - there's such a thing as "`goto` hell" when the wanton use of `goto` statements causes spaghetti code which is very hard to debug. — Wai Ha Lee, Mar 11 '15 at 00:02

Dmitry Bychenko · Answer 1 · 2015-03-10T15:48:55.520

1

String palindrom is if either

it contains less than 1 character
Char at[0] == Char at [Length - 1] and inner string [1..Length - 2] is palindrom

So

public static Boolean IsPalindrom(String value) {
  if (null == value)
    return true; //TODO: or false or throw exception

  if (value.Length <= 1)
    return true;
  else  
    return (value[0] == value[value.Length - 1]) && 
           (IsPalindrom(value.Substring(1, value.Length - 2)));
}

If you want to test a number (e.g. 12321) for being palindrom, just convert it to string:

  int value = 12321;
  Boolean result = IsPalindrom(value.ToString(CultureInfo.InvariantCulture));

edited Mar 10 '15 at 15:48

answered Mar 10 '15 at 15:43

Dmitry Bychenko

180,369
20
160
215

I model you on writing/dabbling in algorithms. Could you look at my contemporary way Mr.Bychenko ? – Soner from The Ottoman Empire Jul 12 '22 at 16:11

Wai Ha Lee · Answer 2 · 2015-03-10T23:41:20.960

In general, it's good practice to NOT use Substring recursively as you end up creating LOTS of strings (in fact, here the memory usage for all the strings increases quadratically with the length of the string).

The MSDN reference for String.Intern says:

The common language runtime conserves string storage by maintaining a table, called the intern pool, that contains a single reference to each unique literal string declared or created programmatically in your program. Consequently, an instance of a literal string with a particular value only exists once in the system.

For any given string, say, "abcdedcba", if recursively using Substring, you'll end up putting "bcdedcb", "cdedc", "ded", and "e"into the intern pool needlessly.

Instead, it's better to pass the same string in to the recursive method, and vary two indices which determine which characters are being compared. String functions are slow, but integers are value types and can be created and thrown away with gay abandon.

Implementation

/// <summary>
/// Returns true if the string is a palindrome (an empty string is a palindrome).
/// Returns false if the string is null or not a palindrome.
/// </summary>
public static bool IsPalindrome(string value)
{
    if ( value == null )
        return false;

    if ( value.Length == 0 )
        return true;

    return isPalindrome(value, 0, value.Length - 1);
}

private static bool isPalindrome(string value, int startChar, int endChar)
{
    if ( value[startChar] != value[endChar] )
        return false;

    if ( startChar >= endChar )
        return true;

    return isPalindrome(value, startChar + 1, endChar - 1);
}

Usage

public static void Main()
{
    var a = IsPalindrome(""); // true
    var b = IsPalindrome("1"); // true
    var c = IsPalindrome("11"); // true
    var d = IsPalindrome("121"); // true
    var e = IsPalindrome("123"); // false
}

Run it here on ideone.com.

score 1 · Answer 3 · answered Jul 12 '22 at 16:02

1

A trifle more contemporary way is the following method which make use of the array range feature.

// soner
static bool IsPalindrome(string s) => s.Length <= 1 || (s[0] == s[^1] && IsPalindrome(s[1..^1]));

answered Jul 12 '22 at 16:02

Soner from The Ottoman Empire

18,731
3
79
101

1

Put aside `s == null` case, this concise solution is correct; ranges are good alternative for old style `Substring` – Dmitry Bychenko Jul 12 '22 at 19:27

MRebai · Answer 4 · 2015-03-10T15:50:16.230

Run Here

    class Program
        {
            public static void Main()
            {
                var x = 545;
                var y = 548785445;
                Console.WriteLine(IsPalindrome(x.ToString()));
                Console.WriteLine(IsPalindrome(y.ToString()));
            }

            public static bool IsPalindrome(string text)
            {
                if (text.Length <= 1)
                    return true;
                else
                {
                    if (text[0] != text[text.Length - 1])
                        return false;
                    else
                        return IsPalindrome(text.Substring(1, text.Length - 2));
                }
            }


        }

A recursive algorithm for palindrome testing

4 Answers4