6. 递推关系引论¶
6.1. 递推关系¶
递归算法的运行时间最容易用一个递归表达式来表示，因为递归算法的总时间包含运行递归调用的时间。 递推关系 通过一个包含自身一个或多个（更小）实例的表达式来定义函数。 一个经典的例子是阶乘函数的递归定义：
\[n! = (n-1)! \cdot n\ \mbox{for}\ n>1; \quad 1! = 0! = 1.\]
递推的另一个标准例子是斐波那契数列：
\[\mbox{Fib}(n) = \mbox{Fib}(n-1) + \mbox{Fib}(n-2)\ \mbox{for}\ n>2; \quad\mbox{Fib}(1) = \mbox{Fib}(2) = 1.\]
根据这个定义，斐波那契数列的前七个数是
\[1, 1, 2, 3, 5, 8,\ \mbox{and}\ 13.\]
注意，这个定义包含两部分： \(\mbox{Fib}(n)\) 的一般定义，以及 \(\mbox{Fib}(1)\) 和 \(\mbox{Fib}(2)\) 的基本情况。 同样，阶乘的定义也包含一个递归部分和若干基本情况。
递推关系常用来为递归函数的代价建模。
例如，对于规模为 \(n\) 的输入，递归版阶乘函数所需的乘法次数在 \(n = 0\) 或 \(n = 1\) 时为零（即基本情况），否则等于在 \(n-1\) 的值上调用 fact 的代价加一。
这可以用下面的递推关系来定义：
\[\mathbf{T}(n) = \mathbf{T}(n-1) + 1\ \mbox{for}\ n>1;
\quad \mathbf{T}(0) = \mathbf{T}(1) = 0.\]
与求和一样，我们通常希望用一个闭式解来替换递推关系。 一种做法是展开递推式，把右端出现的每个 \(\mathbf{T}\) 都替换成它的定义。
一个稍复杂些的递推关系是
\[\mathbf{T}(n) = \mathbf{T}(n-1) + n; \quad \mathbf{T}(1) = 1.\]
同样，我们将借助展开来寻找闭式解。
