《计算之魂》 - 2 递归思维

本章总结：

计算机思维是自顶向下的，称作”递归”，而人的原始思维是自底向上的，称作”递推”。这就是为什么计算机思维难以被人们理解的原因之一。计算机设计出来就是用于计算大规模数据的，而人脑不是，这就是两种逻辑的本质差别。

2.1 递归是计算的核心

递归是计算思维的核心，其成立有两个条件：

1. 每一个步骤在形式上都是相同的
2. 必须有结束条件，否则就陷入了死循环（堆栈溢出）

上台阶问题

以1为起点，加到20，每次可以增加1或者2，共有多少种不同的增加方法？

解法：从F(20)开始算：

• F(20) = F(19)+F(18)
• F(19)=F(18)+F(17)
• 以此类推
• 终止条件：F(1)=1，F(2)=2

最终可以得到一个斐波那契数，求得F(20)的值。

汉诺塔与九连环问题

汉诺塔问题是典型的递归问题，通过将每一步骤拆解为次级步骤转换的中间步骤来递归解决。

汉诺塔的单层三个步骤：

1. Hanoi(i-1, A,T,B)：将A柱上的i-1个盘子移到B，以T为临时柱
2. 将A柱最后一个盘子放到B上
3. Hanoi(i-1, T,B,A)：将剩下i-1个盘子移到B，A作为临时柱

汉诺塔操作步骤数为：$S(n)=2^n-1$，可等效为二叉树的深度优先搜索算法。

汉诺塔的传说
来自越南河内寺院，僧侣需移动64个盘子。若每秒一步，需5800亿年（1800亿亿步）完成，届时世界末日将至。

2.2 遍历与树结构

树是递归的：

• 递归结束条件：节点本身就是树
• 根节点下是子树，子树下仍是子树（递归关系）

树的重要特征：

• 单一父节点：每一个节点仅有一个唯一父节点
• 连通性：每一棵树的内部节点之间，都是相连的
• 无环结构

二叉树是特殊的有序树：

• 严格定义：
  1. 空节点是二叉树
  2. 二叉树有根结点和左右子树（子树也是二叉树）
• 等价性：二叉树和任何树结构都是等价的

二叉树的遍历：

1. 深度优先搜索（FILO，对应栈）
   • 规则：从上到下；先左后右；尽头回溯
   • 中序遍历算法示例：

DepthFirstTraverseTree(BinaryTree tree) {
	if(tree = NIL) return;
    DepthFirstTraverseTree(tree.left_subtree); // 遍历左子树
    PrintNode(); // 打印当前节点
    DepthFirstTraverseTree(tree.right_subtree); // 遍历右子树
}

2. 广度优先搜索（FIFO，对应队列）
   • 规则：分层扫描；每层从左到右

思考题：回旋二叉树的解法需注意：

• 每层用堆栈作为数据结构
• 偶数层从左往右，奇数层从右往左入栈

附录：任意树转二叉树的方法：

1. 子树中的第一棵变为左子树
2. 右边的兄弟子树变为右子树

2.4 自然语言处理与嵌套

计算机语言采用嵌套思维（面向对象的基础），而人类思维更接近线性（面向过程）。

自然语言处理中，语法树的建立就是嵌套过程，通过递归思想逐层拆分句子。

复杂度分析：

• 上下文无关法：$O(N^3)$
• 上下文相关：$O(N^6)$（NP-hard问题）P-NP问题

注：上下文无关法等价于马尔可夫链和条件随机场的机器学习方法。

附录一，斐波那契数的数学推导

代数推导法：

1. 设$F_n=p{F}_{n-1}$
2. 构造线性组合$F_n+q{F}_{n-1}$
3. 通过方程组$p-q=1,pq=1$解得：$p=\frac{1+\sqrt{5}}{2}$

母函数推导法：

1. 定义生成函数：$G(x)={\sum }_{n=0}^{\infty }{F}_n{x}^n$
2. 推导得：$G(x)=\frac{x}{1-x-x^2}$
3. 展开后可得通项公式： $G(x)={\sum }_{n=0}^{\infty }\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2}{)}^n-(\frac{1-\sqrt{5}}{2}{)}^n]x^n$ 然后可得通项公式

思考题：

1. 二叉树的最大深度
2. 二叉排序树的第二大元素