我一直在寫一個is_palindrome(int num)函式，它接受一個整數并回傳真或假。我得到了反轉整數的想法，然后將其與原始整數進行檢查。為此，我需要一個額外的reverse()功能。但我想知道是否有一種方法可以只使用一個遞回函式來檢查回文。
uj5u.com熱心網友回復：
雖然不需要遞回演算法來確定數字是否是回文，但我能想到的最簡單的遞回演算法如下：
偽代碼：
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)
}
該演算法比較第一個和最后一個數字，洗掉它們并使用修剪后的數字遞回呼叫自身，直到所有數字都被檢查或發現不匹配。
uj5u.com熱心網友回復：
您可以使用遞回函式和墊片來完成。這是檢查數字是否為回文的遞回函式。
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);
}
然后，您需要一個 shim 來使用您的簽名來實作該功能。前面的數字-不能是回文，所以你在遞回之前檢查一下。
然后，您應該計算能夠從您的號碼中提取第一位數字的最高位除數。
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）也應該得到適當的處理，具體取決于您想要的方式，并且可以用您使用的語言報告錯誤。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/531673.html
標籤：递归回文递归数据结构