漫谈递归：字符串回文现象的递归判断

前面谈到了递归的一些思想，还有概念上的一些理解，这里试着用递归解决一些问题。比如回文。

回文是一种字符串，它正着读和反着读都是一样的。比如level,eye都是回文。用迭代的方法可以很快地判断一个字符串是否为回文。用递归的方法如何来实现呢？

首先我们要考虑使用递归的两个条件：

• 第一：这个问题是否可以分解为形式相同但规模更小的问题？
• 第二：如果存在这样一种分解，那么这种分解是否存在一种简单情境？

先来看第一点，是否存在一种符合条件的分解。容易发现，如果一个字符串是回文，那么在它的内部一定存在着更小的回文。 比如level里面的eve也是回文。 而且，我们注意到，一个回文的第一个字符和最后一个字符一定是相同的。

所以我们很自然的有这样的方法：

先判断给定字符串的首尾字符是否相等，若相等，则判断去掉首尾字符后的字符串是否为回文，若不相等，则该字符串不是回文。

注意，我们已经成功地把问题的规模缩小了，去掉首尾字符的字符串当然比原字符串小。

接着再来看第二点， 这种分解是否存在一种简单情境呢？简单情境在使用递归的时候是必须的，否则你的递归程序可能会进入无止境的调用。

对于回文问题，我们容易发现，一个只有一个字符的字符串一定是回文，所以，只有一个字符是一个简单情境，但它不是唯一的简单情境，因为空字符串也是回文。这样，我们就得到了回文问题的两个简单情境：字符数为1和字符数为0。

好了，两个条件都满足了，基于以上分析，我们可以很容易的编写出解决回文问题的递归实现方式：

#include "stdio.h"
#include "string.h"

int main(void)
{
    int n, rs;
    char str[50];

    printf("请输入需要判断回文的字符串：");
    scanf("%s",&str);

    n = (int)strlen(str);
    rs = is_palindereme(str, n);
    printf("%d ", rs);
}

int is_palindereme(char *str, int n)
{
    printf("Length: %d \n",n);
    printf("%c ----- %c\n", str[0], str[n-1]);
    if(n == 0 || n == 1)
        return 1;
    else{
        //printf("%d, %d\n", str[0], str[n-1]);
        return ((str[0] == str[n-1]) ? is_palindereme(str+1, n-2) : 0);
    }
}

程序运行结果为：

请输入需要判断回文的字符串：level
Length: 5
l ----- l
Length: 3
e ----- e
Length: 1
v ----- v
1

延伸阅读

此文章所在专题列表如下：

1. 漫谈递归：递归的思想
2. 漫谈递归：递归需要满足的两个条件
3. 漫谈递归：字符串回文现象的递归判断
4. 漫谈递归：二分查找算法的递归实现
5. 漫谈递归：递归的效率问题
6. 漫谈递归：递归与循环
7. 漫谈递归：循环与迭代是一回事吗？
8. 递归计算过程与迭代计算过程
9. 漫谈递归：从斐波那契开始了解尾递归
10. 漫谈递归：尾递归与CPS
11. 漫谈递归：补充一些Continuation的知识
12. 漫谈递归：PHP里的尾递归及其优化
13. 漫谈递归：从汇编看尾递归的优化

本文地址：http://www.nowamagic.net/librarys/veda/detail/2316，欢迎访问原出处。