这章内容是函数及函数递归。函数这个概念在代码里出现频率太高了几乎每个程序都离不开但很多人在初学阶段写函数就是“把代码包起来”碰到递归就直接懵圈总觉得这是某种玄学。其实递归没那么神它就是用一种特殊的方式调用函数本身把一个复杂的问题拆成同类型的子问题一层层拆到不能再拆再一层层返回结果。这篇东西我打算写成一份实操向的复习笔记把函数到底是什么、递归的执行过程怎么走、常见坑怎么避都摊开讲适合正在学编程基础、或者对递归一直处于“看得懂写不出”状态的同学参考。1. 先搞清楚函数存在的意义1.1 把重复逻辑装进盒子里我当年刚开始写代码的时候特别讨厌函数觉得这东西又绕又麻烦。写个计算逻辑直接从上往下排着写不就完了直到有一次一个登录校验的代码块我在三个地方各贴了一遍后来规则变了要加一个“连续输错五次就锁定半小时”的条件我改了第一处忘了改第二处结果线上出了个逻辑不一致的诡异问题。那天我才真正体会到函数这东西不是为了“显得高级”而是为了“让同一段逻辑只维护一份”。函数本质上就是给一段代码起个名字之后每次需要用到这段逻辑就叫这个名字。比如一个金额格式化函数传给它是12345.6它返回12,345.60。你可以在订单页调用它在报表页调用它在导出的脚本里调用它里面就算写了一百行逻辑调用方也只需要一行。将来格式规则变了比如新规定只保留一位小数你只需要改函数内部那一个地方所有调用点自动跟着变。这种“单点修改全局生效”的能力是函数带给你最直观的价值。写函数的时候有个非常实用的判断标准如果一段逻辑你复制粘贴了第三遍就应该停下来抽个函数了。第一遍是需求第二遍是巧合第三遍就是设计问题了。这个标准不是我编的是很多老开发在实际项目里默认遵守的“事不过三”原则。在真实项目里重复代码是最容易滋生Bug的土壤因为改一处漏一处测试还不一定能覆盖到。抽成函数之后你反而有了一个明确的测试目标。1.2 参数、返回值与函数契约函数其实可以理解成一条小小的流水线参数是送进来的原料函数体是加工过程返回值是加工完的成品。调用函数的人不需要关心流水线内部怎么运作只需要知道“我给它什么它能还给我什么”。这就是函数签名形成的“契约”。写函数之前先想清楚输入和输出再动手写函数体顺序很重要。我见过很多初学者一上来就埋头写中间的逻辑写到一半才发现这个函数到底需要几个参数、要返回什么根本还没理清最后只能用全局变量到处传数据把代码搞得一团糟。正确的做法是先把函数签名定下来名字是什么、参数列表是什么、返回值是什么。签名清楚了函数体就是在实现这个“输入到输出”的转换。下面用Python举一个非常基础但有代表性的例子。假设我们要写一个函数判断一个分数是否及格def is_pass(score): 判断成绩是否及格返回布尔值 if score 60: return True return False这个函数契约就很清晰传入一个数字类型的分数返回一个True或False。调用方拿到返回值之后可以直接用在if is_pass(score):这样的判断里。如果你把这个函数写成了直接打印及格或不及格那这个函数的复用价值就大打折扣了因为你没法在别的地方把这个结果继续参与运算。这个细节很多人会忽略一个函数要么负责计算并返回结果要么负责处理副作用比如打印、写文件尽量别混在一起。1.3 函数设计要小而纯“函数要短小、职责单一”这句话最初是从代码整洁的角度提出来的但它确实能实实在在减少你的调试成本。一个函数只做一件事它的名字就能准确地描述它在做什么。比如get_user_by_id就是按ID查用户send_email就是发邮件看到名字就知道行为不用进去读代码。而“纯函数”这个概念对初学者来说也应该尽早建立。纯函数的意思是同样的输入永远返回同样的输出并且在函数体内不修改外部状态。打个比方一个计算圆面积的函数circle_area(r)你要它算r5它永远返回78.5它不会偷偷修改某个全局变量也不会因为你上次调用过它而影响这次的返回值。这种函数最好测、最好调、最好组合。反过来如果一个函数内部会改全局变量、会依赖某个外部状态那它就像一颗定时炸弹你不跑到那一步永远不知道它炸不炸。我在带一些新同事写代码的时候会让他们把函数尽量写成纯函数必要的时候才去碰文件、数据库这些外部东西。这样做的好处非常直接你可以在命令行里随时单测传个参数进去看返回值对不对不需要搭一堆环境。项目里后期维护的人也会感谢你因为一个纯函数可以被放进各种不同场景里而不用担心它“污染”了环境。2. 递归从“自己调用自己”说起2.1 递归的三要素“递归就是函数自己调用自己”这句话几乎所有教材都会说但它只描述了现象没有描述本质。递归真正的本质是把一个规模较大的问题拆成一个相同类型但规模更小的问题反复拆到最简形式再逐层返回。用生活里的例子来类比假设你要知道“坐在你左边那排第七个人叫什么名字”你可以问左边那个人“你旁边第六个人叫什么”他再问他旁边第五个人……到最后一个人那里他直接告诉你“我叫某人”然后这个信息一层层传回来。每次问问题问题规模都缩小了一个最后有一个不需要再问别人的边界点这就是递归的出口。递归要有三个写作上的必备条件。第一个是必须有结束条件也叫递归出口不满足就继续调用自己满足就直接返回。第二个是每次调用都在向出口靠近也就是说问题规模必须不断缩小不能原地打转。第三个是每次调用的问题类型要和原问题一致如果原问题是对数字排序、子问题变成了遍历链表那递归的逻辑就断了。把这三个条件翻译成代码框架大概是这么个形状def solve(problem): if problem is small_enough: # 出口 return direct_answer # 把problem拆成更小的子问题 sub_problem make_smaller(problem) sub_answer solve(sub_problem) # 递归调用 return combine(sub_answer)这个框架看起来很抽象但实际写代码的时候就照着它套准没错。先写出口再写递归调用这个顺序我建议你一定要养成肌肉记忆。2.2 用阶乘拆解递归执行过程纸上谈兵没用得拿个具体的例子走一遍。阶乘是最经典的递归入门题n! n * (n-1)!并且0! 1。def factorial(n): if n 0: return 1 return n * factorial(n - 1)这个函数看起来很简短但它的执行过程其实相当精妙。假设调用factorial(3)函数不会一下就算出结果而是先判断3 0吗不是于是它要计算3 * factorial(2)。但factorial(2)还没算完它又需要计算2 * factorial(1)。再往下factorial(1)需要1 * factorial(0)。直到factorial(0)直接命中出口返回1。这时候调用栈开始逐层“弹回”factorial(1)得到1 * 1 1factorial(2)得到2 * 1 2factorial(3)得到3 * 2 6。我建议你自己拿纸笔把这个过程画一遍画成一个向下的箭头再向上返回的图。向下是层层展开每一步都在“记账”记的是“我当前的结果要靠下面一层的结果来算”向上是逐步收束每一层拿到子结果后做一次乘法然后返回。你真正把这张图画过一遍之后“递归是自顶向下拆分、自底向上合并”这句话就刻在脑子里了。2.3 递归和循环怎么选递归和循环是两种可以互相替代的重复执行方案但它们的适用场景并不一样。循环擅长处理“明确知道迭代次数”的线性任务比如遍历一个数组、打印一百次问候语。递归则更适合那些“问题本身就带有嵌套结构”的场景比如遍历一棵树、解析带括号的表达式。选递归还是选循环我的判断标准是看代码的可读性和心智负担。如果递归写法更贴合问题的自然结构比如处理文件目录我就选递归如果循环两三行就能说清楚那就别硬套递归。递归确实有代价每一次函数调用都会在程序调用栈上占用一帧空间递归深度太大会导致栈溢出这一点后面会专门说。很多教材会强调递归比循环慢所以尽量用循环。这个说法放到今天需要重新审视如果你处理的是深度只有几十层的树结构递归和循环在性能上的差距完全可以忽略但递归代码写起来可能比手工维护栈的循环简洁得多。与其盲目追求性能不如先保证代码结构正确和清晰真遇到性能瓶颈再去优化也不迟。3. 典型递归场景与进阶写法3.1 树形结构遍历是递归的主场递归最舒服的领域就是处理有层级关系的数据。文件目录就是一棵典型的树一个文件夹下面有文件夹文件夹下面还有文件夹直到碰到普通文件才停止。用递归遍历这种结构代码简洁到让人感动。import os def walk_dir(path, indent0): for name in os.listdir(path): full_path os.path.join(path, name) print( * indent name) if os.path.isdir(full_path): walk_dir(full_path, indent 1)这段代码的逻辑一目了然打开一个目录逐个看里面的条目如果是子目录就进入它重复同样的动作。你会发现递归调用被放在if分支里把“继续往下钻”的动作和普通文件并列展示哪怕是没学过递归的人也能大概读懂。类似的场景还有网站的评论楼中楼。一条评论下面有回复回复下面还有回复每条回复都是同样结构的数据。用递归去把整条评论链拉出来比循环嵌套循环要清晰无数倍。我在做某个社区项目的时候就干过这件事当时我用一次递归函数处理任意深度的评论列表配合缩进前缀就能在前端展示出层级结构。3.2 记住那些算过的值记忆化递归有个非常典型的性能陷阱就是重复计算。拿斐波那契数列来说F(n) F(n-1) F(n-2)如果直接按这个公式写递归你会算出一棵指数级增长的调用树F(40)就能让你的程序卡到怀疑人生。问题出在同一个子问题被反复计算了无数次比如F(3)可能在计算F(5)和F(4)的过程中各自算了一遍。解决办法也很简单把已经算出来的结果存下来下次需要时直接取不再重新递归。这就是记忆化。在Python里可以用一个字典手动做也可以直接用标准库自带的functools.lru_cachefrom functools import lru_cache lru_cache(maxsizeNone) def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)加一行装饰器复杂度直接从指数级降到线性级。这个优化思路不局限于斐波那契任何递归函数只要它存在重复子问题你都该考虑加缓存。判断标准很简单递归函数在递归过程里同一个参数的调用会不会被重复触发会就缓存。我在实际项目里处理过一些树形数据的统计逻辑节点之间有大量共享子结构加缓存之后性能提升了几十倍代码改动却只有三五行。3.3 用生成器代替常规递归遍历如果你在处理一个非常深的树结构又不想一次性把所有结果都堆到内存里可以用Python的生成器配合递归把递归的过程改造成“边遍历边产出”的惰性模式。def walk_files(path): for name in os.listdir(path): full os.path.join(path, name) if os.path.isdir(full): yield from walk_files(full) else: yield full这里的关键词是yield和yield from。yield会把一个结果“吐”出来同时函数状态被冻结下次继续进行yield from则会把子生成器里的每一个产出都转发出来。你调用for f in walk_files(/some/dir)的时候它并不会一次性把所有文件路径都生成完而是每遍历到一个文件才产生一个结果。这在处理海量文件的时候能明显降低内存占用。这种“递归加生成器”的组合在写爬虫、日志分析、配置文件扫描类工具时非常实用。我写过一个配置扫描小工具需要递归检索目录下所有指定后缀的配置文件用的就是这种写法。生成器版本比普通返回列表的版本代码量几乎一样但是内存友好度天差地别。4. 参数传递与作用域容易被忽略的细节4.1 值传递和引用传递的区别很多资料在讲Python函数时会提到“不可变对象按值传递可变对象按引用传递”这个说法不算严谨但理解起来确实够用。不可变对象包括数字、字符串、元组传给函数后函数内部怎么改都不会影响外面的变量可变对象包括列表、字典、集合函数内部如果直接修改了它外面的数据也会跟着变。这个差异引发的坑非常常见。下面这个例子我几乎每年都能见到有人踩def add_item(item, container[]): container.append(item) return container print(add_item(a)) # [a] print(add_item(b)) # [a, b]第二次调用时你会发现container居然还记得上一次的[a]。原因就是默认参数[]在函数定义时只创建了一次之后所有调用共享同一个列表对象。这个问题在面试题里出现概率极高但更重要的是在实际代码里也容易隐藏。解决办法很简单不要用可变对象做默认参数改成None再在函数体内判断。还有一个更隐蔽的坑是在函数内部对可变对象重新赋值。比如def update_list(lst): lst.append(1) # 会修改外部列表 def reset_list(lst): lst [1, 2] # 不会修改外部列表只是局部变量重新绑定append是修改原列表对象而lst [1, 2]只是让局部变量lst指向了一个新对象外部引用不受影响。想清楚“你是在修改对象本身还是在换一个新对象”是理解这类问题的关键。4.2 局部变量、全局变量和闭包作用域这个概念说白了就是“一个变量名在哪些范围内能被看到”。函数内部定义的变量是局部变量函数外部定义的是全局变量Python在函数内部读取全局变量没问题但要修改全局变量就得用global声明。这个规则看似简单实际写起来容易踩坑。一个常见的困惑是这样count 0 def increment(): count 1写这段代码的人以为它能修改外面的count结果运行会直接报错提示在赋值之前引用了局部变量。因为Python在编译函数时看到一个count被赋值了就把它当成了局部变量而count 1第一步要先读取count这读的就是还没有赋值的局部变量所以报错。正确做法是count 0 def increment(): global count count 1不过说实话在现实项目里过度依赖global是个不太好的信号。全局变量让函数变得不纯粹也让调试变困难因为任何一处都可能改到同一个变量。一个更优雅的替代方案是用闭包。闭包的意思是内层函数引用了外层函数的变量外层函数返回内层函数于是这个内层函数在定义它的环境消失后依然能记住那些变量。def make_counter(): cnt 0 def increment(): nonlocal cnt cnt 1 return cnt return increment这里用到了nonlocal关键字声明cnt不是当前局部变量而是来自外层函数。这种模式在写计数器、缓存、配置校验器的时候都特别有用。闭包最初看起来有点绕但它实际上是“函数也是对象”这种思维的延伸深入理解之后你对函数签名的理解会提升一个层次。5. 常见问题与排查技巧实录5.1 无限递归与递归深度上限写递归最容易碰到的就是忘了写出口或者出口条件永远不满足导致函数无限调用自己最后报一个RecursionError。Python为了防止程序彻底崩溃给递归深度设了一个上限默认通常是1000层。也就是说递归调用超过这个深度解释器会主动打断你。遇到这个报错怎么排查第一步不是急着改代码而是先检查出口条件。把出口条件写在递归函数的第一行打印一些信息看每次调用时参数的变化。最典型的情况就是参数没有变小比如你写def f(n): return f(n 1)这种就是典型的永远向远处跑永远碰不到出口。def safe_recursive(n, depth0): if depth 900: raise ValueError(递归太深检查出口条件) if n 0: return 1 return safe_recursive(n - 1, depth 1)上面这段加了一个深度保护参数算是一种兜底手段。在调试期间特别有用它能让你快速定位问题出在哪一层。等你确定递归逻辑正确了再把保护去掉或者调高。说实话我在写新的递归函数时前期一定会先加这样一层保护因为谁也没办法保证第一版逻辑一定没问题。5.2 排查函数Bug的三个实用方法我在项目里调试递归和普通函数问题时比较常用的方法有这么几个。第一个是打印法。在每个函数入口和出口处打印关键变量和返回值把函数完整的调用地图画出来。递归场景下建议打印的时候带上缩进用 * depth来表示当前处在哪一层这样输出可读性会好很多。比如遍历树的时候每进一层多缩进两个空格输出就像一颗树一样清晰。第二个是小样例法。拿一个规模特别小的数据来跑比如递归处理列表时就用[1, 2]处理树就用一个只有两个节点的树。在小规模数据上手动推演一遍看看代码输出和手算结果是否对得上。这个方法对递归尤其有效因为递归的报错信息往往不会直接告诉你是哪一层逻辑错了缩小输入范围能让你更快锁定问题。第三个是“只看输入输出”法。把函数拆开分步骤验证。如果一个函数同时做了判断、递归、合并结果你就很难判断是拆分逻辑错了还是合并逻辑错了。解决方法是先假设递归子调用返回的结果是正确的然后单独检查当前层怎么把子结果变成最终结果。这一层对了再往下一层看。递归问题最怕的就是在没定位清楚的情况下乱改通常越改越乱。5.3 如何设计一个可控的递归每次写递归之前我都会先做两件事第一手算一下最小的输入比如n0、空列表、只有一层深度的树保证出口能得到正确结果第二想清楚“当前这一层”和“下一层”之间的衔接关系把公式写在纸上。这个习惯帮我避开了大量“看似正常但结果就是不对”的坑。比如写一个“统计文件夹下所有文件大小总和”的递归我会先写一个empty_dir0的出口再写一个“当前文件大小 所有子目录大小的总和”的公式。公式写出来之后翻译成代码就只是套模板而已。很多人写递归写不出来不是不会语法而是脑子里没有“当前的层怎么跟子层协作”的画面所以你一定要注重纸上演算的过程。另外递归代码的命名也很关键函数名一定要体现这个函数到底返回什么。比如total_size(path)、count_visible_nodes(root)、collect_tags(node)名字越具体调用起来越不容易弄错数据类型。有时候你写出来的递归返回值跟调用方期望的不一致查到最后发现是函数命名太模糊自己把自己带偏了。最后提一个在项目里常见的惯性操作如果你发现递归代码结构混乱别急着硬调试先考虑能不能换个数据结构。能改写成循环的就改写循环能用队列或栈的就把递归换成显式栈能用层级遍历的就别硬递归。有些问题用递归写很优雅但有些问题用迭代反而更自然。划不划算得用实际代码去衡量而不是迷信某一种写法。我个人的实际感受是函数和递归这两块内容刚开始学的时候都会觉得“懂了但不会写”这非常正常。我自己也是写了无数遍阶乘、遍历了无数遍目录之后才慢慢找回手感。最笨也最有效的方法就是找一个树形结构比如自己电脑里某个深一点的文件夹目录从头到尾写一个遍历脚本打印出层级结构然后试着自己加上各种过滤条件。等到你能把一个目录树玩转了递归对你来说就不再是玄学而是工具箱里一件顺手的工具。