企业官网建设流程全解析

Day 5，函数的递归和迭代，几乎每个学编程的人都会在这里卡一次。我自己当年也是这样：迭代老老实实写循环，一点问题没有；一碰到递归，看代码能看懂，真让自己写就懵，总觉得"这句话调自己本身"像套娃，怎么看怎么像一个死循环。后来才明白，递归和迭代不是在竞争"谁更好"，而是在用两种完全不同的方式对付同一个核心问题——怎么在有限的计算步骤里，处理一个原本规模不确定的任务。这篇就当是第五天的学习笔记，我把递归的调用栈真相、迭代的状态推进逻辑、两者的实战对比和常见踩坑都摊开讲一遍。适合刚开始学函数的初学者，也适合工作中遇到"递归改迭代"需求、或者准备算法面试的人。

1. 先搞清楚递归和迭代到底在解决什么问题

1.1 "循环能做的，递归都能做"这句话为什么只说对了一半

很多教程开篇会说"所有递归都能改写成迭代，迭代也都能替换成递归"。这个结论在计算机理论层面是对的，毕竟递归本质上依赖的调用栈，本身就可以用显式的栈数据结构模拟出来。但如果你真的在代码里把所有循环都换成递归，或者把所有递归都硬掰成循环，很快就会发现事情没那么简单。

举个例子，让你求一个数组的最大值。用迭代写：

def find_max_iter(nums): current_max = nums[0] for num in nums[1:]: if num > current_max: current_max = num return current_max

用递归写，可以这样：

def find_max_rec(nums): if len(nums) == 1: return nums[0] rest_max = find_max_rec(nums[1:]) return nums[0] if nums[0] > rest_max else rest_max

两个都能跑，结果也一样，但你能明显感觉到：迭代那个版本脑子里有清晰的"进度条"，变量current_max一路在更新；递归那个版本，你得先相信"对nums[1:]调用find_max_rec一定会返回子数组的最大值"，才能把整个问题想通。这就是所谓"递归信仰"——你得暂时放下"它到底怎么一步一步算出来的"这个执念，先假设更小规模的问题已经被正确解决了。

1.2 递归是"拆"，迭代是"推"

我后来琢磨出一个比较顺手的理解方式：递归的核心动作是"拆解"，把一个大的未知问题，拆成一个更小的同类问题再加一点当前层的处理；迭代的核心动作是"推进"，用一个或几个变量记住当前进度，每轮循环把这个进度向前挪一格，直到挪完。

拿爬楼梯来类比。递归的思路是：我想知道爬到第 10 级有多少种方式，那就先想"到第 9 级的方式加上最后跨一步，以及到第 8 级的方式加上最后跨两步"，于是问题被拆成了f(10) = f(9) + f(8)。迭代的思路则是：我先站在第 1 级，数一下有 1 种方式，再到第 2 级，有 2 种，再到第 3 级，把前两级加起来……一路顺着台阶往上推，手里始终只握着"前两级的答案"。

这两种思维没有优劣，但注意：在递归的"拆"里面，你需要额外维护一个看不见的东西——调用栈；在迭代的"推"里面，你需要自己动手维护那个"进度变量"。前者信任运行时，后者信任自己。

1.3 为什么大家普遍觉得递归更难

我觉得卡住的人，大部分不是卡在"不会写递归"，而是卡在"没法接受递归能正常结束"。第一次看到factorial(n) 里调 factorial(n-1)，直觉反应是：这不该无限循环吗？它什么时候停下来？

这个问题的答案只有一句话：当它遇到终止条件的时候。但这句话需要和"每一层调用都会创建独立的作用域"配合理解。递归不是你站在原地给自己打电话然后陷入死循环，而是每一次调用都开了一个新的执行环境，参数不同、局部变量不同，等最深处那个调用返回结果后，再一层一层带回给上层。想通了这一层，递归的门槛就跨过去一半了。

2. 递归解剖：终止条件、递推关系、调用栈的真相

2.1 递归三要素，缺一个都不是递归

写一个正确的递归函数，理论上只需要三样东西：

1. 终止条件（base case）：当输入规模小到可以直接给出答案时，直接返回，不再继续调用自己。
2. 递推关系（recurrence relation）：把当前规模的问题，转化为一个或多个更小规模同类问题的组合。
3. 规模递减小：每次递归调用，参数必须朝着终止条件的方向逼近，否则程序永远停不下来。

表面上这是三条，实际调试中你会遇到的情况是：三样东西都写了，但写歪了。比如终止条件写成了if n == 0，可你的递推关系是f(n) = n + f(n-1)，当n是负数时就永远到不了 0；又比如递推关系里写的是f(n) = f(n+1)，参数反而越来越大了。这些都是我用 DEBUG 一步步跟进才看出来的，代码看着"有终止条件"，其实是一颗隐形炸弹。

2.2 调用栈：每一层递归到底在内存里发生了什么

理解了三要素，还要理解一个东西：调用栈。我当年真正觉得"通了"，不是靠看教科书上的定义，而是靠亲手一行一行模拟调用过程。

拿最经典的阶乘来说：

def factorial(n): if n <= 1: return 1 return n * factorial(n - 1)

当你在主程序里调用factorial(4)时，内存里发生了这些事情：

1. 创建一帧属于factorial(4)的调用记录，里面存着当前参数n=4，以及还没算完的表达式4 * factorial(3)，于是它先暂停，去调用factorial(3)。
2. 又在栈上叠了factorial(3)的帧，存着n=3和3 * factorial(2)，再次暂停。
3. 叠上factorial(2)的帧，暂停在2 * factorial(1)。
4. 叠上factorial(1)的帧，这次n <= 1成立，直接返回 1。于是factorial(2)的帧被唤醒，算出2 * 1 = 2，返回。
5. factorial(3)的帧被唤醒，算出3 * 2 = 6，返回。
6. factorial(4)的帧被唤醒，算出4 * 6 = 24，返回给主程序。

这个过程就像叠盘子：调用一次叠一个，返回一次取一个。后调用的先返回，先调用的后返回——这就是"栈"这个数据结构名字的来源。在代码里，你只写了三行递归逻辑，但运行时帮你完成了上面一整串的"托盘传递"。这也是为什么递归代码往往很短，却不代表它做的事很少。

2.3 线性递归与树形递归：斐波那契为什么这么慢

同样是递归，结构不同，代价完全不同。阶乘这种每个递归只调用自己一次的，叫线性递归，调用栈深度大约等于问题规模，空间复杂度 O(n)。但斐波那契这种，一个递归调两次自己，就会长出指数级别的调用树：

def fib_rec(n): if n <= 1: return n return fib_rec(n - 1) + fib_rec(n - 2)

调用fib_rec(5)会这样展开：先算fib_rec(4)和fib_rec(3)；fib_rec(4)又去算fib_rec(3)和fib_rec(2)。注意，fib_rec(3)被算了两次，而往下fib_rec(2)还要被重复更多次。这个重复计算量随n呈现指数级增长，跑到n=35左右普通机器就会明显卡顿。

这不是递归本身的错，而是"没有记忆的递归"在重复劳动。解决思路是加缓存，也就是记忆化，这个我后面专门再说。但你现在先记住：写递归之前，看一眼递推关系会不会把同一个子问题重复计算好几遍，会的话，要么加缓存，要么换迭代。

3. 迭代的工程实现：循环与状态变量的配合

3.1 迭代的本质，是把"未来要用的信息"放进变量里

迭代看起来比递归简单，但真要写得稳，也没那么简单。它的核心只有一句话：每轮循环结束之后，你的状态变量必须准确描述"当前已经推进到了哪里、还差什么"。

拿累加来举例，迭代写出来是：

def sum_list(numbers): total = 0 for num in numbers: total += num return total

这里的total就是状态变量。每处理一个元素，total就更新一次，循环结束后，total恰好等于所有元素之和。关键在于：你必须在每一轮循环开始时，都保证total的含义是"前几个元素的和"，否则最后结果一定错。

这个"每一轮都保持成立的性质"，专业说法叫循环不变量。听着玄乎，实际就是调试时的锚点：如果你的while循环跑飞了，第一件事就是检查——进入循环之前，状态变量有没有初始化对；每轮结束前，状态变量有没有按照同一种规则更新。

3.2 三个最常用的迭代套路

我日常写代码，用的最多的迭代形态其实是这三种。

第一种是"累加器模式"，像上面的total，适合求和、求积、统计数量。关键点是初始值要选对：求和初始 0，求积初始 1，求最大值初始要设成极小值或者取首元素。

第二种是"双指针/双变量滚动模式"，适合斐波那契、滚动窗口这类需要保留历史两三个值的问题：

def fib_iter(n): if n <= 1: return n a, b = 0, 1 for _ in range(2, n + 1): a, b = b, a + b return b

这里a和b始终保存"前一个斐波那契数"和"当前斐波那契数"。每轮更新时，新的a等于旧b，新的b等于旧a + 旧 b。一轮循环就相当于把窗口往前滚一格，不需要数组，也不需要记住中间所有结果。

第三种是"显式栈模式"，专门用于把递归逻辑改写成迭代。比如后面要讲的遍历目录，递归天然好写，但如果担心递归深度，就用一个列表模拟调用栈。

3.3 迭代的边界控制，是新手最容易翻车的地方

写循环翻车，十有八九栽在边界条件上。range(1, n)和range(1, n + 1)差一个数，结果就可能完全不对。我自己的习惯是，写完循环先不要急着跑大数据，先拿最小的输入过一遍：

• n = 0会发生什么？
• n = 1会发生什么？
• 数组只有一个元素会怎样？
• 数组为空又会怎样？

这四个"小边界"过掉了，循环才有基本可信度。还有一类错误很隐蔽：while循环里条件判断用的状态变量，在循环体内被更新，但更新语句放错了位置，导致多算一轮或者少算一轮。遇到这种情况，我会直接在纸上手写前几轮的状态变化表，一行一行对，比闷头调试快得多。

4. 同一道题，两种解法：三组实战对比

4.1 第一组：阶乘，递归的代码短，迭代的逻辑长

阶乘是两者差异最直观的题目。递归版三段话能写完：

def factorial_rec(n): if n <= 1: return 1 return n * factorial_rec(n - 1)

迭代版也不复杂：

def factorial_iter(n): result = 1 for i in range(2, n + 1): result *= i return result

注意一个小差异：递归版的递推关系是fact(n) = n * fact(n-1)，它从n往1方向拆；迭代版则是从2往n方向乘，变量result一路累乘。方向相反，结果一致。这个"方向相反"正是很多人觉得递归"别扭"的根源：我们平时习惯从前往后推，递归却要求你先假设后面的结果已知，再倒推回来。

4.2 第二组：斐波那契，性能差距可以大到指数级

这组对比最有说服力。朴素的递归版前面写过，问题在于重复计算；迭代版是滚动变量，每一轮只做一次加法，时间复杂度 O(n)、空间 O(1)。我拿n=40分别跑了一下（普通的个人电脑），递归版肉眼可见地停顿，迭代版瞬间返回。

如果你非要写递归版，又不想承担重复计算，可以加记忆化缓存：

from functools import lru_cache @lru_cache(maxsize=None) def fib_memo(n): if n <= 1: return n return fib_memo(n - 1) + fib_memo(n - 2)

加了lru_cache之后，每个子问题只计算一次，时间复杂度从 O(2^n) 降到 O(n)，递归的"优雅代码"和"高效执行"就兼得了。但你要明白一个前提：能用缓存的前提是子问题高度重叠。如果递推关系里每个子问题只被算一次，比如阶乘，那加缓存没什么意义。

4.3 第三组：遍历目录树，递归的天然主场与手动栈模拟

遇到树形结构——目录、JSON、多级评论——递归的优势就非常明显了，因为它本身就是"把大树拆成小树"。

递归遍历：

import os def walk_dir_rec(path): for entry in os.listdir(path): full_path = os.path.join(path, entry) if os.path.isdir(full_path): walk_dir_rec(full_path) else: print(full_path)

这段代码里没有任何"当前在第几层"的概念，因为每层递归自成一体，只管当前目录下的子项，遇到子目录就继续调自己。写起来几乎零负担。

如果你担心目录层级太深触发递归深度限制，可以改成显式栈的迭代版：

def walk_dir_iter(root): stack = [root] while stack: current = stack.pop() for entry in os.listdir(current): full_path = os.path.join(current, entry) if os.path.isdir(full_path): stack.append(full_path) else: print(full_path)

注意：这里用stack模拟的并不是"一层一层嵌套返回"的调用栈，而是"待处理的目录清单"。因为遍历时不要求返回上层后接着上次的位置继续（我们只需要输出所有文件），所以一个简单的先进后出列表就够用。这个例子特别能说明：迭代改写递归时，你得想清楚递归隐式维护的那个"栈"到底在撑起什么语义，不能照搬。

5. 最容易踩的四个坑：从无限递归到性能误判

5.1 无限递归：不是真的"无限"，是栈用光了

新手最怕的报错是RecursionError: maximum recursion depth exceeded。很多人第一反应是"我的递归是不是变成死循环了"。其实不是死循环，而是每一层调用都会在内存栈上占一帧，帧叠得太多，触发了系统保护。Python 默认递归深度上限是 1000 层，超过就抛这个异常。

常见的触发原因有两个：一是真的忘了写终止条件或者条件永远不成立；二是问题本身规模太大，比如处理一个上万元素的嵌套结构，正常递归也会超过 1000 层。

排查工具很简单：在递归函数里打印参数，看它怎么变化的。比如：

def fn(n): print("enter fn", n) if n <= 1: return 1 return fn(n - 1)

如果你发现n一直停在某个值不变，说明递推关系没有让规模递减；如果你发现n一路走但越过了应该停止的阈值，说明终止条件写错了；如果你发现n本来就在往外层拨，那肯定冤枉——可能你调用的根本是别的函数。

5.2 递归深度限制：临时调大可以，但物理边界绕不过去

网上很多说法是"遇到RecursionError就调大sys.setrecursionlimit"。这是个治标不治本的办法。setrecursionlimit(10000)确实能把 Python 的软限制调高，但每次函数调用都真实占用内存和栈空间，操作系统那层还有一个硬性上限，调到特别大之后程序不是爆RecursionError，而是直接段错误崩溃，连捕获的机会都没有。

我的经验是：如果递归深度可能超过几百层，直接考虑迭代；如果深度不确定但预计可控，可以用递归加深度保护；如果项目里到处发生深度问题，那就是数据结构设计上的问题——比如树没有做平衡、嵌套层级没有限制，这时候改代码结构比调限制更重要。

5.3 迭代的隐蔽边界错误：多算一次还是少算一次

迭代看起来比递归安全，但边界错误往往更隐蔽，因为代码不会报错，只是结果不对。我踩过的两个典型坑：一个是range终止值差一，另一个是while循环里状态变量更新的位置不对。

比如求数组所有元素的和，写成：

def buggy_sum(nums): total = 0 i = 0 while i <= len(nums): total += nums[i] i += 1 return total

当i等于len(nums)时，nums[i]直接IndexError。如果把条件写成i < len(nums) - 1，又会少加最后一个。正确的应该是while i < len(nums)。这种问题，多一个等于号就翻天。

我自己的检查法只有一个：把最极端的输入先跑一遍，再打印每一步的状态变量，确认最后一轮循环结束后状态变量符合预期。没有捷径。

5.4 性能误判：把"代码优雅"当成"性能好"

还有一种坑不是在写代码时踩的，是在分析时踩的。看到递归版很短，就觉得"代码越短跑得越快"，这是大错特错。短的递归代码背后可能挂着一棵指数级的调用树，也可能每一层都在创建新列表、新字符串，开销一点都不小。

判断性能，不要看代码行数，要看三样东西：时间复杂度、空间复杂度、以及每一层递归里额外复制或创建的数据结构。比如我见过有人用递归统计字符串里某种字符的个数，每一层都切片，跑起来又慢又占用内存。这种问题其实迭代一行就解决了。性能判断的原则永远是"先定量，再优化"：拿大数据实测一下，不要凭感觉。

6. 怎么选：我的个人判断框架和最后一点体会

6.1 先看数据规模，再看数据结构

我现在接到一个任务，第一反应不是"我要用递归还是迭代"，而是先问两个问题：处理的规模大不大？问题本身是不是树形/嵌套结构？

如果规模从一开始就可能是成千上万，尤其是一眼看不完的深度——比如超深目录、超长链表——迭代几乎总是安全的选择，因为递归深度限制是硬约束。如果规模小、结构天然是分形的——比如 JSON 解析、目录树、多级评论——递归的代码可读性碾压迭代，我没有理由不用。

一个简单的决策表：

6.2 递归不是"高级技巧"，是一种思维工具

很多人把"会写递归"当成某种炫技，其实不是。递归真正的价值，是逼着你从"怎么一步一步算"切换到"怎么把一个复杂问题定义成更小的问题"。

这个过程对算法能力的提升非常大。我后来学树和图的遍历、快速排序、归并排序，都发现核心思想就是递归的"拆解"：一个数组先分成两个小数组，分到不能再分就合并。如果没有第五天那次把递归彻底搞清楚，后面这些全都会绕弯路。所以别急着问"什么时候用得上"，先把这种思考方式练成肌肉记忆。

6.3 我自己的一个实用小技巧：两个版本都写

面对不定规模的算法题时，我的习惯是先写出递归版，确认递推关系正确，逻辑没问题；然后再考虑需不需要改写成迭代版。递归版是"验证思维正确"的工具，迭代版是"应对工程限制"的工具。

改写时也不追求一次到位，而是先把递归的隐式栈用显式列表模拟出来，跑通之后再优化状态变量。这一步一步来，比直接"凭感觉手写迭代"稳妥得多。毕竟代码跑错一次，排查的时间往往比多写几行代码的时间长。

Day 5 的这个坎，我到底是迈过来了。回头看，递归和迭代只是同一枚硬币的两面：一个把问题的粒度不断切小，一个把进度一格一格推到底。没有哪个更高级、哪个更菜，只有哪个更合适。遇到卡壳的时候，不用硬背模板，亲手把调用栈和状态变量在纸上各画一遍，脑子里那团浆糊基本就散了。