——— ◆ ———
【真题算法·第十九期】迭代与递归
📖知识点详解
01什么是迭代与递归？
迭代（iteration） 是用循环反复执行同一段代码、逐步逼近结果，状态靠变量在每次循环里更新（如 for / while 累加到 n）。
递归（recursion） 是函数自己调用自己来求解：把大问题拆成结构相同、规模更小的子问题，直到触达一个可直接返回的"边界（基线）条件"。
核心区别一句话：迭代是"自己一遍遍做"，递归是"交给更小的自己去做"。两者往往可以互转（尾递归 ↔ 循环）。
02核心操作 / 代码模板
递归三要素（写递归前先想清楚）：
边界条件（base case）：什么时候直接返回，不再递归（否则无限递归栈溢出）。
递归关系（递推式）：本步结果如何用"更小的自己"表达。
返回与收敛：每次调用必须让参数朝边界靠近（规模变小）。
Python
# 递归标准模板
def rec(param):
if 满足边界条件: # ① 基线
return 边界值
# ② 递归关系：调用"更小的自己"
return 处理(param) + rec(更小的param)
Python
# 迭代标准模板（以求和为例）
result = 初值
for / while 未结束:
result = 更新(result, 当前项) # 状态在循环里推进
return result
03常见考查模式 / 变式
模式一：数值递推（尾递归 ↔ 循环） 如 f(a,s) 中每次 a+1、s-a，直到 a>=s。这类"每一步只依赖上一状态"的递归，改写成 while 循环最自然。
模式二：字符串 / 序列的递归拆解 如甲程序段 f(s,t) 取偶数位字符逆序拼接：递归 return f(s,t+2)+s[t] 把"取当前位 + 处理剩余"组合起来，等价于"步长 2 的循环 + 头插 / 尾插"。
模式三：递归转循环的正确性判定 考题常给"递归版"和"循环版"两个程序，要求它们输出相同。解法是手动展开递归的前几层，归纳出它实际在做什么，再匹配循环版的拼接顺序（顺 / 逆、头插 / 尾插）。
选考算法考查范围内，“迭代”无处不在，而“递归”仅考查是否理解执行过程。吴军在《计算之魂》一书中，写道：递归是计算思维的核心。虽然考查的形式不足以体现这一点，但是会做这些题，多少能为学生以后的学习打下一点基础。
04递归 vs 迭代
🧪真题举例
【2023年01月 · 第11题】
🔗 来源：[[202301-Q11-递归]]
11.定义如下函数：
Python
def rf(n):
if n < 3:
return n
return rf(n-1)+rf(n-3)
执行语句v = rf(5),函数rf被调用的次数是( )
A. 1
B. 5
C. 7
D. 15
📝解析
本题考查对递归程序的理解。由自定义函数可知，当参数n大于等于3时，继续两次递归调用（参数为n-1和n-3），反之结束递归直接返回值。题干执行的语句中参数值为5较小，故可以直接模拟并分析计算过程：①rf(5)=rf(4)+rf(2)，调用函数rf两次；②rf(4)=rf(3)+rf(1)，调用函数rf两次；③rf(3)=rf(2)+rf(0)，调用函数rf两次；再加上v=rf(5)本身调用的一次，得到答案7。故本题中rf被调用的次数是7次。
【2023年06月·第10题】
🔗 来源：[[202306-Q10-递归]]
定义如下函数：
Python
def f(a,s):
if a >= s:
return a
else:
return f(a+1,s-a)
执行语句k = f(6,21)后，k的值为
A. 6 B. 7 C. 8 D. 9
📝解析
本题考查递归算法及自定义函数。
由自定义函数f（a，s）可知：当参数a≥s时（即递归结束条件），返回值a,否则递归调用f（a+1，s-a）。执行语句k = f（6，21），第一次调用函数f（6，21）未达到递归结束条件，第二次调用函数f（7，15）未达到递归结束条件，第三次调用函数f（8，8），满足递归结束条件a≥s，返回值为a，得到答案8，故选C。
【2025年01月·第11题】
🔗 来源：[[202501-Q11-递归-字符串处理]]
11.对于任意非空字符串 s，甲、乙程序段输出结果相同，则乙程序段加框处的正确代码为
甲程序段：
Python
def f(s, t):
if t >= len(s) - 2:
return s[t]
return f(s, t+2) + s[t]
print(f(s, 0))
乙程序段：
Python
r = ""
n = len(s)
for i in range(0, n, 2):
# 加框处
print(r)
A. r = s[n-i] + r
B. r = r + s[n-i-1]
C. r = r + s[i]
D. r = s[i] + r
📝解析
本题考查递归和字符串处理知识。根据甲程序段代码可知，该程序段是典型的利用自定义函数实现的递归算法。若s的值依次为"ABCDEF"和"ABCDE"，分别调用函数f，返回值均为"ECA"，可见函数的功能是获取字符串s奇数位上的字符，并进行逆序连接。其调用过程如下：
假设非空s="ABCDEF"，f(s,0)→f(s,2)+s[0]→f(s,4)+s[2]+s[0]→s[4]+s[2]+s[0]→"ECA"；
假设非空s="ABCDE"，f(s,0)→f(s,2)+s[0]→f(s,4)+s[2]+s[0]→s[4]+s[2]+s[0]→"ECA"。
乙程序段代码则是采用循环递推的方式，索引从0开始遍历字符串，变量i的值依次为0，2，4…，且每次步进2（跳过一个字符），再拼接成结果字符串。
选项A错误： 当i为0时，s[n]越界。
选项B错误： 因索引必须是偶数且逆序拼接结果字符串，但是n奇偶性不确定。
选项C错误： 将每次获取奇数位上的字符并按原来顺序进行连接。
答案为：D
——— ◆ ———
💡解题要点
1先找边界条件：见到递归先圈出 if ... return，那就是递归何时停下；漏了它就会无限递归。
2盯紧参数的收敛：每次递归调用参数必须朝边界靠近（如 a+1、s-a、t+2）；不收敛必错。
3展开前几层归纳行为：手算 f(...) 的前 2~3 次调用，往往就能看出"取奇数位逆序"之类的真实功能。
4递归↔循环靠拼接顺序匹配：两程序输出相同，关键看循环版是"头插"（r = s[i] + r）还是"尾插"（r = r + s[i]），对应递归里 return f(...) + s[t] 还是 s[t] + f(...)。
如果这篇文章对你有帮助，欢迎 点赞、分享、推荐。
