程序员的数学I

递归——自己定义自己

GNU是什么的缩写？
“GNU is Not Unix”
这里面的GNU又是什么的缩写？
“GNU is Not Unix”

递归是一种奇妙的思考方法，它“使用自己来定义自己”。

汉诺塔

• 思考：有三根细圆柱(A,B,C)，A柱上套着6个圆盘。这些圆盘大小各异，按从大到小的顺序自下而上摆放，现在要把A柱上的6个圆盘全部移动到B上，并且在移动的时候遵守下述规则：
  1. 一次只能移动柱子最上端的一个圆盘
  2. 小圆盘上不能放大圆盘

将1个圆盘从一根柱子移动到另一根柱子，算移动1次，那么将6个圆盘全部从A移动到B最少需要移动几次呢？

汉诺塔

解题思路：

1. 先尝试解决3个圆盘的问题，需要7次
2. 仔细思考，无论如何，想移走k层的圆盘，都必须把k-1层的圆盘全部移走
3. 因为ABC三个柱子在不同的场景下会发挥不同的职能，我们假设x,y,z三个柱子，x为起点，y为目标，z为中转
4. 解出n层塔的步骤，即是利用z将n个圆盘从x移动到y
5. 当n=0时，不用做任何动作
6. 当n>0时，

• 首先，将n-1个圆盘从x，经由y中转，移动到z(解出n-1层)
• 然后，将1个圆盘从x移动到y
• 最后，将n-1个圆盘从z柱，经过x中转，移动到y(解出n-1层)

7. 从以上步骤得出结论，为了解出n层的汉诺塔，我们要使用n-1层的解法，我们将解出“n层汉诺塔”所需的最少移动步骤表示为：
   H(n)，例如，移动0个圆盘的次数为0，那么：
   H(0)=0，H(1)=1
   H(n)=H(n-1)+1+H(n-1)
   n的解法数=n-1的解法数+移动最大的圆盘的次数+n-1的解法数

• 我们将这种H(n)和H(n-1)的关系式称为递推公式(recursion relation, recurrence)

H(0)=0
H(1)=0+1+0=1
H(2)=1+1+1=3
H(3)=3+1+3=7
H(4)=7+1+7=15
H(5)=15+1+15=31
H(6)=31+1+31=63
H(n)=2^n-1推导式可以被数学归纳法证明

编程部分(略)

• 关键步骤
  1. 找出递归结构
  2. 建立地推公式

再谈阶乘

• n! = n x (n-1)! ←发现递归结构
• 0!=1的原因，就是为了完成递归定义
• 阶乘的递归定义和数学归纳法比较类似，n=0时相当于数学归纳法的步骤1(基底)，n>=1时相当于步骤2(归纳)。若用多米诺骨牌来打比方，“正确地定义0!”就相当于“确保推倒第1张多米诺骨牌”。

递归和归纳

• 递归和归纳本子上是相同的，都是将复杂问题简化。
• 递归和归纳，只是方向上不同。“从一般性前提推出个别性结论”是递归，“从个别性前提推出一般性结论”是归纳。