思路
在世上，人们解决问题的方式归为两种
- 人类思路：根据生活归纳出来的，人们根据生活经验，总结提炼
- 数学思路：根据数学推理归纳，通过对应的数学公式/定理，得出的结论
人类思路
把人类的思考流程翻译成代码，就是算法
人类思路求解最大值，一般利用遍历，从左到右扫描寻找最大值。
但是实际上，一堆数字，人们也可能直接看出最大值，比如有一个9999鹤立鸡群
const array = [23,99,17,28,84]
function max(array){
let result = array[0]
for(let i = 1; i< array.length; i++){
if(array[i] > result){
result = array[i]
}
}
}
max(array) // 99
如何证明算法是对的？
- 经验
按照一般人的逻辑和经验，这个算法是对的
无法给出反例，说明这个算法是对的
通过大量的测试，发现这个算法可以满足需求
大部分程序员只需要能满足需求的代码，而不是正确的代码，非科班的程序员一般使用的解题思想
有时候，这种人类思维，因为逻辑或者认知不够严谨，在未来也会被郑面是错误的。比如最早以前人们认为地球是平的，直到后来又有了日心说。人类思路就是在不断的利用经验得出结论，再推翻再结论的过程
数学思路
完全归纳法：数学家们喜欢利用公式和定理，一步步推理得出解法，而这样的解法是具有说服力的，只要公式定理以及推理过程是没有瑕疵的，那么结论一定是对的。
但是数学思路带来的弊端也是很明显，就是需要很强的逻辑能力。回忆一下高中数学物理老师最爱说的就是：显然，我们可以得出这个结论。而如果我显然不出来，那基本是凉凉了。
还是这个例子，选出最大值，通过完全归纳法我们可以得出下面的数学公式：
n1,(k=1)
max(n1,n2,...,nk){
nk>max(n1,n2,...,nk-1)? nk:max(n1,n2,...,nk-1),(k=2,3,...)
一旦有了数学公式，我们发现可以很轻易的转化成代码,但仔细一看会觉得，这什么鬼也太难懂了吧。没错，这就是数学思想。难懂，但好像的确是对的。
const array = [23,99,17,28,84]
function max(array){
if(array.length === 1) { return array[0] }
const otherMax = max(array.slice(1))
return array[0] > otherMax ? array[0] : otherMax
}
max(array) // 99
可以发现，其实这就是递归，数学家们擅用递归来解决问题，我们也只是将定理公式代码化了。
如何证明数学算法是对的？
- 首先证明公式是对的（较难）
回忆一下高中数学，我们经常用代入法和举例法证明公式是对的，其实
max([23,99,17,28,84])
= m(23,max([99,17,28,84]))
= m(23,m(99,max([17,28,84])))
= m(23,m(99,m(17,max([28,84]))))
= m(23,m(99,m(17,m(28,max([84]))))
= m(23,m(99,m(17,m(28,84)))
= m(23,m(99,m(17,84)
= m(23,m(99,84)
= m(23,99)
= 99
通过代入法，你就会发现这就是递归，先递进，再回归的感觉，>型回调地狱
- 然后证明代码和公式等价
这一步就是用代码翻译一下了（简单）
- 总结
数学方法更容易通过形式化证明保证代码的正确性
但数学方法效率不一定高（但可以优化）
数学方法往往不够直观，普通人没有什么数学知识
一般不对变量进行二次赋值，因为数学里没有
对比
数学思路更注重形式（结构）
- 往往更加优雅/简单
- 更容易优化
- 投身于数学，有无线广阔的可能性
人类思维更注重过程（命令）
- 往往更容易执行、被理解
- 对人脑的负担更重
- 被人类的经验所局限
总结
- 复杂度守恒：复杂度不会因为任何原因降低
- 取决于把复杂度放在人脑这边，还是机器那边
- 实际上，我们可以结合两种思路，各取所长
遍历/递归/迭代
现在我们似乎可以简单的归纳
- 人类思路 ~ 遍历
- 数学思路 ~ 递归
遍历这边就不说了，因为大多数同学在写代码时，用的最多的就是for循环，所以人类思想不需要去特意修炼，顺着感觉写就可以。
接着借汉诺塔问题说说递归，汉诺塔是什么问题呢
相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。（据说当都移完了以后，已经世界末日了，因为实在太久了）
image
那这个问题，靠直觉或者经验求解（人类思路）简直就是太难了，一般我们遇到这种问题，都会看一下答案，哦！然后恍然大悟。
简单理解为，把A上面的N-1个移动到B，然后把最大的移动到C，最后把B上面的N-1个移动到C，就结束了...
但是为了做到上面这一步，你需要先把A上面的N-2个移动到C，然后把最大的移动到B，最后把C上面的N-1个移动到B...
然后你就发现你的人类思维已经想不过来了，因为实在太多步了。
数学归纳法
- 证明当n=1时命题成立
- 证明如果n=k时命题成立，那么n=k+1时命题也成立（k=1,2,3...）
看着答案我们得出公式：
AC,(n=1)
h(n,A,B,C){
h(n-1,A,C,B) + AC + h(n-1,B,A,C)
通过一堆高中数学的应用题经验，我们其实也可以推出上面这个答案，不过显然，数学没有学好。
好在可以轻易的转为代码，然后我们验证一下啊，果然似乎是对的。
h = (n, from, cache, to) =>
n === 1 ? `${from}${to}` :
h(n-1, from, to, cache) + ',' + `${from}${to},` +
h(n-1, cache, from, to)
通过汉诺塔问题，我们可以得出一些结论，在有些场景，巧妙的使用数学思想，是可以巧妙的解决一些似乎常规思想想象不到的问题，于是可以理解了为什么数学家那么少那么伟大，确实太烧脑了
现在我们尝试研究一下斐波那契数列
既然数学思想牛逼，那直接来递归搞起
// 数学思路：递归
f = n =>
n === 0 ? 0 :
n === 1 ? 1 :
f(n-1) + f(n-2)
看起来的确简单也好理解，但是当我用浏览器控制台尝试跑一下f(45)/f(46)/f(47),似乎感觉不太好了，因为实在是太慢了，你可以试试f(100),我反正是没有勇气的
那现在再来看看人类思路，循环
// 人类思路：循环
f = n => {
const array = [0,1]
for(let i=2; i<=n; i++){
array[i] = array[i-1] + array[i-2]
}
return array[n]
}
不必说，人类的白话形式本身在理解层面就有优势，那执行速度呢，f(45)/f(46)/f(47)直接都是秒出的，完全没感觉到计算时间
斐波那契问题也巧妙了解释了，不是数学思想就一定是最棒的思想，有些问题，数学家想的过于复杂，设计的过于巧妙，导致产生了更多的时间复杂度。而用人类思想，反而解的很轻松。
为什么递归的时间效率会这么慢呢，这是为什么呢？
栈
-
递归需要使用栈
前面说到递归是先递进再回归，所以他可以巧妙用到栈这个数据结构，压栈时，把当前函数所在的环境变量压入，待回归时，把对应的环境弹出来
-
栈有长度限制
栈其实是有长度限制的，如果溢出了，我们通常称之为stackoverflow，每个引擎每种语言，栈的大小都是不定的。正常代码中也是需要考虑到爆栈问题
-
压栈和弹栈
提供了pop和push API的list就可以称之为栈
回到刚才的问题，为什么递归计算汉诺塔就特别慢，我们就可以从栈的思维推敲一下，如何有效减小压栈？
-
不用递归，所有的递归都可以写成循环
就是转成人类思维，所有的数学思维都是可以转人类思维的，只是你想不想的来的问题
// 循环代替递归
// 递归
f = n =>
n === 1 ? 1 :
n * f(n-1)
// 循环
f = n => {
let result = 1
for(let i = 1; i <= n; i++){
result = result * i
}
return result
}
- 尾递归
尾递归的意思就是递归只出现在return语句且return语句里只有递归
//普通递归
f = n =>
n === 1 ? 1 :
n * f(n-1)
// 这里的4就是环境变量，每次压栈，导致弹栈的时候需要找到这个变量
f(4)
= 4 * f(3)
= 4 * (3 * f(2))
= 4 * (3 * (2 * f(1)))
= 4 * (3 * 2 * 1))
= 4 * (3 * 2)
= 4 * 6
= 24
// 尾递归，没有旧状态
f(4)
= f(1,4,1)
= f(2,4,2)
= f(3,4,6)
= f(4,4,24)
= 24
递归需要归，尾递归不需要归
尾递归 -> 迭代
在这里，为方便理解，我们简单的给尾递归一个新定义，迭代。当然迭代还分好几种，如循环迭代，尾递归迭代。目前只讨论尾递归。
顾名思义，迭代可以理解为一种自我进化，带着旧的状态进化成了一种新的状态，进化后，就不再保留旧状态。也不再需要所谓的“归”
尾递归压栈: 因为不同语言不同客户端表现不一致，所以要提一下
形如：function a() { return b() } 这样就是一种尾递归或者说是尾递归迭代，由a函数完全到了b函数
在b()算出结果后，不需要任何其他操作，直接去a改返回的地方，所以为什么其实可以干脆省掉中间的压栈，在某些语言中，的确是这样的
不过缺点也有，平时我们都关注函数调用栈，如果以为这种尾递归调用而丢失了调用历史，那么debug将是一种灾难
这里查了一些资料，不同语言不同客户端在优化上表现不一致，就JavaScript来说
- Chrome的v8没有实现尾调用优化
- safari却实现了
缓存
尾递归是优化递归的一个方法，另一个方法就是缓存了
在刚才例子中，相信大家都看出来了，为什么人类思想的计算时间那么快，并不是因为本身多先进，只是因为人类会自然而然的使用缓存来加速计算，而数学公式却不会
就斐波那契问题，我们试试f(6)的计算次数：
f(5)一次，f(4)两次，f(3)三次，f(2)五次，f(1)和f(0)共11次，左右相加11次，总共33次操作。而这仅仅只是f(6)，所以我们刚才试图运行f(45)，想象一下是多么的灾难
f = n =>
n === 0 ? 0 : n === 1 ? 1 : mf(n-1) + mf(n-2)
memorize = fn => {
cache = {}
return (first, ...args) => {
if(!(first in cache)){
cache[first] = fn(first, ...args)
}
return cache[first]
}
}
mf = memorize(f)
这次我们使用一个cache增强一下f函数，再试试你就会发现计算速度大大加快了，而且这个增强函数是无痛的，是不是就有点像平时我们用的缓存AOP原型了
但是，再往深层的想，你用了cache，那无非又回到了那个深奥的结论，时间换空间罢了~
总结
聊了这么多，人类思路或数学思路也好。其实写代码的时候，都是我们避不开的解法。作为人类，我们往往还是会使用直觉最优解。只是在这里，强行将两种解法抽象开了，并做了对比。一旦拨开云雾，就豁然开朗，感受着代码的魔力，感受着一切有因果。无非时间换空间，空间换时间罢了。
网友评论