Checking an integer is palindrome using recursion without using any extra reverse function-CodePudding

I have been writing a is_palindrome(int num) function which takes an integer and return true or false. I got the idea of reversing the integer and then check it with the original. To do that I need an extra reverse() function. But I want to know if there is a way of checking the palindrome using only one recursive function.

CodePudding user response：

While a recursive algorithm isn't necessary to determine whether or not a number is a palindrome, the simplest recursive one I could think of would be as follows:

Pseudocode:

function is_palindrome(i) {
  if (i is a single-digit number) return true
  x = first digit of i
  y = last digit of i
  if (x != y) return false
  if (i is a two-digit number) return true
  j = i without the first and last digit
  return is_palindrome(j)
}

The algorithm compares the first and last digits, removes them and recursively calls itself with the trimmed number until either all digits have been checked or a mismatch is found.

CodePudding user response：

You can do it with a recursive function and a shim. Here is the recursive function to check whether a number is a palindrome.

bool is_palindrome_impl(int number, int radix, int highest_digit_divider) {
    // First check if the number has 1 digit, in which case
    // it is a palindrome.
    if(highest_digit_divider < radix) { return true; }

    // Then check if the highest digit is different from the lowest digit,
    // in which case it is NOT a palindrome.
    const int highest_digit = number / highest_digit_divider;
    const int lowest_digit = number % radix;
    if(highest_digit != lowest_digit) { return false; }

    // Then check whether the inner part is a palindrome
    const int inner_part = (number % highest_digit_divider) / radix;
    return is_palindrome_impl(inner_part, radix, highest_digit_divider / radix / radix);
}

Then, you need a shim to implement the function with your signature. Numbers preceded by - cannot be palindromes, so you check that befor recursing.

Then, you should calculate the highest digit divisor to be able to extract the first digit from your number.

bool is_palindrome(int number, int radix = 10) {
    // Non-positive numbers are NEVER palindromes.
    if(number < 0) { return false; }

    // We first suppose that the number has less than 2 digits
    int highest_digit_divider = 1;
    int temp_number = number;
    // As long as we are proven wrong, we increase the number of digits by 1
    while(temp_number >= radix) {
        temp_number /= radix;
        highest_digit_divider *= radix;
    }

    return is_palindrome_impl(number, radix, highest_digit_divider);
}

Note that the algorithm is not radix-dependent, but invalid radixes (less than 2) should also receive appropriate treatment, depending on how you want and can report the error in the language you are using.