时间戳

首页 > 解决方案 > “如何在 C++ 中不使用反向函数递归调用回文数？”

c++ - “如何在 C++ 中不使用反向函数递归调用回文数？”

问题描述

这是一个递归函数的程序，它检查一个数字是否是回文。这里没有使用反向函数。这对我来说似乎很复杂。

我无法理解此示例中的递归代码是如何工作的。因此，我需要一个带有试运行的演示或该程序中算法的详细描述。

int onedigit(int a)
{
    return (a>=0 && a<10);
}
bool isPalUtil(int num, int *duplicate)
{
    if(onedigit(num))
    return (num == (*duplicate)%10);

    if(!isPalUtil(num/10, duplicate))
    return false;

    *duplicate /= 10;

    return (num%10 == (*duplicate)%10);
}
int isPal(int x)
{
    if(x < 0)
    x = -x;
    int *dup = new int(x);
    return isPalUtil(x,dup);
}

标签： c++recursion

解决方案

首先考虑会发生什么num：

当您进行递归调用时，您会删除最低有效数字。你一直这样做，直到你只剩下最重要的数字。

当您从递归调用返回时，将恢复先前“删除”的数字。

让下面的每一行新行代表一个调用/返回然后num会做：

num:
12321   // Call path
1232
123
12
1       // Now the return path starts
12
123
1232
12321

当只剩下一位时，将其与副本的最低有效位进行比较，并开始返回路径。

在返回路径中，重复的最低有效数字（即刚刚匹配的那个）被删除，并完成新最低有效数字的比较。这样，结果比较就像“反向”比较。

所以num会这样做：

num:                     *duplicate:
12321                    12321
1232                     12321
123                      12321
12                       12321
1                        12321   // Compare least significant of both
12                       1232    // Compare least significant of both
123                      123     // Compare least significant of both
1232                     12      // Compare least significant of both
12321                    1       // Compare least significant of both

注意：

该算法的一个重要部分num是按值传递，以便在返回后恢复它的值 whileduplicate是一个指针，从而允许所有级别的递归更改指向的值。

失败案例的示例如下所示：

num:                        *duplicate:
123421                      123421
12342                       123421
1234                        123421
123                         123421
12                          123421
1                           123421   // Compare least significant of both
12                          12342    // Compare least significant of both
123                         1234     // Compare least significant of both
  ^                            ^
  Compare fails so false will be returned all the way up

所以在返回路径中，最低有效位num是从左到右的原始数字的数字，而重复的最低有效数字是从右到左的原始数字的数字。

因此，通过比较返回路径中的最低有效数字，算法可以检查该数字是否为回文。

推荐阅读