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

回文符合递归的两个条件
服务器君一共花费了623.132 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

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

回文是一种字符串,它正着读和反着读都是一样的。比如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,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2316

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《重来:更为简单有效的商业思维》 贾森•弗里德(Jason Fried) (作者), 大卫•汉森(David Heinemeier Hansson) (作者), Mike Rohde (插图作者), 李瑜偲 (译者)

这本书呈现的是一种更好、更简单的经商成功之道。读完这本书,你就会明白为什么计划实际上百害而无一益,为什么你不需要外界投资人,为什么将竞争视而不见反倒会发展得更好。事实是你所需要的比你想象的少得多。你不必成为工作狂,你不必大量招兵买马,你不必把时间浪费在案头工作和会议上,你甚至不必拥有一间办公室。所有这些都仅仅是借口!

更多计算机宝库...