跳到主要内容
🔍
1.3.3已发布beginner · 约 3 课时 · P0

函数与递归

掌握函数声明/定义/调用与传值语义，理解递归三要素与栈开销

  • 来源
  • 补充

标记说明：【来源】来自上传资料 · 【补充】课程新编 · 【纠错】按勘误表修正 · 【更新】过时内容已现代化 · 【待确认】无法可靠还原

完成标准（本章）

  • 📖 已阅读：滚动 ≥ 80% 且有效阅读 ≥ 180 秒
  • ✏️ 已练习：小练习正确率 ≥ 60%
  • 📝 已通过测验：分数 ≥ 60 分
  • 🛠️ 已掌握还需完成实践任务
学习状态：未开始

1.3.3 函数与递归

本章来源：函数定义/声明/调用、形参与实参、传值与传址、递归三要素、阶乘/斐波那契/汉诺塔来自《第一阶段讲义》20.1-20.3 节【来源】，经重新组织表述；示例代码（原资料为截图无法还原）与全部练习为新编【补充】并本机实测（gcc 15.2.0）。平台适用性 universal。

① 学习目标

  1. 区分函数声明（原型）、定义与调用，写出先声明后调用的多函数程序；
  2. 说清 C 参数一律传值：形参是实参的副本；"传址"是把地址值复制进指针形参、间接修改所指对象——不是引用传递；
  3. 说出递归三要素（基准情形 / 递归步骤 / 规模递减），并能用三者审查递归函数；
  4. 画出阶乘/汉诺塔的递归调用栈图，说明递归的栈开销与栈溢出风险；
  5. 按"数据规模与栈限制"在递归与迭代之间正确选型（实践任务）。

② 前置知识

  • 必选：1.3.1 指针基础（传址需要指针参数）；1.3.2 二级指针（想修改调用者指针时的延伸）；
  • 建议：1.2.4 控制结构（迭代的 for/while 基础）。

③ 核心概念【来源】

概念说明
声明 vs 定义 vs 调用声明（原型 int add(int, int);）只告诉编译器签名；定义给出函数体；调用是执行。先声明后调用是工程习惯（头文件里放声明）
形参 vs 实参定义处的参数是形参（parameter），调用处传入的是实参（argument）；调用时实参值复制给形参
传值（pass by value）C 唯一的参数传递方式：函数内改形参不影响实参（ex1 的 swap_by_value 实证）
传址把实参的地址值复制进指针形参（swap_by_address(&x, &y)），函数内通过 *p 间接修改调用者的变量——表述为"通过指针间接修改"，不可说成"C 的引用传递"
递归三要素① 基准情形（base case，不再递归直接返回）；② 递归步骤（把问题缩小后调用自身）；③ 规模递减（每次递归参数向基准逼近，否则无限递归）
调用栈每次调用在栈上分配栈帧（局部变量/返回地址）；递归层数×栈帧大小 = 栈开销；层数过深→栈溢出（stack overflow）
递归 vs 迭代递归代码贴近数学定义、可读性好；迭代无栈帧累积、效率高。递归深度可预估且规模小时递归合适；嵌入式栈小（几 KB）时大数据量优先迭代
汉诺塔经典递归：n 盘 → 先移 n-1 盘到中转柱（递归），再移底盘，再移 n-1 盘到目标柱（递归）；移动次数 2^n - 1

④ 通俗解释【补充】

  • 传值是"复印文件"：把文件复印一份递进去，里面的人怎么改复印件，原件纹丝不动——swap_by_value 没交换就是这回事；
  • 传址是"留门牌号"：把原件的门牌号写给他，他按门牌号上门改原件——swap_by_address 交换成功；
  • 递归是"俄罗斯套娃"：每层娃娃开一层壳（递归步骤），直到最小的娃娃（基准情形）不再套娃；忘写"最小娃娃"就永远套下去（无限递归 → 栈被挤爆）；
  • 调用栈是"待办便签塔"：每次调用压一张便签（局部变量+返回到哪），递归 n 层就是 n 张便签——栈（便签本）用完就 stack overflow；
  • 选型口诀一句话：规模小、定义天然递归 → 递归；规模大、栈小（嵌入式）→ 迭代。

⑤ 示例代码

代码示例与验证记录

  • examples/ex1-swap-value-address.c传值 vs 传址对照（swap 成功与失败）✓ 已实测（gcc 15.2.0 / MinGW-w64 x86_64 / Windows 11, 2026-08-15）
    编译：gcc ex1-swap-value-address.c -o ex1 -std=c11 -Wall -Wextra -Wpedantic
    适用环境：LinuxWindows(MinGW)
    展开预期输出（实测）
    after swap_by_value: x=10 y=20（未交换）
after swap_by_address: x=20 y=10（已交换）

    差异说明：本机实测（0 警告）；传值只交换形参副本；传址通过指针间接修改调用者变量

    完整源码见 /code 代码示例页

  • examples/ex2-factorial.c阶乘：递归 vs 迭代对照（0..10 全等）✓ 已实测（gcc 15.2.0 / MinGW-w64 x86_64 / Windows 11, 2026-08-15）
    编译：gcc ex2-factorial.c -o ex2 -std=c11 -Wall -Wextra -Wpedantic
    适用环境：LinuxWindows(MinGW)
    展开预期输出（实测）
    factorial( 0): rec=         1 iter=         1
factorial( 1): rec=         1 iter=         1
factorial( 2): rec=         2 iter=         2
factorial( 3): rec=         6 iter=         6
factorial( 4): rec=        24 iter=        24
factorial( 5): rec=       120 iter=       120
factorial( 6): rec=       720 iter=       720
factorial( 7): rec=      5040 iter=      5040
factorial( 8): rec=     40320 iter=     40320
factorial( 9): rec=    362880 iter=    362880
factorial(10): rec=   3628800 iter=   3628800

    差异说明：本机实测（0 警告）；递归版含基准情形（n<=1）与规模递减（n-1）；0 与 1 的基准同样正确

    完整源码见 /code 代码示例页

  • examples/ex3-hanoi.c汉诺塔（3 盘，7 步；2^n - 1 验证）✓ 已实测（gcc 15.2.0 / MinGW-w64 x86_64 / Windows 11, 2026-08-15）
    编译：gcc ex3-hanoi.c -o ex3 -std=c11 -Wall -Wextra -Wpedantic
    适用环境：LinuxWindows(MinGW)
    展开预期输出（实测）
    move disk 1: A -> C
move disk 2: A -> B
move disk 1: C -> B
move disk 3: A -> C
move disk 1: B -> A
move disk 2: B -> C
move disk 1: A -> C
total moves = 7（2^3 - 1 = 7）

    差异说明：本机实测（0 警告）；移动序列是 3 盘唯一最优解；把 3 改成 4 得 15 步（指数增长，勿在嵌入式上跑大 n）

    完整源码见 /code 代码示例页

  • examples/ex4-infinite-recursion.txt无限递归与栈溢出（conceptual：静态讲解，不运行）概念讲解示例✓ 文档核对（非执行）· C 调用栈机制与常见实现行为核对, 2026-08-15
    编译：无（静态讲解文本；不运行无限递归）
    适用环境：LinuxWindows(MinGW)
    展开文档核对记录
    （无运行输出——本示例为静态讲解文本，见文件内容）

    差异说明：内容按函数调用栈机制核对：每次调用分配栈帧（局部变量+返回地址），缺基准情形或参数不递减 时递归永不终止、栈帧无限累积 → 栈溢出（stack overflow，通常触发段错误/栈保护崩溃）。 不运行无限递归演示（会导致进程崩溃，无教学增益）

    完整源码见 /code 代码示例页

⑥ 编译与运行方法

gcc ex1-swap-value-address.c -o ex1 -std=c11 -Wall -Wextra -Wpedantic
./ex1    （Windows: ex1.exe）

三个示例均为本机实测（gcc 15.2.0，0 警告），输出见示例卡折叠区；ex3 汉诺塔为 3 盘（7 步），可在源码把 3 改成 4 观察 15 步（层数指数增长）。

⑦ 常见错误

症状原因解决
swap 函数调用后没交换参数传值：只交换了形参副本传地址（swap(int *a, int *b)）并在函数内解引用交换
递归函数死循环/段错误（stack overflow）缺基准情形或参数不递减用三要素审查：基准存在？每次递归向基准逼近？
把"传址"说成"引用传递"C 没有引用（那是 C++）正确表述：把地址值复制进指针形参，间接修改所指对象
头文件里写函数体导致重复定义声明与定义混淆.h 只放原型（声明），.c 放定义（1.3.10 展开）
深递归在嵌入式上崩溃任务栈仅数 KB，递归栈帧累积超出预估递归深度；大数据量改迭代（ex2 对照）
依赖编译器尾递归优化尾调用优化是优化行为，标准不保证不把性能押在尾递归上；需要保证就写迭代

⑧ 小练习

小练习

学习自测：提交后才显示答案与解析（前端判分，不作为正式考试）

  • ex-1-3-3-1.swap(int a, int b) 只交换形参副本，调用后实参不变，根本原因是？（单选）

    ◌ 未作答

  • ex-1-3-3-2.代码审查：int f(int n) { return n * f(n - 1); } 有什么问题？（单选）

    ◌ 未作答

  • ex-1-3-3-3.递归版的阶乘在 n 非常大（如 100 万）时会出什么问题？（单选）

    ◌ 未作答

⑨ 章节测验

章节测验

共 5 题题库 · 随机抽 5 题 · 及格线 60 分 · 前端判分（学习自测）
开始测验 →

⑩ 实战任务

实践任务

斐波那契递归版与迭代版性能对比 + 递归调用栈图

实现 fib(n) 的递归版与迭代版，对比两者在 n=30/35/40 下的运行耗时（本机用 time 或 clock() 计时），画出 fib(4) 的递归调用栈图（标注每次调用的参数与返回值）， 并写一段 100 字以上的"递归开销与选型"小结。

输入与输出

程序输入：n（如 40）。输出：fib(n) 的值 + 递归版/迭代版各自耗时（clock() 毫秒级）。 交付物：① 两版源码；② fib(4) 调用栈图；③ 小结。

功能要求

  • 递归版与迭代版各实现 fib（long long 防溢出，说明 n 上限）
  • 用 clock() 测量两版在 n=30/35/40 的耗时并打印
  • 画出 fib(4) 的递归调用树/栈图（含参数与返回值）
  • 写出"递归 vs 迭代：时间/空间开销与选型"小结

限制条件

  • 不在嵌入式板卡上跑大 n（本任务在 PC 上做）
  • 计时对比只作教学观察（不把单次计时写成精确结论）

验收步骤（自检清单 0/4）

验收标准

  • 两版结果一致且耗时打印正常（验收步骤 1/2）
  • 栈图体现重复计算（fib(2) 出现多次）与深度（验收步骤 3）
  • 小结提到栈开销 O(n) 与递归版指数时间（验收步骤 4）

常见失败原因

  • 递归版缺基准情形（fib(0)/fib(1)）
  • 耗时测量放在一次性调用上（应循环多次取平均或直接比较大 n 差异）
  • 把递归版在 n=40 的慢归因于编译器而非指数复杂度

可选扩展

  • 给递归版加备忘录（数组缓存）观察提速
  • 用 -O2 重编译对比两版耗时变化

完成必要清单后才能计入"已完成实践"（学习状态自动推导，不提供一键完成）

⑪ 面试问题

面试问题

  • C 语言里函数参数是传值还是传引用？"传址"是怎么回事？高频C/C++ · medium

    要点：C 一律传值：形参是实参的副本。"传址"是把变量的地址值复制进指针形参，函数内通过解引用间接修改调用者的变量——本质仍是传值。

    传值意味着函数内对形参的任何赋值都不影响实参（swap(int a,int b) 交换失败的原因）。 "传址"（swap(int *a,int *b) + 调用传 &x,&y）只是把地址这个"值"复制给了形参， 函数内 *a 解引用访问的是调用者的变量，所以能交换成功。严格表述： C 不存在引用传递（那是 C++ 的 &）；"传址"= 传地址值 + 间接访问。 面试加分项：想修改调用者的指针变量本身，需要传指针的地址（二级指针）。

    追问：
    • 追问：如何在一个函数里修改调用者的 int *p 本身？（int **pp + &p，或返回新指针）
    评分要点：
    • 传值本质
    • 传址=传地址值+解引用
    • 与 C++ 引用的区别
  • 写递归函数要注意什么？递归有什么风险？高频C/C++ · medium

    要点：三要素：基准情形、递归步骤、规模递减；风险：每层调用占栈帧，深度大时栈溢出；性能与栈开销高于等价迭代。

    三要素是正确性保证：① 基准情形让递归终止；② 递归步骤把问题分解为子问题； ③ 每次调用参数向基准逼近（如 n-1），否则无限递归。 风险：调用栈每层一个栈帧（局部变量、返回地址），深度×帧大小=栈消耗； Linux 默认栈 8MB、嵌入式任务栈常仅几 KB，深递归直接栈溢出（崩溃）。 工程选型：规模小、定义天然递归（树遍历、汉诺塔）用递归；大规模/嵌入式栈小改迭代； 不依赖尾调用优化（标准不保证）。斐波那契递归还有指数级时间复杂度的额外问题（可提 memo 或迭代）。

    追问：
    • 追问：为什么嵌入式里尽量避免深递归？（任务栈 1-16KB）
    评分要点：
    • 三要素
    • 栈帧与栈溢出
    • 迭代选型
  • 函数声明和函数定义有什么区别？为什么头文件里只放声明？高频C/C++ · easy

    要点：声明（原型）只有签名；定义含函数体。头文件只放声明可被多个 .c 安全包含；定义重复会出现链接期重定义错误。

    声明告诉编译器"存在这样的函数"（返回类型、参数类型），支持在定义之前调用； 定义给出实现（函数体），一个函数全程序只能有一份定义（内联/静态函数等特例另说）。 头文件被多个源文件包含时，若放定义则每个 .c 编译出副本，链接时报 multiple definition； 放声明则每个 .c 只引用同一份定义。工程惯例：.h 放原型与类型，.c 放实现（1.3.10 的 API 规范展开）。

    追问：
    • 追问：static 函数和 inline 函数在这个规则上有什么不同？（static 内部链接可放定义；inline 有特殊规则）
    评分要点：
    • 声明/定义区分
    • 多重定义问题
    • 头文件职责

⑫ 延伸阅读

  • 《C 程序设计语言（K&R）》4.x（函数与程序结构）；
  • 《C 语言程序设计：现代方法》第 9 章；
  • 下一章预告：1.3.4 函数指针与回调——把"函数"当作数据传递，驱动/事件框架的基础。

迁移训练（migration training）

把本章技能迁移到 Linux 与 嵌入式：

环节Windows（MinGW）Linux嵌入式
函数语义一致一致一致
栈大小系统默认默认 8MB（ulimit -s 可查）任务栈通常 1-16KB
递归深度较深可用较深可用必须预先估算，深递归禁用

不变的：传值语义、递归三要素、调用栈机制；要改的：递归深度的预算（嵌入式栈小，优先迭代）。

内容来源映射

内容部分资料位置标记说明
函数定义/声明/调用、形参与实参、传值与传址、递归三要素、阶乘/斐波那契/汉诺塔第一阶段讲义20.1/20.2/20.3 节【来源】正文在原资料基础上重新组织表述，未大段复制原文
示例代码（3 个可运行程序）与无限递归栈风险讲解无【补充】原资料示例代码以截图嵌入无法还原；本章示例全部新编并本机实测（gcc 15.2.0）
小练习 / 章节测验 / 实践任务 / 面试问题 / 延伸阅读无【补充】原资料该章无成体系练习，全部新编
① 学习目标② 前置知识③ 核心概念【来源】④ 通俗解释【补充】⑤ 示例代码⑥ 编译与运行方法⑦ 常见错误⑧ 小练习⑨ 章节测验⑩ 实战任务⑪ 面试问题⑫ 延伸阅读迁移训练（migration training）