使用递归检查整数是否回文，无需使用任何额外的反向函数

Question

我一直在编写一个

is_palindrome(int num)

函数，它接受一个整数并返回 true 或 false。我想到了反转整数，然后与原始整数进行检查。为此，我需要一个额外的

reverse()

函数。但我想知道是否有一种方法仅使用一个递归函数来检查回文。

Answer 1

虽然不需要递归算法来确定数字是否是回文，但我能想到的最简单的递归算法如下：

伪代码：

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)
}

该算法比较第一个和最后一个数字，删除它们，并用修剪后的数字递归地调用自身，直到检查完所有数字或发现不匹配。

Answer 2

您可以使用递归函数和垫片来完成此操作。这是检查数字是否为回文的递归函数。

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);
}

然后，您需要一个垫片来实现带有您签名的功能。

-

前面的数字不能是回文，因此您需要在递归之前进行检查。

然后，您应该计算最高位除数，以便能够从您的号码中提取第一位数字。

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);
}

请注意，该算法不依赖于基数，但无效的基数（小于 2）也应该接受适当的处理，具体取决于您想要的方式，并且可以用您正在使用的语言报告错误。

Answer 3

除了已接受的答案之外，还需要检查该数字是否包含 0。
考虑示例 10401。删除第一个和最后一个数字后，数字变为 40。下面是我的实现，没有将数字转换为字符串并处理 0 的情况。

import math

def isPalindrome(n):

    if(n < 10): #base case
       return True

    digit_count = math.floor(math.log10(n))+1 #no. of digits
    max_place_value = 10 ** (digit_count-1) #place value
    first_digit = n // max_place_value
    last_digit = n % 10
    if(first_digit != last_digit):
        return False
    n = n - first_digit * max_place_value #removing 1st digit
    zeroes_removed = (digit_count-1) - (math.floor(math.log10(n))+1)
    n = n//10 #removing last digit

    while(n > 0 and zeroes_removed > 0):
        if(n % 10 != 0):
           return False
        n = n//10
        zeroes_removed -= 1
           
    return isPalindrome(n)
    

说明：
位数 = 总数数字中的位数
max_place_value = 第一个数字的 10 次方值
Zeroes_removed = 编号。删除第一个数字时删除的零的数量。例如：100401。删除 1 后，int 值为 401。所以不是。删除的零是 2。

while 循环删除了确切的编号。截至 Zeroes_removed 值的零数。如果同样没有。不存在，我们可以说它不是回文。

检查的测试用例：
print(isPalindrome(1001)) #True
print(isPalindrome(10451)) #False
print(isPalindrome(10401)) #True
print(isPalindrome(10441)) #False