递归 —— 你值得拥有
共 4460字，需浏览 9分钟
· 2019-12-20
相信很多人对递归的认知是这样的：
function foo() {
foo();
}
就是一个函数在它内部又调用了自己，简称自我调用。
刷新对递归的认知
如果遇到一个问题，你说你可以用递归解决，基本上大家都会觉得这不是一个最好的方案。
如果另一个人说，他不用递归就可以搞定了，基本上大家都会认为他的方法比你的牛逼些。
怎么说呢，就是大部分人可能对递归都是有点“偏见”的，或多或少罢了。
我想这可能和递归的执行过程有关，一个函数在还没有执行完时又调用了自己，这就需要保存函数调用的当前上下文，然后发起一个新的函数调用。
结果又是这样子，又是在函数还没有执行完时再次调用了自己，那就需要继续保存本次函数调用的上下文，然后再发起一次新的函数调用。
如此这般下去，会造成调用层次嵌套太深，保存的函数调用上下文过多，然后把线程栈空间用完了，最后就是StackOverflow了。
这是事实，任何人都无法辩解，自然我也不例外。但我还是建议那些对递归不太喜欢的开发人员要适当的改变自己的这个看法。
备注：尾递归可以避免这个问题。
把递归看作是函数的自我调用，是一种十分狭隘的思想。我们应该提高自己的认知，推而广之的来看递归，就会发现：
递归就是某种形式的不断重复，结果构成了闭环。（当然，最后是可以跳出来的。）
按照这个观点去思考，你会发现我们生活在递归中。不相信吗？一起快速看看吧。
2019的春夏秋冬即将过完，马上就又迎来了2020的春夏秋冬，一年四季的变换无穷无尽何时休。这是不是递归？当然是啦。
还有每天24小时的昼夜交替永不停歇。还有每天上班打卡下班回家，天天如此仿佛看不到尽头。还有老子生儿子，儿子生孙子，世世代代的生老病死。
还有电磁波的传播，就是变化的电场产生了磁场，变化的磁场又产生了电场，电场和磁场相互交替着向前传播。
以上这些都可以认为是递归。所以不要只看表明现象，要看事物的本质是不是某种形式的重复，且形成了闭环，最后在适当的条件下又跳出了这个环。
总之，接受递归，将会拥有一片更为广阔的天地。
识别出构成递归的要素
有些递归很明显，一眼就看出来了。有些则很含蓄，需要仔细甄别才行。这就造成有些简单、有些很难。
但是当你写出来后，又发现其实也没有那么难，我相信这种感觉应该都有过。今天就以科学的分析方法来搞一把，看看结论是什么？
根据上一小节的描述，我们知道递归必然是一种重复，而且还有跳出这种重复的条件。
因此，我们认为递归至少包含两个要素：重复体和跳出条件。
结合一个最简单的示例来检验一下。比如，求N个自然数的和。就是
n + (n - 1) + (n - 2) + ... + 2 + 1
这样一个表达式的值。
我们很容易写出一个递归来：
function sum(n) {
if (n == 1) {
return 1;
}
return n + sum(n - 1);
}
不难看出这里的重复体就是sum()函数自身，因为它一直在自我调用。而跳出条件也十分明显，就是n == 1。
这种最简单形式的递归是符合我们刚刚提出的观点的，再来看另一个稍微复杂点的情况。
假如在草原上遇到一群动物在奔跑，普遍人就认为这可能就是一次普通的集体活动而已，但是专家可能识别出它们是在集体迁徙。
这区别是很大的，迁徙的话就是从A地到B地，等来年某个时候再从B地回到A地，这不就是递归嘛，而普通活动则肯定不是递归。
这里的问题是为什么“专家”能够看出是递归，而我们普通人看不出呢？这是因为参与递归的A地和B地相距太远，我们缺乏专业知识，识别不出来。
根据这个，我们就又可以得出两个要素：递归中的重复体可以是两个和这两个重复体互相调用的条件。
我们还使用求自然数和的例子，但是加一个限制条件，奇数和偶数分别用两个函数来处理。
下面代码仅仅用作示例，可能没有什么实际意义：
function oddSum(n) {
if (n == 1) {
return 1;
}
if (n % 2 == 1) {
return n + evenSum(n - 1);
}
return evenSum(n);
}
function evenSum(n) {
if (n == 2) {
return 2;
}
if (n % 2 == 0) {
return n + oddSum(n - 1);
}
return oddSum(n);
}
不难看出oddSum()和evenSum()这两个函数都是重复体，它们互调对方，合起来构成递归。互调对方的条件就是n是奇数还是偶数，跳出条件就是n是1或是2。
既然重复体可以有两个，那么就可以有三个甚至更多，不过原理都是一样的。因此我们可以得出递归三要素：
1）识别出重复体，可能是多个。
2）如果是多个，识别出重复体间的互调和自调条件。
3）识别出跳出条件，以便结束。
通俗的讲就是，重复体越多越复杂，它们既可以互相调用也可以自我调用，一个重复体可以调多个重复体，多个重复体也可以调用一个重复体。
而且会有很多调用条件，只有在条件满足某个重复体的时候才会发起对它的调用。而且在自我调用时也要满足某个条件。
如果把重复体看作节点，把调用关系看作边，十分复杂的递归就会变得像蜘蛛网一样密密麻麻的。
小试牛刀not分配律
利用上面的结论，再结合一个相对有意义的案例，来试试看。之前遇到一个逻辑表达式求值的问题，表达式由操作数、and、or、not和括号组成。
一开始为了简单，就做了个规定，not只能作用于操作数，不能作用于括号。就是这样子的：
not A and not B 是可以的，not (A and B) 是不可以的。
后来需求有变，确实也需要支持not作用于括号的这种情况。但是我又不想修改解析表达式的代码，好像也不太好改。
因为表达式字符串转换成表达式树之后，括号就没有了。它本来就是起一个优先级的作用，因为树的节点本身就带有优先级了。
关键一开始就没有这方面的设计，所以要改的话，改动量较大，后来转念一想，我何不把not分配到括号里面呢，就像这样：
not (A and B) -> (not A or not B)
这样是完全等价的，而且表达式解析代码一点也不用改。
所以接下来要做的就是，通过纯字符串操作把not分配到括号里面，然后再解析，我把它称为not分配律。
其实这个不用递归使用while循环也可以，只需要自己维护好进入/退出括号这个上下文和对应的not情况即可。
不过这里还是采用递归实现。仔细分析后发现，我们只需处理not后面是左括号的这种情况，如果不是只需原样不动就行。
这样的问题一时不太好想，那就把所有的情况都列出来，找找规律。
1）没有括号没有not的，A or B
2）没有括号有not的，not A or not B
3）有括号没有not的，(A or B) and C
4）有不在括号前的not的，(not A or not B) and not C
5）有在括号前的not的，not (A or B)
看完之后发现，其实这里也存在不需要递归的情况，比如前四种一个循环就可以了。第五种有了括号前面的not后就需要递归了。
可能乍一看认为也不需要啊，但是要写成这样呢：
not (not (not (A or B)))
可以很多层嵌套，这回肯定需要了。所以：
当not遇上左括号这种情况就是一个重复体。调用这个重复体的条件自然就是not遇上左括号。
只有这一个重复体吗？我们尝试把表达式再嵌套一层看看：
not (A or not (B or C) and D)
当not分配到括号里后，会与里面括号前面的not抵消掉，这样里面的括号只需原样不动就可以，括号结束后，not继续与括号后面的部分进行转换。
所有内部括号这部分相当于一个独立的上下文，外层括号是一个上下文，这涉及到从外层上下文进入内部上下文，然后再退出内部上下文回到外层上下文。
所以内部的括号虽然最终没有not，但也是一个重复体，于是就有：
在上面那个重复体里的括号也是一个重复体，调用条件就是在上面那个重复体里遇到左括号。
通俗一点说就是带not的括号里面出现了不带not的括号。
还可以再复杂点，再增加一层嵌套看看：
not (A or not (B or C and not (D or E)) and F)
通俗的说就是带not的括号里是不带not的括号，该括号里又有了带not的括号。
即三层括号嵌套，这样我们就需要在第二个重复体里调用第一个重复体，调用条件依然是在第二个重复体里遇上not加左括号。
这样这两个重复体之间就形成了互相调用，调用条件是在自己的重复体内遇到了括号或not加括号。造成互相调用的原因就是括号的嵌套和not的存在。
所以递归调用确实有很多的上下文，这些上下文会自动保存和还原，因此如果采用非递归形式的话，这个上下文就需要自己保存和还原了。
而且有些递归非常复杂时，基本上转变为非递归的形式非常困难，有的可能转不成。
最后总结一下：
整个过程既有非递归部分也有递归部分。递归部分有两个重复体。从非递归部分只能进入递归部分的第一个重复体，进入条件是遇上not加左括号。
这两个重复体可以互相调用，也可以自己调自己。调用条件上面已经说的很明白了。这两个重复体的退出条件都是遇到右括号。
当所有嵌套调用的重复体全部都退出时，递归部分就执行完毕，接着进入非递归部分继续执行，然后还可以再次进入递归部分，然后再退出。
直到最后表达式字符串处理完毕，就全部结束了。最后再重复下这句话：
递归确实有一定的难度，但是当你写出来后，发现也不过如此。
发现递归四要素理论
我们发现在递归的三要素上还要再加一个要素，就是重复体也会有退出条件，控制着某个重复体的执行结束。
这样就构成了递归四要素：
1）识别出重复体，可能是多个。
2）如果是多个，识别出重复体间的互调和自调条件。
3）如果是多个，识别出重复体的退出条件。
4）识别出跳出条件，以便结束。
个人感觉：
使用递归解决问题，思考起来较难，但代码写起来简单。
使用while循环解决问题，思考起来简单，但代码写起来较难。
自我发问：
那么我们什么时候才能跳出自己的递归呢？答案是，鬼知道。
请问鬼是谁？我怎么知道，你去问鬼啊。WTF！
推荐阿里云推广服务器89/年，229/3年，买来送自己，送女朋友马上过年再合适不过了，买了搭建个项目给面试官看也香，还可以熟悉技术栈，(老用户用家人账号买就好了，我用我女朋友的?）。扫码购买
我这里还有购买后的教程：搭建教程，从0开始一步一步带你搭建 
两年呕心沥血的文章：「面试题」「基础」「进阶」这里全都有！