吴军老师的《计算之魂》部分重点摘要

递推 vs 递归

递推

我们都熟知的正向思维,从前往后、从小到大、由易到难、由局部到整体
比如5的阶乘,要从小到大一个个乘起来,即 5!= 1 × 2 × 3 × 4 × 5

这种计算思维是我们从小学到初中,到高中一直培养的习惯,甚至到现在的编程算法,我们大部分人也是运用这种思维来解决问题,比如大家面试经常遇到的问题,要求编写一个斐波那契函数f(n),计算给定 n 的函数值


递归

递归属于逆向思维,需要倒过来思考问题,从大到小、由整体到局部的思维,例如上面求 5 的阶乘,先假定4!是已知的,然后再乘以 5 即可。当然,大家会问,那 4! 怎么计算呢? 很简单,采用同样的方法,3!× 4,只要计算出 3!乘以 4 即可。同样的方法,来计算 3!,直到最后的 1!,我们知道它就等于 1 。接下来,就是倒推回所有的结果,从 1!、2!一直倒推回 5!

递归的思想有两个明显的妙处:
1、只要解决当前一步的问题,就能解决全部的问题
2、复制同一个过程,就能得到结果

要把问题通过递归的细想来解决,必须满足两个前提条件:
1、每一个问题在形式上都是相同的,否则无法通过同一个过程完成不同阶段的计算(也就是必须要满足过程可复制)
2、必须确定好结束条件,否则就像 “从前有座山” 那个故事里的情节,永远无法结束

吴军老师的原话:很多人在学计算课程时非常不喜欢递归这种不直观的逆向思维,觉得像阶乘运算这种从小到大一个个相乘就可以了,何必那么复杂地倒着计算呢?原因很简单,很多问题只有倒着才能想清楚。这一关如果过不了,在计算机领域做一辈子技术也出不了师

小编见解:递归的思维,用到的地方其实很多,比如,数据分析里面,我们正着去分析可能就不通,但我们反向去思考可能就解决了


信息编码的重要性

计算机中的所有内容都是以二进制进行编码的,比如看到的文字,在硬盘、内存、网络传输时中都是以编码形式存储的,如我们熟悉的UTF-8编码,还有最开始学计算机编程时了解的ASCII (American Standard Code for Information Interchange) 等,都是编码在计算机中的应用。信息的编码和有效表示是计算机科学和工程的基础,所以我们要理解这些基础的原理,这样有助于我们深入了解计算机。

当然,二进制编码对于人类来讲很不直观,便产生了很多便于人类辨识的等价代码,比如在MIPS处理器中,用 001000 代表加法运算,如果这样写程序几乎没有人能记住,出错也很难以检查,于是人们就将 ADD 这三个字母和 001000 这条代码对应起来。

下面以书中的案例,来更深入的向大家介绍编码的重要性,这道题 吴军老师说也是面试题,大家不妨把自己当作面试者,也一起思考下怎么来解答

案例—分割黄金问题:
泰勒是一位雇主,雇用鲍尼为自己新建的房子铺设院子里的地砖,这是一个七天工作量的活。泰勒答应一共支付一根金条作为报酬,但是鲍尼每天支付他 1/7 的工资,泰勒答应了。现在,请问你如何在金条上切两刀,保证每天正好能支付鲍尼 1/7 的工资?

(思考2分钟,再往下看)

小编看了这道题也没有想出来怎么切分,但看了答案感觉确实妙不可言,里面巧妙的运用了编码的思想,下面就给出答案

在金条的 1/7 的地方切一刀,在 3/7 的地方再切一刀,这样金条就变成了三个小金块,质量分别是 1/7、2/7、4/7 的金条质量。接下来,我们就要用1、2、4 这三个数字表示出 1 ~ 7 这七个数字,具体的表示方法如下:
1 = 1
2 = 2
3 = 2 + 1
4 = 4
5 = 4 + 1
6 = 4 + 2
7 = 4 + 2 + 1

利用上面的公式,在发工资时,泰勒第一天给鲍尼 1/7 金条质量的那一块黄金;第二天给鲍尼 2/7 的那一块,并要求对方交回先前 1/7 的那一块;第三天,再给鲍尼 1/7 的那一块,这样鲍尼就得到了 3/7 金条质量的黄金;第四天,给鲍尼 4/7 的那一块,但是要求他将之前给的那两小块金条交回;…到了第七天,把所有的黄金都给鲍尼即可。

这道题解法的关键是 1、2、4 这三个数字能够表达 1 ~ 7 的所有数字。那为什么 1、2、4可以呢?因为它们分别是二进制的 “个位数”、“十位数”、“百位数”。因为二进制只有 0、1 两个数字,所以每一个进位是 0 或者是 1 的组合,就能表示各种数字。我们不妨再用二进制把前面七个等式重写一遍就一清二楚了(二进制以 0b 开头)
1 = 0b001
2 = 0b010
3 = 0b011 = 0b010 + 0b001
4 = 0b100
5 = 0b101 = 0b100 + 0b001
6 = 0b110 = 0b100 + 0b010
7 = 0b111 = 0b100 + 0b010 + 0b001

通过这道案例题,大家是不是对编码有了更进一步的了解,原来编码这么重要,其实大家在编程时可能已经运用过,只是没有深入思考而已,以下摘自微软开发者文档,文件的操作:
编码



以上是自己实践中遇到的一些问题,分享出来供大家参考学习,欢迎关注微信公众号:DataShare ,不定期分享干货