迭代法
迭代法也被称为辗转法，是一种不断用变量的旧值递推新值的过程，在解决问题时总是重复利用一种方法。与迭代法相对应的是直接法(或者称为一次解法)，即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法，功能都比较类似。
在使用迭代算法解决问题时，需要做好如下3个方面的工作：
(1)确定迭代变量
在可以使用迭代算法解决的问题中，至少存在一个迭代变量，即直接或间接地不断由旧值递推出新值的变量。
(2)建立迭代关系式
迭代关系式是指如何从变量的前一个值推出其下一个值的公式或关系。通常可以使用递推或倒推的方法来建立迭代关系式，迭代关系式的建立是解决迭代问题的关键。
(3)对迭代过程进行控制
在编写迭代程序时，必须确定在什么时候结束迭代过程，不能让迭代过程无休止地重复执行下去。通常可分为如下两种情况来控制迭代过程：
所需的迭代次数是个确定的值，可以计算出来。可以构建一个固定次数的循环来实现对迭代过程的控制。
所需的迭代次数无法确定，需要进一步分析出用来结束迭代过程的条件。
迭代与递归的区别
从“编程之美”的角度看，可以借用一句非常经典的话：“迭代是人，递归是神！”来从宏观上对二者进行把握。
从概念上讲，递归就是指程序调用自身的编程思想，即一个函数调用本身；迭代是利用已知的变量值，根据递推公式不断演进得到变量新值得编程思想。
从直观上讲，递归是将大问题化为相同结构的小问题，从待求解的问题出发，一直分解到已经已知答案的最小问题为止，然后再逐级返回，从而得到大问题的解(一个非常形象的例子就是分类回归树 classification and regression tree，从root出发，先将root分解为另一个(root,sub-tree)，就这样一直分解，直到遇到leafs后逐层返回)；而迭代则是从已知值出发，通过递推式，不断更新变量新值，一直到能够解决要求的问题为止。
迭代与递归的转换
理论上递归和迭代可以相互转换，但实际从算法结构来说，递归声明的结构并不总能转换为迭代结构(原因有待研究)。迭代可以转换为递归，但递归不一定能转换为迭代。
递归转迭代
将递归算法转换为非递归算法有两种方法，一种是直接求值(迭代)，不需要回溯；另一种是不能直接求值，需要回溯。前者使用一些变量保存中间结果，称为直接转换法，后者使用栈保存中间结果，称为间接转换法。
直接转换法： 直接转换法通常用来消除尾递归(tail recursion)和单向递归，将递归结构用迭代结构来替代。(单向递归 → 尾递归 → 迭代)
间接转换法： 递归实际上利用了系统堆栈实现自身调用，我们通过使用栈保存中间结果模拟递归过程，将其转为非递归形式。
尾递归函数递归调用返回时正好是函数的结尾，因此递归调用时就不需要保留当前栈帧，可以直接将当前栈帧覆盖掉。
递归转迭代之尾递归.png
Go语言描述
还是以斐波那契数列为例吧：
递归方式：
// 递归生成斐波那契数
func Fibonacci(n uint) uint {
if n <= 2 {
return 1
}
return Fibonacci(n-1) + Fibonacci(n-2)
}
迭代方式：
// 获取斐波那契数列
func GetFibonacciArray(n int) []int {
fArr := make([]int, n+1, n+1) // 数列第一位从下标1开始
fArr[1] = 1
fArr[2] = 1
for i := 3; i <= n; i++ {
fArr[i] = fArr[i-1] + fArr[i-2]
}
return fArr[1:]
}
就以上斐波那契数列的生成为例，尽管递归看起来比较简单，但迭代方式确实比递归方式效率高。
Java 面试宝典是大明哥全力打造的 Java 精品面试题，它是一份靠谱、强大、详细、经典的 Java 后端面试宝典。它不仅仅只是一道道面试题，而是一套完整的 Java 知识体系，一套你 Java 知识点的扫盲贴。
它的内容包括：
- 大厂真题：Java 面试宝典里面的题目都是最近几年的高频的大厂面试真题。
- 原创内容：Java 面试宝典内容全部都是大明哥原创，内容全面且通俗易懂，回答部分可以直接作为面试回答内容。
- 持续更新：一次购买，永久有效。大明哥会持续更新 3+ 年，累计更新 1000+，宝典会不断迭代更新，保证最新、最全面。
- 覆盖全面：本宝典累计更新 1000+，从 Java 入门到 Java 架构的高频面试题，实现 360° 全覆盖。
- 不止面试：内容包含面试题解析、内容详解、知识扩展，它不仅仅只是一份面试题，更是一套完整的 Java 知识体系。
- 宝典详情：https://www.yuque.com/chenssy/sike-java/xvlo920axlp7sf4k
- 宝典总览：https://www.yuque.com/chenssy/sike-java/yogsehzntzgp4ly1
- 宝典进展：https://www.yuque.com/chenssy/sike-java/en9ned7loo47z5aw
目前 Java 面试宝典累计更新 400+ 道，总字数 42w+。大明哥还在持续更新中，下图是大明哥在 2024-12 月份的更新情况：
想了解详情的小伙伴，扫描下面二维码加大明哥微信【daming091】咨询
同时，大明哥也整理一套目前市面最常见的热点面试题。微信搜[大明哥聊 Java]或扫描下方二维码关注大明哥的原创公众号[大明哥聊 Java] ，回复【面试题】 即可免费领取。
