迭代法的步骤：
- 迭代用递推方程的右部替换左部
- 出现初始值时，迭代停止
- 用数学归纳法验证解的正确性
例如，Hanoi塔问题是一个可以递归求解的经典问题。我们便可以用迭代法求解其时间复杂度的递推方程。首先看一下Hanoi塔问题的算法伪码：
算法1 Hanoi(A, C, n) //将A柱上n个盘子按照要求移到C柱上
1. if n=1 then move (A, C) //将A柱上1个盘子移到C柱上
2. else Hanoi(A, B, n-1)
3. move (A, C)
4. Hanoi(B, C, n-1)
设移动n个盘子的所需要的移动次数为T(n)，由算法的伪码得到递推方程T(n) = 2 * T(n-1) + 1 = 2 * [T(n-2) + 1] + 1 = ... = 2n-1 * T(1) + 2n-2 + ... + 2 + 1，其中T(1) = 1。于是得到T(n) = 2n - 1。再用数学归纳法带入验证结果：T(n) = 2 * T(n - 1) + 1 = 2 * (2n - 1 - 1) + 1 = 2n - 1。
随着n的增大，算法的时间复杂度呈指数级别增长，解Hanoi问题需要的时间之漫长将令人难以接受。事实上，Hanoi塔问题属于NP-Hard问题，即不存在多项式级别时间复杂度的解法，是不可解的。
有时，当直接只用迭代法解递归方程比较复杂时，可以采用换元迭代的方法，其执行步骤总结如下：
- 将对n的递推式换成对其它变元k的递推式
- 对k直接迭代
- 将解（关于k的函数）转换成关于n的函数
例如，考虑归并排序的时间复杂度。设待排序数组A的长度为n。首先看一下伪码：
算法2 MergeSort(A, p, r)
输入: 数组A[p...r], 1 ≤ p ≤ r ≤ n
输出: 从A[p]到A[r]按照递增顺序排好的数组A
1. if p < r
2. then q←floor((p+r)/2)
3. MergeSort(A, p, q)
4. MergeSort(A, q+1, r)
5. Merge(A, p, q, r)
设W(n)为对长度为n的数组排序需要的比较次数。由伪码得到时间复杂度的递推表达式W(n) = 2 * W(n / 2) + n - 1, W(1) = 0。
直接迭代求解比较困难，可以令n = 2k，则k = log2n。带入递推关系式后，用迭代法解得W(2k) = (k - 1) * 2k + 1。再将k = log2n代入就可以得到W(n) = nlog2n - n + 1。
需要指出的是，迭代方法一般适用于一阶的递推方程。对于二阶以上的情况，直接迭代将导致求和公式变得过于复杂，因此需要运用差消法，先化简方程再进行迭代。适用差消法的例子将在后续博文中介绍。