前面几节课咱们把函数怎么定义、怎么调用、怎么传参数都聊透了。今天咱们说两个新东西：一个是“套娃”，一个是“自己喊自己”。
你没听错——函数可以在别的函数里面被调用，也可以调用自己。
这俩概念一个比一个有意思，特别是后面那个，很多人第一次接触到的时候脑子是转不过弯来的。但你别怕，咱们掰开揉碎了说，你跟着我的思路走，很快就能整明白。
先讲函数的嵌套调用。这个词儿听着挺唬人，实际上就是你早就干过的事儿。
啥叫嵌套调用？说人话就是：在一个函数里面调用另一个函数。
你想想，你写的每个程序是不是都在main里调用了printf和scanf？这就是嵌套调用啊——main里面调了别的函数，只不过那些函数是C语言自带的而已。
现在换成你自己定义的函数，道理一模一样：
#include <stdio.h> int add(int a, int b) { return a + b; } int add_and_double(int a, int b) { int sum = add(a, b); // 在函数里面调用了另一个函数 return sum * 2; } int main() { int result = add_and_double(3, 4); // 在main里面调用了add_and_double printf("%d\n", result); // 输出14: (3+4)*2 = 14 return 0; }
你看，add_and_double里面调用了add，这就是嵌套调用。流程很简单：
-
main里调用add_and_double(3,4) -
程序跳到
add_and_double去执行 -
add_and_double里面调用了add(a,b)，程序又跳到add去执行 -
add算完返回结果，回到add_and_double继续 -
add_and_double算完返回，回到main继续
一层套一层，每一层都是“跳到下一层，下一层干完活回来，我再接着干”。
这个思想特别重要——一个函数可以调用任何其他函数，没有任何限制。 你甚至可以A调B，B调C，C调D，想调多深调多深。
那什么是递归调用呢？
递归比嵌套调用更狠——函数不调用别人，它调用自己。
没错，一个函数在执行的过程中又调用了它自己。这听起来像个死循环，对吧？确实，如果写得不讲究，它就是个死循环，然后程序崩溃。
但如果你设计得好，它能把一个复杂问题拆成几个同样类型但规模更小的问题，一层层拆下去，直到变成一个简单到不用拆的问题。
看个最经典的例子：用递归计算阶乘。
阶乘是什么？5! = 5 × 4 × 3 × 2 × 1。你发现没有，5! = 5 × 4!，而4! = 4 × 3!，3! = 3 × 2!，2! = 2 × 1!，1! = 1。
这个规律用数学公式写就是：
-
当n=1时，1! = 1
-
当n>1时，n! = n × (n-1)!
用C语言写成递归函数：
int factorial(int n) { if (n == 1) { return 1; // 终止条件：1! = 1 } return n * factorial(n - 1); // 自己调用自己 }
你输入5，想知道5!，就调用factorial(5)。它一看“n不等于1”，就返回5 * factorial(4)。但factorial(4)是多少？它得去算。factorial(4)返回4 * factorial(3)……就这样一层层往下“钻”，一直钻到factorial(1)，这里不再调用自己了，直接返回1。
然后呢？然后就开始“往回返”：
-
factorial(2)拿到了1，返回2 × 1 = 2
-
factorial(3)拿到了2，返回3 × 2 = 6
-
factorial(4)拿到了6，返回4 × 6 = 24
-
factorial(5)拿到了24，返回5 × 24 = 120
这就是递归的执行过程：先一层层往里钻，钻到底之后再一层层往外返。
画个图你脑子里就清楚了：
factorial(5)
└── 5 * factorial(4)
└── 4 * factorial(3)
└── 3 * factorial(2)
└── 2 * factorial(1)
└── 1 ← 钻到底了，开始往回返
└── 2 * 1 = 2
└── 3 * 2 = 6
└── 4 * 6 = 24
└── 5 * 24 = 120你看到了吗？每次调用自己，n就减1，直到n变成1，然后停住，再也不往下走了。
这就是递归的关键：必须有一个终止条件。 如果没有终止条件，或者条件写错了，函数就会永远调用自己，直到内存耗尽，程序崩溃。这叫“无限递归”，比死循环还狠——死循环是占着CPU不撒手，无限递归是把内存栈撑爆。
写递归函数的时候，脑子里要记住两件事：
第一，找终止条件。 也就是“什么时候不再调用自己，直接返回一个值”。这个条件必须正确，必须能到达。
第二，找递推公式。 也就是“这层的结果怎么用下一层的结果算出来”。把你当前要算的问题，拆成同类型但规模更小的问题。
你看阶乘：
-
终止条件：n == 1，返回1。
-
递推公式：n * factorial(n-1)。
那比如你想用递归算斐波那契数列，规则是：第1项和第2项都是1，从第3项开始每项等于前两项之和。
-
终止条件：n == 1或n == 2，返回1。
-
递推公式：fib(n) = fib(n-1) + fib(n-2)。
代码写出来就长这样：
int fib(int n) { if (n == 1 || n == 2) { return 1; } return fib(n - 1) + fib(n - 2); }
有些同学可能想问了：“这递归看着挺好玩的，那它和循环有啥区别？我是不是以后写程序都该用递归？”
我得给你一个实在的回答：递归是把问题变“简洁”了，但不一定让程序变“快”。
递归的好处：代码特别简洁，特别符合人类的数学思维。阶乘、斐波那契、树形结构遍历、汉诺塔……这类问题用递归写出来，那个代码漂亮得跟诗一样。
递归的坏处：每一次函数调用都有开销——要保存现场、分配栈空间、传递参数、返回。递归调得深了，效率不如循环。而且递归层数太多会把栈撑爆。
所以我的建议是：学肯定要学，因为递归是理解“分治思想”的重要一环。写程序的时候，如果问题天生适合递归（比如处理树、文件夹结构这种），就用递归。如果循环能写清楚，优先用循环。
最后总结一下这节课的核心：
嵌套调用就是函数里面调别的函数，一层套一层，这个你一直在用，只是以前不知道它叫“嵌套”。
递归调用就是函数调自己，把大问题拆成同类型的小问题，一层层拆下去，拆到最简单的情况再一层层返回。
写递归必须记住两点：终止条件和递推公式。 缺了哪个都不行。
递归是很多复杂算法的基础，这个思维你得建立起来。现在不要求你把递归用得飞起，但你至少得理解它是什么、怎么执行的，后面学数据结构的时候你会跟它打无数次交道。
回去试试写一个递归版的阶乘，然后用printf把每一层调用和返回的结果打出来，亲眼看看它到底是怎么一层层钻进去又一层层返出来的。