函数递归调用

官官方信息技术老师·11 页·深入（追求细节与边界）·0 次浏览·3 天前

✦ 函数递归调用信息技术函数递归调用运行程序

递归调用调用栈尾递归边界条件

函数递归调用

看清递归每一层的栈帧压入与回溯，掌握边界条件、尾递归优化与递归到迭代的转换

按空格/→ 演示下一步

1 / 11 页

全部页面点击任意一页，跳回舞台从这页播放

递归调用调用栈尾递归边界条件

函数递归调用

看清递归每一层的栈帧压入与回溯，掌握边界条件、尾递归优化与递归到迭代的转换

1第 1 页 · 函数递归调用

递归问题开场白

你拆过俄罗斯套娃吧？最大那层里面套着一个一模一样的更小娃娃，再拆还有，直到最小的实心那一颗——打不开为止。递归，就是让函数做一模一样的事。

递归定义

函数直接或间接调用自身，用自身的副本处理规模更小的同类问题

两个必备要素

基线条件（最小子问题直接返回）与递归步骤（缩小问题后调用自身）

调用栈机制

每次递归调用压入一个栈帧，达到基线后逐层弹出并返回结果

典型应用

树与图的遍历、数学序列（阶乘、斐波那契）、分治算法、回溯搜索等

俄罗斯套娃对应 →递归调用

外层套内层=大问题含同类小问题；最小实心娃娃=基线条件

n! = \begin{cases} 1 & n=0 \\ n \cdot (n-1)! & n \geq 1 \end{cases}

2第 2 页 · 递归问题开场白

递归定义和调用过程

迷宫里找出口——每到一个岔路就选一条深入，走到死胡同退回上层重新选——这种'深入再退回'的过程，正是递归调用栈的工作方式。

递归定义

函数直接或间接调用自身，把大问题拆解为同结构的子问题

基线条件

递归出口：最简情况下无需再递归，直接返回确定答案

递归条件

将问题推向规模更小的子问题，且每次都向基线靠近

调用栈过程

递推时压栈记录每层调用，到达基线后逐层弹栈回归

典型应用

阶乘、斐波那契、汉诺塔、二叉树遍历等结构自相似问题

俄罗斯套娃对应 →递归调用过程

打开一层又一层，最小的是基线；一层层合回去就是逐层返回结果

f(n) = \begin{cases} 1, & n \leq 1 \\ n \times f(n-1), & n > 1 \end{cases}

3第 3 页 · 递归定义和调用过程

运行程序

上一页讲了递归的'形状'——函数调用自身。但程序真跑起来时，机器怎么记住'这一层还没算完，等子调用回来再继续'？靠的是内存里一摞叠起来的'便签'，专业名叫调用栈。

调用栈

程序运行时的一块工作区，专门记录每一次函数调用的现场

栈帧

每次调用压入的一块记录，含参数、局部变量、返回地址

压栈与出栈

递归深入时压入新栈帧，回归时从栈顶弹出

终止与回溯

命中 base case 后开始逐层返回，把结果传回上一层

栈溢出

递归太深超出栈容量，程序崩溃——深度学习的边界

叠便签处理杂事对应 →调用栈压栈出栈

新便签压顶、做完撕顶，每张记着'我做到哪、做完去哪'

4第 4 页 · 运行程序

汉诺塔介绍

上一页跑完程序，你看到的'A→C、B→A...'就是这古老谜题的解。汉诺塔——一个用递归天然就能漂亮回答的问题，咱们先把谜面看清。

问题定义

三根柱子、n个大小不同的圆盘，从起点柱全部挪到目标柱，一次挪一个，大盘不能压小盘

传说起源

1883年法国数学家Lucas提出；传说64个金盘、每秒一步，全部挪完那天世界毁灭

递归拆分

n盘=上方n-1挪到中转柱+挪最大盘到目标+n-1从中转挪回目标；每步内部都是规模更小的同问题

最少步数

T(n)=2^n−1；n=3要7步、n=10要1023步、n=64要约1.8×10^19步

边界与应用

n=1是唯一基础情形（直接挪一步）；常用于递归栈深度测试、指数增长教学、问题分解训练

搬家叠箱子对应 →汉诺塔递归

先腾空上面小箱到临时桌 → 搬大箱去目的地 → 小箱叠回到大箱上方，每层内部又是同样三步

T(n) = 2^n - 1

5第 5 页 · 汉诺塔介绍

汉诺塔讲解

前页我们认识了汉诺塔——三根柱子、64个盘子。这页要真正弄懂它为什么是递归的经典案例，以及递归到底是怎么把难题拆开的。

递归核心思想

把n个盘子拆成「上面n-1个」与「最底下1个」两个子问题

三步走策略

①移n-1到辅助柱 ②移最底到目标柱 ③再把n-1从辅助柱移到目标柱

递推终止条件

只剩1个盘子时直接移动一次，递归到此返回

时间复杂度

移动次数为2ⁿ-1，n=64时约需1844亿亿步

搬家时大件最后搬对应 →汉诺塔最大盘最后动

小箱先一个个挪开让路，大箱才能一次到位——递归就是让小问题先解决

T(n) = 2T(n-1) + 1

6第 6 页 · 汉诺塔讲解

汉诺塔程序运行

上页讲了汉诺塔的拆分思路：把 n 块分成「上面 n-1 块」和「最底 1 块」。现在的问题是——翻译成代码后，程序到底是怎么一步步跑出正确顺序的？

函数签名

hanoi(n, src, dst, aux)：n 是盘数，src 源柱，dst 目标柱，aux 中转柱

基准情形

n=1 时直接 print「src→dst」，不再递归调用

代码结构

先递归移 n-1 到中转，再 print 底盘，最后递归移中转上 n-1

调用栈行为

每次递归调用把当前任务压栈，返回时弹栈，先压的后执行完

输出顺序反直觉

n=2 时实际打印「A→B、A→C、B→C」，不是按代码书写先后

代办清单对应 →递归调用栈

处理当前事被打断就先记下来（压栈），回头看清单顶端（弹栈）

T(n) = 2 \cdot T(n-1) + 1 \;\Rightarrow\; 2^n - 1

7第 7 页 · 汉诺塔程序运行

递归调用例题

前面我们跟着汉诺塔走完了一次完整递归。现在换四个更小的例题,把「拆成同形子问题」的套路在不同场景里再练一遍。

阶乘:最简模板

n! = n × (n-1)!,出口 n=0 返回 1;只有一次递归调用,最干净的入门例。

斐波那契:树形代价

fib(n)=fib(n-1)+fib(n-2),两次调用导致指数级重复计算,典型的反面教材。

爬楼梯:问题建模

n 级台阶每次跨 1 或 2 级,方案数 f(n)=f(n-1)+f(n-2);问题被抽象成递推结构。

字符串反转:尾递归风格

把首字符取出拼接在尾部,递归处理剩余子串;展示「用参数携带中间结果」的写法。

公司层层转包任务对应 →递归调用的调用链

总包把任务拆给分包,分包再拆,直到有人能直接做;结果再层层回传汇总

8第 8 页 · 递归调用例题

递归总结

从汉诺塔和例题的运行过程，我们已经完整看到了递归是怎么'进去'和'出来'的。现在把这一路走过的关键点串起来：递归到底在干什么？

定义

函数直接或间接调用自身，把大问题化为同结构的子问题

两个要素

必须有基例（终止条件）和递归式（向基例推进）

调用栈机制

每次调用入栈保留现场，归回时按栈顶顺序出栈

典型应用

分治算法、树/图遍历、汉诺塔、阶乘、斐波那契

边界注意

递归过深会栈溢出；重复子问题需记忆化否则指数爆炸

俄罗斯套娃对应 →递归调用栈

每开一个套娃（递推入栈）都把当前状态装进去，直到最小的那个（基例），再一个个合上（归回出栈）

f(n) = \begin{cases} c & n \leq 1 \\ a \cdot f(n/b) + g(n) & n > 1 \end{cases}

9第 9 页 · 递归总结

本节要点

✓终止条件（基例）是递归能停下来的唯一保险
✓每层调用都是独立栈帧，参数与局部变量各自一份
✓递归前语句递下去执行，递归后语句归上来执行
✓递归深度受栈容量硬性限制，过深即溢出
✓设计递归等于写数学归纳法：证基例 + 证递推

延伸主题：递归转迭代的等价改写尾递归与编译器优化递归的时空复杂度分析

10第 10 页 · 本节要点

课后思考

三个问题带走琢磨。先自己思考，再看参考答案——重要的不是答对，而是想清楚为什么。

1递归为什么必须有终止条件？少写一个，程序会出现什么现象？

参考答案没有终止条件 = 无限递归：每次调用都在栈上压入新帧，直到栈空间耗尽、程序崩溃（栈溢出）。基例就是递归的『刹车』。

2迭代也能实现重复逻辑，为何还需要递归？举一个迭代写起来明显更痛苦的例子。

参考答案递归胜在贴合『自相似』结构——树的遍历、分治、汉诺塔、排列组合，递归往往几行说清；迭代要手动维护栈/队列，逻辑繁琐得多。

3所有递归都能用循环改写吗？递归深度过大时，会暴露什么语言层面的『边界』？

参考答案都能——本质是把调用栈换成显式栈。但 Python 默认递归上限约 1000 层，深递归会抛 RecursionError，这是『递归不万能』的现实边界。

11第 11 页 · 课后思考