我一直理解，这个世界有两种人反应快。一种是想问题比较简单的人，另一种是试图把问题简单化的人。能够在脑海中建立有效的问题模型，对于快速思考很有帮助。这篇博客将教你如何理解递归。
从反证法说起
在高中的时候，一开始不理解“反证法”，因为我一直“担心”这样一件事，就是要证明“A是苹果。”，我就算假设A是香蕉，然后证明了A不是香蕉，A不是桃子，但是我并没有证明A就是苹果啊，后来我才明白，我的理解是有误的。
反证法的意思是指，如果我要证明“A是苹果”，那我先要假设A不是苹果，然后去论证这个假设是错误的，然后A就一定是了。其关键点就在于这是一个谓词，非真既假，相当于告诉你集合中只有两个元素0和1，如果不是0，那就自然是1了。
之所以讲这样一个例子，是因为我想说我一开始总担心反证法不能正确证明，是因为我没有理解反证法是一个“谓词模型”。同样的，我原来也担心过，递归这东西为啥能求出结果，等我弄懂了之后，我就再也没对此怀疑过。
汉诺塔
在大学的时候，学习编程课时，一开始我并不能很好的理解汉诺塔问题。因为我一直好奇，这东西递归一步步是如何解出答案的。
你应该可以理解当有一块盘子时，只需要将盘子从第一个塔移动到第三个塔。
那么有n块盘子的时候，当第一个塔，塔上有n个盘子时候，先将第一个塔塔上编号1至n-1的盘子（共n-1个）移动到第二个塔上（借助第三个塔），然后将第一个塔塔上最大的n号盘子移动到第三个塔上，最后将第二个塔，塔上的n-1个盘子借助第一个塔移动到第三个塔上。然后再去求解一个n-1的子问题，直到子问题是一个再简单不过的一块盘子，所以问题就这样用描述的方式就解答了。
听着很绕很烧脑是不是？只要我告诉你，理解这个问题的关键在于，递归是把一个问题，分解为当前要解决的问题+子问题。而子问题和当前要解决的问题完全独立不相关。我的意思是指没有任何上下文依赖。比如你在解决“n-1块盘子”的移动这个子问题的时候，第n块盘子完全不用关心它，甚至可以理解为第n块盘子和塔融为一体了。如果你能理解这种无关，那么你的思路就会非常清晰。你可以在脑海中“大胆”的运行这个递归问题，而不是总是放不下怀疑的心态，思考这玩意为啥就能求出结果。
01背包
背包问题的递归描述是这样的：
在前i件物品放进容量v的背包时，它有两种情况：
第一种是第i件不放进去，这时所得价值为:f[i-1][v]
第二种是第i件放进去，这时所得价值为：f[i-1][v-c[i]]+w[i]
01背包是动态规划问题。实际上用斐波纳契数列讲动态规划，还算简单，但是01背包的理解就比较复杂，实际上理解01背包也可以用同样的子问题思路，关键就是，你在决策第i件物品放或者不放，前i个物品重量限制在v0～v大小的解已经存在最优解，而你的决策并不会影响之前已经决策出的最优解，你只需要比较两个子问题的结果大小，然后继续决策就行了。而且虽然动态规划是一个二维表，但实际上，两个子问题，都锁定了一个变量，就是前i个物品，然后决策影响到的，是我们选择一个更小的背包，还是相同大小背包。
程序上的独立
从算法层面讲起，递归问题的定义，让当前问题与更小的问题无关，从编程的角度，递归通过函数调用，在栈中增长，而且栈之间是不能相互访问的。所以虽然迭代和递归有时可以相互转化，但是递归在描述问题和解决问题上面真的要好很多。而迭代则会让你共享上下文，污染外部空间（共享内存）。经常是bug之源。而递归通过函数的“自身调用”，在函数的参数和返回值之间传递是绝对安全的。
而且说到递归是“自己调用自己”的问题时，我一直很不喜欢这个定义，因为只有在函数的声明是那样的，但是在调用的时候，完全都是独立的空间，自己调用自己，会让人感觉很绕，完全想不到“子空间无关”，这个我刚才提到的概念。
其实说到空间独立，就不得不说空间污染，那么作用域的概念就非常重要了。通俗的讲，在某个空间内，内部的变量永远不会流到外部，但是内部可以在拿不到内部作用的作用域时，试图从更上一级查找。（比如python的LEGB）
所以你看并行程序设计之所以这么复杂，就是因为，上下文中间会相互影响并不独立，所以我们要用锁，还要维护乱七八糟的一致性。