迭代法：用旧值递推新值，求解方程近似根与工程问题的算法设计指南（Learn-Algorithms 精讲）

• 教程

迭代法（Iteration）是一种不断用旧值递推新值的过程，是算法设计中与递归并列的基本思维方式。本文基于 Learn-Algorithms 仓库中 迭代法.md 的骨架，结合仓库内 8 Algorithms Analysis 系列笔记与 9 Algorithms Job Interview 面试题代码，系统梳理迭代法的定义与分类、三大构成要素（迭代变量、迭代关系、迭代过程控制）、与递归的关系对比，并以求方程近似根（牛顿迭代法、二分迭代）、幂运算、平方根判断、数组与链表遍历、排序、查找等真实代码案例展开实战讲解。读完本文，你将掌握迭代法的建模步骤与终止条件设计方法，能直接用 C/Java 代码实现典型的精确迭代与近似迭代算法。

一、什么是迭代法：定义与分类

迭代法是一种不断用旧值递推新值的过程，分精确迭代和近似迭代，是用来求方程和方程组近似根的方法。——迭代法.md

迭代法本质上是让一系列状态按照既定的规则逐步演化：每一轮循环中，利用当前状态（旧值）计算出下一轮的状态（新值），并将新值作为下一轮计算的输入，如此反复，直到满足终止条件。这个过程不需要函数自我调用，而是通过循环结构显式地推进状态。

1.1 精确迭代

精确迭代适用于能够通过有限次递推得到确定精确结果的问题，例如：

• 斐波那契数列的循环计算：fib(n) = fib(n-1) + fib(n-2)，用两个变量滚动推进；
• 幂运算的循环累乘：result *= base；
• 数组/链表的遍历、计数、求和；
• 排序算法中基于比较交换的多轮扫描（如冒泡、选择排序）；
• 二分查找中通过循环不断收缩查找区间。

这类迭代的次数通常是确定的（与问题规模相关），结果不依赖于收敛判断，一次运行即可得到最终答案。

1.2 近似迭代

近似迭代用于求方程和方程组的近似根，其特点是：迭代结果无法在有限步内得到精确值，只能通过不断逼近，在误差或变化量小于某个阈值时终止。典型代表是牛顿迭代法（Newton's Method）：

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

从一个初始猜测值出发，反复用切线近似逼近方程的根。仓库中 4.2 数值-指数.md 在"求根号2的值"一题中明确指出候选解法为泰勒级数与牛顿迭代法，正是近似迭代的典型场景。

近似迭代的核心特征是"收敛性"：只有迭代关系设计合理、初值选取恰当，序列 $x_1, x_2, \dots, x_n$ 才会收敛到目标根；否则迭代可能发散或震荡，永远无法终止。

二、迭代法的三要素：建模与设计

原文档明确指出，一个完整的迭代算法必须回答三个问题：

1. 迭代变量：确定哪些变量承载状态，每轮迭代后这些变量的值会被更新。
2. 迭代关系：即状态转移规则——从旧值推导新值的公式或逻辑。迭代关系选择不合理，会导致迭代失败（发散、死循环或结果错误）。
3. 迭代过程控制：确定迭代什么时候结束，不能无休止进行下去。

2.1 迭代变量

迭代变量是迭代过程的"记忆单元"。例如求斐波那契数列时，只需要保存前两个状态prev和curr（见下文案例）；二分查找中保存区间端点low与high；链表反转中保存三个指针prev / curr / next。变量的数量与含义直接决定迭代关系的表达能力。

2.2 迭代关系

迭代关系是算法的"发动机"，必须满足两条要求：

• 正确性：新值必须严格按数学或业务规则由旧值推导；
• 收敛性（近似迭代）：映射必须能引导状态向目标逼近，否则会出现发散或振荡。

以牛顿迭代法求 $\sqrt{2}$ 为例，构造 $f(x) = x^2 - 2$，迭代关系为：

$$x_{n+1} = \frac{x_n + \frac{2}{x_n}}{2}$$

该关系来自牛顿法的化简：$x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n} = \frac{x_n + 2/x_n}{2}$。若错误地写成 $x_{n+1} = x_n^2 - 2$，则初值 1 会得到 1 → -1 → -1 … 立即发散，这正是"迭代关系选择不合理导致迭代失败"的直观例证。

2.3 迭代过程控制：终止条件设计

迭代控制是防止"无休止进行下去"的关键，常见终止条件包括：

特别注意两个高频错误：

1. 死循环：终止条件永不为真（如比较方向写反、步进语句缺失）；
2. 过早终止/精度不足：阈值 $\epsilon$ 取得过大，导致近似根精度不够；过小则迭代次数过多。

三、迭代与递归的关系：自顶向下与自底向上

仓库中 递归.md 给出了精辟的总结：

自顶向下的递归，自底向上是迭代。

两者的本质联系在于：任何一个可以用递归描述的过程，都可以改写为迭代；反之亦然。区别在于：

递归的运行效率相对较低，因为有函数调用的开销，递归多次也可能造成栈溢出（递归.md）；迭代版本往往可以用 O(1) 空间完成同样计算。这也是为什么许多面试题（如斐波那契、链表反转）都要求先给出迭代解法。

斐波那契数列是理解二者差异的最佳案例：递归版fib(N) = fib(N-1) + fib(N-2)存在大量重复子问题（递归树中重叠子问题呈指数膨胀）；而迭代版只需两个变量滚动更新，时间复杂度 O(n)、空间复杂度 O(1)。

四、精确迭代实战：从数列到数组、链表

4.1 斐波那契数列：滚动变量的精确迭代

仓库 5 array/fibonacci.c 同时给出了递归与循环两种实现，并用clock()对fibonacci2(40)计时：

// 循环迭代版 int fibonacci2(int n){ int result[2] = {0,1}; if ( n<2 ) return result[n]; int fibOne=0; int fibTwo=1; int fibN; for (int i = 2; i < n; ++i){ fibN = fibOne + fibTwo; // 迭代关系：新值 = 旧值之和 fibOne = fibTwo; // 迭代变量更新 fibTwo = fibN; } return fibN; }

对照 递归.md 中给出的滚动迭代优化写法：

int fib(int n) { if (n < 1) return 0; if (n == 2 || n == 1) return 1; int prev = 1, curr = 1; for (int i = 3; i <= n; i++) { int sum = prev + curr; prev = curr; curr = sum; } return curr; }

要点拆解：

• 迭代变量：prev、curr（可推广到 K 阶递推时用环形数组保存最近 K 个值）；
• 迭代关系：fibN = fibOne + fibTwo；
• 过程控制：i < n的定长循环，无需收敛判断；
• 空间优化：原文档指出"当前状态只和之前的两个状态有关，并不需要那么长的一个 DP table 存储所有状态"，因此空间复杂度可降为 O(1)——这正是迭代自底向上思想的体现。

4.2 幂运算：快速幂的迭代化

4.2 数值-指数.md 讨论了double Power(double base, int exponent)，并指出朴素写法for循环连乘只考虑了exponent > 0的情况，未处理exponent <= 0与浮点判零。仓库 4 numer/Power.c 给出了快速幂的递归实现：

double Power(double base, int exponent){ if (exponent == 0) return 1; if (exponent == 1) return base; double result = Power(base, exponent >> 1); result *= result; if (exponent & 1) result = result*base; return result; }

该递归基于a^n = a^(n/2) * a^(n/2)（n 为偶数）、a^n = a^(n/2) * a^(n/2) * a（n 为奇数）。从"自底向上是迭代"的角度，完全可以改写成等价的二进制扫描迭代：按指数二进制位逐位平方累乘。这是精确迭代在数值计算中的典型应用。注意原文件注释也指出Power(2, -3)负数指数会出错——在工程化实现中需先处理exponent < 0的取倒数分支。

4.3 判断平方数：循环逼近的迭代

4 numer/isSquare.c 实现了一个"除数递增、商随除递减、二者相遇"的迭代判断：

int isSquare(unsigned integer){ if (integer==1 || integer==0) return integer; int divider=2,result=integer/divider; while(result>divider){ divider++; result = integer/divider; } if (result!=divider) return -1; return result; }

• 迭代变量：divider、result；
• 迭代关系：divider++且result = integer / divider（整数除法）；
• 过程控制：while(result > divider)，当商不再大于除数时停止。

4.2 数值-指数.md 同时给出了更高效的二分迭代方案：在[0, x]区间反复取中点平方与目标比较，把区间不断减半，最终落在 $\lfloor\sqrt{x}\rfloor$ 处，时间复杂度 O(log n)。原文用 25 演示了 (0+25)/2=12.5 → (0+12)/2=6 → (0+6)/2=3 → (3+6)/2=4.5 → (5+6)/2=5.5 的收缩轨迹。二分迭代比线性递增更快收敛，也印证了"迭代关系选择决定效率"。

4.4 数组遍历与查找：迭代的工程底色

• 二分查找：7 bianrytree/binary_search.c 中查找元素首次/末次出现位置，用low/high/mid三个迭代变量在while(low<high)中不断收缩区间——左边界用mid = (low+high)/2，右边界用mid = (low+high+1)/2防止死循环（经典的向上取整技巧）。
• 连续序列求和：5 array/print_continuous_sequence_sum.c 用small/big双指针滑动窗口迭代，迭代关系为sum -= small; small++（收缩）与big++; sum += big（扩张），控制条件small<big && big<=n/2+1，同时内层while(sum>n)负责收缩——这是"迭代过程控制"多层次的典型。
• 句子按单词翻转：1 string/revert_by_word.c 使用start/end双指针，while(*start != '\0')与while(start < end)双重循环完成"整句逆序 + 单词逆序"，指针每轮移动即为迭代变量更新。

4.5 链表与排序：三指针迭代与多轮扫描

• 链表反转：2 链表.md 明确指出"思路一：迭代，三个指针，遍历一遍，O(n) 复杂度"，即prev / curr / next三个迭代变量，每轮完成curr.next = prev后整体前移；递归版虽然简洁（head.next.next = head），但理解难度更高，且存在栈深度风险。
• 检测链表环：同文档的"快慢指针"迭代——p1每次前进一步、p2每次前进两步，若p2到达尾部则无环，否则p1 == p2时必然相遇。这是迭代过程控制依赖"相遇"这一终止条件的典型。
• 排序的多轮扫描：仓库 6 Sort 下的冒泡/选择/插入排序均为双层循环的精确迭代，8.c 演示了for (int i = 0; i < length; ++i) for (j = i+1; j < length; ++j)的经典双重扫描结构；插入排序每轮把新元素"插入"已排序前缀，迭代关系即"从后往前比较并后移"。

4.6 合并有序链表：迭代 vs 递归对照

递归.md 给出了合并两个有序链表的递归与非递归双版本。非递归版是典型的指针迭代：

public static LinkedNode mergeSeqLink(LinkedNode l1, LinkedNode l2){ if (l1 == null) return l2; if (l2 == null) return l1; LinkedNode result = new LinkedNode(0); LinkedNode tmp = result; while (l1 != null && l2 != null) { if (l1.value < l2.value) { tmp.next = l1; tmp = tmp.next; l1 = l1.next; } else { tmp.next = l2; l2 = l2.next; tmp = tmp.next; } } if (l1 != null) tmp.next = l1; if (l2 != null) tmp.next = l2; return result.next; }

• 迭代变量：tmp（结果链尾指针）、l1、l2（两条输入链的游标）；
• 迭代关系：每次取两链头部较小者接到结果链尾部；
• 过程控制：while (l1 != null && l2 != null)，循环结束后把剩余链整体拼接。

该案例与 5.3 数列-交并集.md 中"合并两个有序数列"的尾部扫描写法（while (index_a >= 0 && index_b >= 0)从后往前放置大值）互为印证：迭代的关键是选对扫描方向和指针推进规则。

五、近似迭代实战：牛顿迭代法与二分法求根

5.1 牛顿迭代法求平方根

4.2 数值-指数.md 在"求根号2的值并指定小数位"一题中，明确列出牛顿迭代法作为解法。求 $\sqrt{a}$ 等价于求 $f(x) = x^2 - a = 0$ 的正根，牛顿迭代公式化简为：

$$x_{n+1} = \frac{x_n + \frac{a}{x_n}}{2}$$

伪代码（可扩展为 C/Java 实现）：

double my_sqrt(double a, double eps){ if (a < 0) return -1; // 无实数根 double x = a; // 迭代变量：当前近似值 while (fabs(x * x - a) > eps) { // 过程控制：误差阈值终止 x = (x + a / x) / 2; // 迭代关系：牛顿切线逼近 } return x; }

• 迭代变量：x（当前近似根）；
• 迭代关系：$x_{n+1} = (x_n + a/x_n) / 2$，该关系保证二次收敛（每轮有效位数约翻倍）；
• 过程控制：fabs(x*x - a) > eps，以误差阈值为终止条件；若需要"指定小数位输出"，可把阈值设为0.5 * 10^-k（k 为目标小数位），再对结果做定点格式化。
• 收敛性提醒：初值不宜为 0（会出现除零）；迭代关系若写错（如x = x - (x*x - a)），序列可能震荡或发散，无法终止——这正是"迭代关系选择不合理会导致迭代失败"的直接体现。

5.2 二分法求根：区间收缩型近似迭代

对单调函数 $f(x)$ 在 $[l, r]$ 内求根，可用二分迭代：每次取中点 $mid=(l+r)/2$，根据 $f(mid)$ 与 0 的关系把区间减半，直到区间宽度小于eps。该过程与仓库 binary_search.c 的"查找首/末次出现位置"完全同构：迭代变量是区间端点low/high，迭代关系是"依据比较结果更新一侧端点"，过程控制是"区间收缩到指定程度"。二分法对迭代关系的鲁棒性要求比牛顿法低（不需要导数、不会因初值发散），但收敛速度（线性收敛）慢于牛顿法。

5.3 近似迭代的工程注意事项

1. 浮点判零：4.2 数值-指数.md 强调"判断浮点数是否等于 0，不能直接写base == 0，而应判断差的绝对值是否小于一个很小的范围"——近似迭代的终止条件同样必须用阈值而非精确相等。
2. 最大迭代次数兜底：工程中应同时设置"最大迭代轮数"（如 1000 轮）作为第二重过程控制，防止收敛失败时死循环。
3. 初值选择：牛顿迭代对初值敏感，越接近真根收敛越快；应结合问题领域给出合理初值。

六、迭代法的设计套路与常见误区

6.1 四步设计法

1. 抽象状态：找出承载问题状态的最小变量集合（迭代变量）；
2. 推导转移：从数学递推式或业务规则写出"旧值→新值"的映射（迭代关系）；
3. 设定终止：确定迭代轮数/误差阈值/边界条件三者之一作为过程控制；
4. 验证收敛：对近似迭代，用若干初值测试序列是否收敛、是否满足精度。

6.2 常见误区对照表

6.3 迭代法在仓库算法体系中的位置

8 Algorithms Analysis/README.md 把迭代法与递归、分治、动态规划、回溯、穷举、贪心并列，并总结："贪心法、分治法、动态规划都是将问题归纳为更小的、相似的子问题，通过求解子问题产生全局最优解。"迭代法正是这些"自顶向下"策略的自底向上执行引擎：

• 动态规划：动态规划.md 的"状态转移方程"即迭代关系的泛化，DP table 填表过程就是多维迭代；
• 分治/递归：递归的"回归"阶段可视为逆序迭代，如快速幂、归并排序的合并；
• 回溯法：回溯树的深度搜索常配合迭代式剪枝循环；
• 贪心法：多轮"局部最优选择"本身就是迭代的实例化。

因此在面试与工程中，"把递归改写成迭代"（如斐波那契、链表反转、二叉树遍历的显式栈迭代版）是考察算法基本功的高频题，其本质就是正确设计迭代变量与迭代关系。

七、总结

迭代法以"旧值递推新值"为核心，由迭代变量、迭代关系、迭代过程控制三要素构成完整算法：

1. 精确迭代面向结果确定的递推问题（斐波那契、幂运算、遍历、排序、查找），通常 O(1) 辅助空间即可完成；
2. 近似迭代面向方程与方程组求根（牛顿迭代法、二分法），核心是设计收敛的迭代关系并设置误差阈值与轮数上限；
3. 与递归互为表里——自顶向下递归、自底向上迭代，二者可互相转化；
4. 迭代关系选择不合理会导致迭代失败，终止条件设计不当会导致死循环，这两点是迭代法最容易出错的环节。

参考仓库中的源码路径可继续深入：迭代法.md、递归.md、README.md、4.2 数值-指数.md、5 array/fibonacci.c、4 numer/Power.c、4 numer/isSquare.c、7 bianrytree/binary_search.c、2 链表.md。

• 教程