网上写 递归的文章可以用汗牛充栋来形容了,大多数 都非常清晰而又细致的角度上讲解了递归的概念,原理等等。以前学生的时候,递归可 以说一直是我的某种死穴,原理,细节我都懂,但是不 管是在如何运用或者如何试试算法题上真是有一种“听过好多道理,依然过 不好这一生的感觉”。经常感觉信心受挫,力不从心呐。但是到 后来如果不要去太纠结这些细节,原理反而豁然开朗,突然我 发现我可能是明白了。所以我 的这篇瞎扯是想从一个宏观的角度来扯扯递归算法,所以我 起了这么个土洋结合的题目,因为全 因为的话显得略装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阶的时候是怎样的呢?你会发 现很快你就会到我上面的那个懵圈状态,反过来 你会怀疑你的算法是不是对的,这样你就会挂了。所以,试着仅 仅从数学或者宏观的角度证明一下这个算法,相信自 己也相信计算机。所以这 个问题的代码很简单,就这么几行:

photoshop培训,电脑培训,电脑维修培训,移动软件开发培训,网站设计培训,网站建设培训 climbStairs

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

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

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

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

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

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

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

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

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

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

photoshop培训,电脑培训,电脑维修培训,移动软件开发培训,网站设计培训,网站建设培训 reverseString

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

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

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

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

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

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

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

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

photoshop培训,电脑培训,电脑维修培训,移动软件开发培训,网站设计培训,网站建设培训 sumOfLeftLeaves

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

 

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

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