Think in 递归

     网上写递归的文章可以用汗牛充栋来形容了,大多数都非常清晰而又细致的角度上讲解了递归的概念,原理等等。以前学生的时候,递归可以说一直是我的某种死穴,原理,细节我都懂,但是不管是在如何运用或者如何试试算法题上真是有一种“听过好多道理,依然过不好这一生的感觉”。经常感觉信心受挫,力不从心呐。但是到后来如果不要去太纠结这些细节,原理反而豁然开朗,突然我发现我可能是明白了。所以我的这篇瞎扯是想从一个宏观的角度来扯扯递归算法,所以我起了这么个土洋结合的题目,因为全因为的话显得略装b,但是我又实在找不到合适而又简洁的中文来表达“think in”的这个意思。 无论如何,希望看完这篇文章的人不再对递归感到混乱,也许能自己运用递归解决算法问题或者实际问题,最重要的是希望能帮助一些曾经和我有一样困惑的人。

     虽然是嘴上说的是想重点从宏观上写一些如何运用递归,但是内心还是想先扯一下递归的概念的。递归,我虽然没查到他的最开始的出处,但是我感觉应该不是从计算机这里创造出来的,这两个字翻译的也挺传神,传递和归约,但是如何用好这个传递和归约就是过不好这一生的那一部分了。我一直觉得递归的思想颇有点“站在领导层”的感觉,为什么这么说,因为在设计递归算法的时候,你只需要设计出大问题化小问题的递归算法,很多时候都是简单的几个函数就能解决,剩下的具体都交给编译器或者说语言本身来解决。但是正是这种特性,往往导致我们这种底层人民长期的思维习惯在灵活运用上会有点觉得“这尼玛就行啦?”或者"还是有点不放心呐“这种感觉,正是这些感觉往往会导致一种混乱,从而舍本求末,造成在灵活运用上的困难。所以,我一直觉得,在设计递归算法的时候,要有四步,第一先分析最简单的情况,第二,从小问题中总结大问题的规律,第三要写出伪代码,然后再写真的代码。

     我会把递归问题分为三大类:

     第一类,别细想,想多了绝逼能给你整懵圈型。 这类问题的有两个特点,一个是定睛一看,按普通算法想感觉完全一下子不知道从哪里下手,第二个就是当你意识到这肯定得用递归啊,但是往往你会陷入一个怪圈,在你想出递归算法之后,你会自然的去验证。关键是,在你演这个时候或者试着仔细分析这个题目的时候会发现脑子越来越乱,越来越不够使,最终本来想的透彻无比的问题就剩文字本身是清晰的了。这类问题比如想这种:

    “一个有n阶的楼梯,每次可以选择上一阶或者两阶,请问有多少种登顶的方法?” 这个问题是一个烂大街的递归问题,如果你不用递归的思维去想,会觉得这玩意儿应该怎么弄?但是这个问题使用递归的思维大问题化小问题其实很容易就想出解法。先想一阶楼梯,两阶楼梯,三阶楼梯试试,写出伪代码/步骤试试:

1. 如果只有一个阶梯,只有一种方法,就是一次性上一阶,直接登顶,应该返回1

     2. 如果有两个阶梯,两种办法,一次上一阶,上两次,或者一次直接上两阶,应该返回2.

     3. 如果有三个阶梯,那么可以选择1+1+1,1+2,2+1。

     甚至你可以试试4,5,6阶数的楼梯,但是你会发现的你的脑子到后面根本无法在继续思考下去了,会有种大脑不够用的感觉,这就到了该总结规律的时候,你会发现其实你上第n阶楼梯的方法数目就等于你上第n-1阶楼梯的方法数目加上上第n-2方法的数目,为什么?因为在这两种情况下,只需要一步你就可以登顶了,在方法的数目上你已经没得选了。到这里,你会忍不住的想去从细节上证明你的想法,别控制,你试试按照你的思维走下去。你会想,我靠,这么简单,真的吗?我来想想到n-1阶的时候是怎样的呢?你会发现很快你就会到我上面的那个懵圈状态,反过来你会怀疑你的算法是不是对的,这样你就会挂了。所以,试着仅仅从数学或者宏观的角度证明一下这个算法,相信自己也相信计算机。所以这个问题的代码很简单,就这么几行:

 1 int climbStairs(int n)
 2 
 3 {  
 4     if(n==1) return 1;
 5 
 6     if(n==2) return 2; 
 7 
 8     else return climbStairs(n-1) +  climbStairs(n-2);
 9  
10 }

    就是这样,很多时候用递归的方式解决问题写出的代码短的超乎想象,所以恐怕这也是造成自我怀疑的一个原因吧。为什么会造成懵圈,我觉得是我们大脑的堆栈不够大,相比于计算机,在不大的问题规模上已经overflow了。

    类似这样的稍微复杂但是差不太多的还有:有无限个25美分,10美分,5美分和1美分的硬币,如何组合成n美分,有多少种兑换方法? 可以按照我瞎扯的办法试试,别细想,专注于宏观设计出的算法本身,嘿嘿。

     第二类,我觉得应该叫”递归算法不容易想到“型。 这些问题设计出递归算法再反推回去不会造成脑子的懵圈, 但是想出这个递归算法容易导致自信心崩溃之类,因为这种问题一般递归解法都不太明显,比如这个吧: 

     ”反转一个字符串,abcdefg,输出gfedcba“,又是一个非常常见的问题,这个问题不是很难就能设计出一个一般的解法。利用一个循环,计算好坐标,利用一个中间变量,相互交换字符的位置,大功告成。但是这个问题完全可以换一种思维,用递归的方法去解决。还是先从最小的规模先试试,还是得先写下来:

     1. 只有一个字符,直接输出。

     2. 有两个字符,交换两个字符的位置,输出。

     3. 有三个字符,中间一个字符不变,交换两边的字符,输出。

     4. 有四个字符,前两个字符互相交换,后两改字符互相交换,然后两部分再两两交换,输出。

     5. 有五个字符,中间一个字符不不变,其余的重复4.

    这个算法用写出每一部分的方法很难总结出规律,但是如果真的写出五个字符,在纸上试试,其实很容易就能找到分别交换两个部分再互相交换的规律。这可能就是这里面最难的”算法设计“的这个部分吧。所以这个问题写成代码大概应该是这样的:

    string reverseString(string s) {
        if(s.length() == 2)
        {
           string strTmp;
           strTmp += s[1];
           strTmp += s[0];
           return strTmp;
        }
        else if(s.length() == 1)
        {
           return s;
        }
        else if(s.length() == 0)
        {
           return s;
        }
        else
        {
            if(s.length()%2 == 0)
                return reverseString(RightStr(s))+reverseString(LeftStr(s));
            else
                return reverseString(RightStr(s)) + s[s.length()/2] + reverseString((LeftStr(s)));
        }

    }

    这种问题,一般会沮丧在想出这个算法上,但是我觉得其实对于我们这种普通人来说,计算机里的算法设计多还是停留在多见世面才能解决问题的层面。毕竟那种能独立设计,思考出一个算法的人凤毛麟角,所以,其实这个时候不必沮丧和失去信心,你现在不知道怎么做可能仅仅是见到的太少,你要见多了,大部分问题都能解决。

    第三类,我把它叫”递归才是最好的理解答案思路型“,这种问题最常见于树啊,图啊之类的问题,简直不甚枚举。特点是,这种问题你会发现你会自然的用递归的思想去思考这个问题,所以说,最后的代码如果是以递归的形式呈现会跟符合人本身的自然思路。 随便举一个比较简单的例子:

      ”计算一个二叉树所有左叶子节点的权重值的和"。看着这个问题思考,思路很容易就流淌出来,一个二叉树所有左叶子节点权重值的和就等于一个左子树的左叶子节点的权重值加上右子树的左叶子节点的权重值。“递”的部分很容易就想出来了,那么“归”的部分就可以从最小的问题思考一下,因为“归”应该满足最小的问题集合,假设这个树只有一个根节点,那么可能返回0,如果是一个根节点带一个左叶子节点,那么应该返回这个左叶子节点的值,因为是左叶子节点的值的和,所以所有的右子树在这里有可以化为另一个“递”。貌似有点乱了,列一下可能能清晰一点:

      1. 如果只有根节点,返回0。

      2. 如果根节点有左叶子节点,返回左叶子节点的值。

      3. 继续遍历根节点的右子树。

      4. 遍历所有当前的左子树和右子树,重复1-3。

    这样再写成代码就很容易了:

 int sumOfLeftLeaves(TreeNode* root) {

        if (!root) return 0;

        if (root->left && !root->left->left && !root->left->right) {

            return root->left->val + sumOfLeftLeaves(root->right);

        }

        return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);

    }

    这类问题你会发现递归写出来的代码更符合人的自然思维逻辑,比起那些传统方法可能更容易展开和理解。

     好了,上面就是我的一些胡扯,其实就像开头说的,递归主要是"递“和”归“,先从宏观的方面找到传递的路子,再用最小的问题集合找到归约的条件和返回,大部分递归问题都很很容易能想出来。如果让我选一个例子来最初步的理解递归算法,我会十分推荐快速排序,你可以就看一遍快速排序的算法描述,然后把它实现出来。不要小看实现一段某某算法,作为工程师,我觉得实现某种算法或者功能比设计算法更符合本职工作,也是一种非常大的能力。就像造汽车的和赛车手,造汽车的不一定开的好车,但是肯定会开车。赛车手大部分都不能独自制造发动机,但是肯定懂点基本原理。所以说想不出来算法也并没有什么好沮丧的。

     最后,希望这篇文章能帮助需要的人。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

POJ2318 TOYS 判断点与直线位置关系 【计算几何】

Calculate the number of toys that land in each bin of a partitioned toy box.

1063
来自专栏Java成长之路

【c语言】简单学生信息管理系统

1.有10个学生,每个学生的数据包括学好、姓名、4门课的成绩、总成绩和平均成绩。从键盘输入10个学生的数据(包括学好、姓名以...

1.1K1
来自专栏一个会写诗的程序员的博客

编程范式 (Programming paradigm)

范,模范、典范也。范式即模式、方法。常见的编程范式有:函数式编程、程序编程、面向对象编程、指令式编程等。

3321
来自专栏Web行业观察

盘点那些奇形怪状的编程语言

有的语言是多面手,在很多不同的领域都能派上用场。这类编程语言叫 general-purpose language,简称 GPL。大家学过的编程语言很多都属于这一...

2632
来自专栏我杨某人的青春满是悔恨

函数式思维

自从大四看了三章《SICP》之后我就自诩为一个函数式编程爱好者,之前也在公司分享过一个 Haskell 的 Topic,效果非常糟糕,讲到后来已经没剩几个人了,...

1001
来自专栏趣学算法

数据结构学习秘籍

网络上太多的同学吐槽被虐,如滔滔江水连绵不绝,数据结构太难了!真的很难吗?其实数据结构只是讲了三种:线性结构、树、图。到底难在哪里呢?通过调查了解大概有四个原因...

1192
来自专栏企鹅号快讯

C+虚函数实现多态性的思考

相信这篇文字已经被这个晦涩的标题直接给PASS了,但笔者想把这些晦涩的概念说的生动些,C++和Python在编程思想上有很多是一致的,比如面向对象的思想,面向对...

21310
来自专栏aCloudDeveloper

算法导论第二章小试牛刀

Author: bakari   Date: 2015.9.11 《算法导论》真是一本让人又爱又恨的书,爱自然是因为它精简凝练的算法呈现,读来让人欲罢不能;至于...

28210
来自专栏tkokof 的技术,小趣及杂念

Sweet Snippet 之 Bounce Setting

  又是一篇Sweet Snippet,自己看来都觉得过小,不足以成篇,不过自觉有些趣味,也就随便记一记了,权当自娱自乐 :)

581
来自专栏C语言及其他语言

初学C语言的学习计划

背景:很多同学在学习C语言的过程中,常常会遇到这样的问题,即“教材看完了,知识点也懂,但写不出来程序”,这段时间,我们通过长期与有多年C语言研究经验的教授、教师...

3624

扫码关注云+社区

领取腾讯云代金券