迭代与递归¶
在算法中，重复执行某个任务在实现某些功能时是非常常见的，通常可通过迭代或递归两种方式来实现这些重复的任务。
迭代¶
迭代（iteration）是一种重复执行某个特定任务的控制结构。
在迭代中，程序会在满足一定条件时重复执行某段代码以更新某种状态（这个状态本质上是一个或一系列变量的值或者某个/些可迭代对象的状态），直至该条件不再满足。
可迭代对象
可迭代对象（Iteratable Object）是能够一次返回其中一个成员的对象，通常使用 for 循环来完成此操作，如字符串、列表、元组、集合、字典等等之类的对象都属于可迭代对象。简单来理解，任何可以循环遍历的对象都是可迭代对象。
可迭代对象的应用几乎遍布所有高级编程语言，尤其是现代编程语言。可参考以下资料理解其概念与应用：
迭代重复操作的本质使得循环控制结构成为实现其最合适的方式与形式。
for循环¶
for循环是最常见的迭代形式，可迭代对象的遍历通常就可通过for循环完成。
Tip
for循环适合 在预先知道迭代次数 的程序中使用。
以下面的求和程序为例：
def sum(n: int) -> int:
"""Sum from 1 to n"""
res = 0
# iteration with for loop
for i in range(1, n + 1):
res += i
return res
可视化运行
对于该程序而言，迭代的应用在于不断更新res的过程，以下是描述该过程的算法流程图：
while循环¶
while循环与for循环的一个主要区别就是前者无法用于直接操作可迭代对象，但它仍然可以用于实现迭代。
还是以前面的求和函数为例，使用while循环实现则有：
def sum(n: int) -> int:
"""Sum from 1 to n"""
res = 0
i = 1
while i <= n:
res += i
i += 1
return res
可视化运行
虽然在使用while循环操作可迭代对象需要更加复杂的代码，但麻烦的同时也赋予了while循环更高的自由度，使得其能够实现一些逻辑更加复杂的迭代。例如需要同时对两个变量进行迭代：
def sum_with_product(n: int) -> int:
"""renew i twice once loop"""
res = 0
i = 1
while i <= n:
res += i
i += 1
i *= 2
return res
可视化运行
嵌套循环¶
在一些复杂场景中，可在一个循环结构中嵌套另一个循环结构来满足特定的迭代需求。最简单且经典的例子莫过于输出一个乘法口诀表：
def multiplication_table() -> None:
for i in range(1, 10):
for j in range(1, i+1):
print(f"{i} * {j} = {i*j}", end='\t')
print('\n')
可视化运行
算法流程图：
Warning
在使用循环嵌套时，每增加一层嵌套就会使得迭代操作的数量“提升一个维度”，同时减低代码的可读性，因此应尽量避免使用过深的嵌套。
递归¶
递归（recursion）是一种算法策略，通常通过函数间接或直接调用自身来实现。
顾名思义，递归的过程可分为两个部分：
- 递：在触发终止条件前，通过不断深入调用自身逻辑简化传入参数。
- 归：在触发终止条件后，程序从最深层的调用栈逐层释放内存空间并执行返回操作返回。
如果缺乏编程经验与计算机底层理论的知识积累，可能难以理解上面的描述。还是以在学习迭代过程中的求和算法为例，这次我们采用递归形式实现：
def sum_with_recur(n: int) -> int:
"""Sum from 1 to n with recursive."""
if n == 1:
return 1
return n + sum_with_recur(n - 1)
可视化运行
像上面这样，函数在每次递归中只调用自身一次，使得整个递归调用链呈线性结构的递归形式，我们称之线性递归（Linear Recursion），是最容易理解的递归形式。
可参考下图理解线性递归求和的过程：
除了线性递归，还有如下常见的递归形式：
尾递归¶
尾递归（Tail Recursion）是指递归调用是函数的最后一步操作，且递归调用的结果直接作为函数的返回值，没有额外的计算的递归形式。
尾递归可以被编译器优化为迭代形式（尾递归优化, TRO/TCO），从而减少栈空间的使用，避免栈溢出1。
还是以求和函数为例，下面是它的尾递归版本：
def tail_recur(n: int, res: int) -> int:
"""Sum from 0 to n and add with res with tail recursion"""
if n == 0:
return res
return tail_recur(n - 1, res + n)
可视化运行
在上面的例子中，尾递归与线性递归的区别在于二者的求和执行点有所不同：
- 线性递归的加法操作在触发终止条件后，即在“归”的过程中逐步执行。
- 尾递归的加法操作则在触发终止条件前，即在“递”的过程中逐步执行。
可参考下图理解尾递归求和的过程：
互递归¶
互递归（Mutual Recursion）是指两个或多个函数通过相互调用形成递归循环。例如，函数 A 调用函数 B，函数 B 又调用函数 A。
互递归常用于处理复杂的逻辑关系或状态转换，逻辑上类似于尾递归，但涉及多个函数。
以一个判断整数奇偶性的程序为例，在定义整数奇偶性时，考虑以下思路： - 如果一个整数比偶数大 \(1\)，那么它就是奇数 - 同理，如果一个整数比奇数大 \(1\)，那么它就是偶数 - \(0\) 是偶数
显然，前两个陈述可以形成一个判断的调用循环；而第三个陈述就可以作为一个基准条件（递归终止条件）。根据这个思路，我们就可以有以下实现：
def is_even(n: int) -> bool:
"""Judge whether an integer is an even by Mutual Recursion."""
if n == 0:
return True
return is_odd(n - 1)
def is_odd(n: int) -> bool:
"""Judge whether an integer is an odd by Mutual Recursion."""
if n == 0:
return False
return is_even(n - 1)
可视化运行
也可以将两个函数合并为一个：
def is_even(n: int) -> bool:
if n == 0:
return True
else:
if (n - 1) == 0:
return False
else:
return is_even((n - 1) - 1)
可视化运行
Review
回顾前文所介绍的，这个合并版本就相当于将这个程序的递归形式由互递归转化为了尾递归。之所以将其认定为尾递归，是因为其执行判断操作的时机在触发递归终止条件前。
树递归¶
树递归（Tree Recursion）是指一个函数在递归过程中调用自身多次（通常两次或更多），形如树状的分支结构。每次递归产生多个子问题，形似树的分叉。
最经典的树递归案例莫过于斐波那契数列：
def fibonaci(n: int) -> int:
"""Fibonaci with recursion"""
if n == 1:
return 0
if n == 2:
return 1
return fibonaci(n - 2) + fibonaci(n - 1)
可视化运行
可结合下图理解调用过程：
由于树递归的调用栈呈现出一种形似树枝的分叉结构，故其天然地适合用于解决分治问题，例如在数据结构中，树递归在构建递归对象时就十分常见。
递归调用栈¶
函数的调用在内存中需要划分一定的栈帧空间，在函数调用结束并返回后这些空间会被系统释放。递归调用在系统层面的本质就是函数在调用过程中持续在调用栈帧上为“新”的函数调用分配内存空间。
以前面的线性递归求和程序为例，我们可以通过显式调用语言封装好的栈（或者自己手搓一个）来将递归问题转化为一个实际的迭代问题：
def sum_in_stack(n: int) -> int:
stack = []
res = 0
# 递
for i in range(n, 0, -1):
# 反向 range，以实现堆栈的 FILO 特性
stack.append(i) # 入栈
# 归
while stack:
# 出栈
res += stack.pop()
return res