大厂裁员，35岁现象，这些热搜关键词想必刺痛了无数码农的心。大家当初投身于这行，谁也不想干个十年就被扫地出门，然后就无人问津了。不说一定就财富自由，起码能保持一个体面的生活吧。
虽然这个行业会洗牌，大厂为了盈利会砍掉亏损的业务，但互联网行业并不会消失，技术过硬的码农根本无惧于行业的动荡。或许在大浪淘沙之后，他们会获得更好的机会，在下一次增长周期中满载而归。
我们也听过太多次，要成为优秀的程序员，而不是只会CRUD的码农。那怎么区分优秀与平庸呢？
是否具备计算思维可以作为一个重要判断依据。如果要为判断依据找一个技术点，那么递归就是很好的考察点。
说起递归，凡是计算机专业的同学，在大学里就已经学过了。要问起来，他们一句话就给解释了：函数里可以调用自身的函数。
再问可以解决什么问题？学得更好些的，会举出汉诺塔、八皇后问题等。如果继续问下去，为什么要用递归来解决，用别的方法行不行？估计得到的回答是书上就这么写的，能解决问题就行，还要想那么多干什么。
如果只是从形式上知道递归，那基本上也就停留在应付考试，解答笔试题的水准。在工作中遇到类似问题，只会写出高射炮打蚊子的代码来。业界流传一个杰出程序员能顶五十个普通程序员，不是没有道理的。
不服气的话，就看一个笔试题吧：有一层20级的楼梯，你从第一级开始往上走，每次可以跨一级或者两级，直至20级。比方说：1,3,5,6,8,10,12,14,16,18,20就是一种，那么从1级到20级之间可以有多少种走法？
也许我前面说了那么多递归，你的第一反应还是从第一级开始逐级研究有多少种可能，然后寄希望找到规律，总结公式来解决问题。这种从前往后，从小到大的推导方式符合人的自然直觉，也被称为递推方法（Iterative)。
所以在面试中，你要么给出一个自己也知道不对的答案；要么两手一摊，说这题算出来要花的时间太长了。
用递归的思想来解决，假设F(20)是最终解，那么要走到20级，就得先走到19或者18级。那么F(20) = F(19) + F(18)，可以总结出递归公式：F(n) = F(n-1) + F(n-2)。
那么第一级只有一种情况，就记为F(1) = 1，第二级为F(2) = 2，第三级为F(3) = 3，第四级为F(4) = 5 ……
看到这里，你可能会猛拍大腿说，这不就是非波那契数列吗，这个我也会啊。所以最终结果F(20) = 10946。递归你会，非波那契你也会，就是计算思维没学会。
好了，递归到底是一种怎样的计算思维？
前面我们说了递推思维是什么，那递归（Recursive）则相反，它是一种逆向思维。递归是自顶向下，先全局后局部的思维方式。
递归有两个优点，第一是解决当前的一步问题，就能解决全部问题。例如上面计算梯级走法问题里，要计算20级，只需要关心19级与18级就可以，以此类推。
第二就是每一步的解决方法都是相同的，程序只要反复调用就可以。这就是调用自身的形式，但必须要有结束条件，否则就产生无法终止的函数调用了。
建议各位再回头去仔细研究一下汉诺塔和八皇后问题吧，它们之所以会被作为经典案例写在教科书里，就是因为以递推方式来解决近似于不可解。例如八皇后问题让数学大神高斯都栽了跟斗，但一个刚学会编程的小白用递归算法就能得到准确解。
是你比高斯还神吗？我知道你也不会去妄想。这就是递归计算思维，它能将许多现实难题转化为计算机可解决的算法，从而发挥出计算机的真正能力。
在递归算法中，我们需要将运算过程的中间状态保留下来，当走到结束条件时再逐级回溯，中间状态值就在这个过程中被使用，直至计算完成。
如果仅用函数调用自身的方式，把中间状态都保留在局部变量里，那么问题来了。
首先是调试难。如果结果有误，而调用次数有成百上千次，你要查看某一次的状态，你在调试器里要怎么看？
其次是开销大。函数调用会占用进程运行资源，如果调用次数过多，很容易挤占系统资源。结果是将解决问题，变成了制造问题。
掌握了思想是第一步，接下来在工程实践中做好，才是成为优秀程序员的最后一步。要解决上节的难题，就要用到两个经典的数据结构：堆栈（stack）与队列(queue)。
我想你也许又喊出了声，这两个都学过，堆栈支持后进先出(LIFO，Last-in First-out)，或者先进后出(FILO, First-in Last-out)，队列支持先进先出（FIFO, First-in First-out）。
很好，你也知道我们不会满足于通过考试或者拿到offer，那让我们继续探究堆栈与队列在递归中的工程实践吧。
一道典型面试题：实现简单的计算器，不考虑括号的四则运算，要满足先乘除后加减。
它考察的就是对堆栈的使用和掌握情况，将数字和运算符号逐个压栈，根据运算符号优先级调整中间计算结果。它显然极大方便代码调试，也让程序结构清晰易读。
队列的应用也相当广泛，例如消息处理、缓冲区实现，以及树的遍历等。
对于视频压缩处理来说，就是对画面不断地逐层分块，直至对最小块完成编码，然后返回上层，完成整幅画面编码。编码所产生的层级是相当多的，不借助于队列，那函数调用的开销就会导致编码运算不可用了。
在本文中我没有写一行代码，其实也考虑过贴上一些关键的伪代码。但还是决定不放了，因为一看到代码，也许大家又习惯性地陷入到细节中去，最后只记住一堆结论，却没有改变自己的思维。
本文的目的是想启发大家的思考，审视自己在过去工作中遇到的问题。现在回过头去看，是不是很多问题其实并不难解决。
要想在IT行业中站得稳且站得久，掌握基础计算思维太重要了，它决定了你解决问题的效率。
希望大家都可以不惧裁员潮，逆风成长，获得更好的机会。
本文内容参考《计算之魂》第2章 逆向思维——从递推到递归
联系客服
