python学习笔记（12）算法（5）迭代与递归

一、迭代

迭代（iteration）是一种重复执行某个任务的控制结构。在迭代中，程序会在满足一定的条件下重复执行某段代码，直到这个条件不再满足。

迭代通常用于解决需要逐步推进的计算问题，例如遍历数组、计算阶乘等。迭代的优点是内存使用效率高，易于优化，适合处理大规模数据。

1.for 循环

以下函数基于 for 循环实现了求和 1 + 2 + ⋯ + 100，求和结果使用变量 res 记录。需要注意的是，Python中 range(a, b) 对应的区间是“左闭右开”的，对应的遍历范围为 𝑎, 𝑎 + 1, … , b − 1 ：

ret=0
for i in range(1,101):ret=ret+i
print(ret)

2.while 循环

与 for 循环类似，while 循环也是一种实现迭代的方法。在 while 循环中，程序每轮都会先检查条件，如果条
件为真，则继续执行，否则就结束循环。
下面我们用 while 循环来实现求和 1 + 2 + ⋯ + 100 ：

res = 0
i = 1while i <=100:res += ii += 1
print(res)

while 循环比 for 循环的自由度更高。在 while 循环中，我们可以自由地设计条件变量的初始化和更新步骤。for 循环的代码更加紧凑，while 循环更加灵活，两者都可以实现迭代结构。选择使用哪一个应该根据特定问题的需求来决定。

二、递归

递归（recursion）是一种算法策略，通过函数调用自身来解决问题。它主要包含两个阶段。
1. 递：程序不断深入地调用自身，通常传入更小或更简化的参数，直到达到“终止条件”。
2. 归：触发“终止条件”后，程序从最深层的递归函数开始逐层返回，汇聚每一层的结果。
而从实现的角度看，递归代码主要包含三个要素。
1. 终止条件：用于决定什么时候由“递”转“归”。
2. 递归调用：对应“递”，函数调用自身，通常输入更小或更简化的参数。
3. 返回结果：对应“归”，将当前递归层级的结果返回至上一层。

递归是指在函数或方法中调用自身，以分解问题为更小的子问题，直至达到某个基准条件为止。递归通常用于解决具有自相似性质的问题，如树的遍历、斐波那契数列等。递归的优点是代码简洁，自然表达，适合处理自相似问题。
观察以下代码，我们只需调用函数 recur(n) ，就可以完成 1 + 2 + ⋯ + 100的计算：

def recur(n=100):if n == 1:return 1res = recur(n - 1)return n + resprint(recur())

虽然从计算角度看，迭代与递归可以得到相同的结果，但它们代表了两种完全不同的思考和解决问题的范
式。
‧ 迭代：“自下而上”地解决问题。从最基础的步骤开始，然后不断重复或累加这些步骤，直到任务完成。
‧ 递归：“自上而下”地解决问题。将原问题分解为更小的子问题，这些子问题和原问题具有相同的形式。
接下来将子问题继续分解为更小的子问题，直到基本情况时停止（基本情况的解是已知的）。
以上述求和函数为例，设问题 𝑎(𝑖) = 1 + 2 + ⋯ + 𝑖。
‧ 迭代：在循环中模拟求和过程，从 1 遍历到 𝑖，每轮执行求和操作，即可求得 𝑎(𝑖) 。
‧ 递归：将问题分解