【C语言程序设计】第27篇：递归函数原理与实例分析

1 引言考虑计算阶乘的问题n! n × (n-1) × ... × 2 × 1。我们可以用循环实现cint factorial(int n) { int result 1; for (int i 1; i n; i) { result * i; } return result; }但也可以换一种思路n! n × (n-1)!即阶乘可以用自身来定义。这种“自己定义自己”的方式就是递归。cint factorial(int n) { if (n 1) return 1; /* 基本情况 */ return n * factorial(n - 1); /* 递归调用 */ }这段代码简洁优雅但它背后发生了什么为什么函数可以调用自己这就是本章要探讨的问题。2 递归的数学基础数学归纳法2.1 数学归纳法简介数学归纳法Mathematical Induction是证明与自然数有关的命题的一种方法包含两个步骤基础步骤证明命题对最小的自然数通常是1或0成立归纳步骤假设命题对某个自然数k成立证明它对k1也成立2.2 递归与归纳法的对应关系递归函数的设计思想与数学归纳法惊人地一致数学归纳法递归函数证明基础情况成立定义基本情况递归终止条件假设命题对k成立假设递归调用能解决规模更小的子问题证明命题对k1成立利用子问题的解构造原问题的解c/* 阶乘的递归实现与数学归纳法的对应 */ int factorial(int n) { /* 基础步骤证明 n1 时成立 */ if (n 1) return 1; /* 归纳步骤假设 factorial(n-1) 正确 那么 factorial(n) n * factorial(n-1) 也正确 */ return n * factorial(n - 1); }这种对应关系不是巧合——递归的本质就是用数学归纳法的思想来设计算法。当我们写递归函数时实际上是在做两件事写出临界条件基础情况找这一次和上一次的关系归纳步骤2.3 用数学归纳法理解递归的正确性以阶乘为例我们可以用归纳法证明递归函数正确n1时函数返回1正确假设函数对n-1正确即factorial(n-1)返回(n-1)!那么对n函数返回n * factorial(n-1) n × (n-1)! n!正确重要写递归函数时不要试图跟踪每一层调用的细节而应该相信递归调用能正确解决规模更小的子问题。这正是数学归纳法的核心思想。3 递归的栈实现3.1 函数调用的底层机制在计算机底层函数调用是通过栈来实现的。当一个函数调用另一个函数时将实参、返回地址等信息压栈为被调函数的局部变量分配空间将控制转移到被调函数当被调函数返回时保存返回值释放局部变量空间根据返回地址跳回调用函数3.2 递归调用时的栈帧变化递归调用本质上就是同一个函数的多次嵌套调用每次调用都会在栈上创建一个新的栈帧Stack Frame。以计算factorial(3)为例栈的变化过程text/* 调用序列 */ factorial(3) → factorial(2) → factorial(1) → 返回1 ← 返回 2*1 2 ← 返回 3*2 6栈帧变化示意图text调用 factorial(3) 时 栈顶 → [factorial(3)的栈帧] ← n3, 等待递归返回 调用 factorial(2) 时 栈顶 → [factorial(2)的栈帧] ← n2 [factorial(3)的栈帧] 调用 factorial(1) 时 栈顶 → [factorial(1)的栈帧] ← n1满足终止条件直接返回 [factorial(2)的栈帧] [factorial(3)的栈帧] factorial(1) 返回后 栈顶 → [factorial(2)的栈帧] ← 收到返回值1计算2*12后返回 [factorial(3)的栈帧] factorial(2) 返回后 栈顶 → [factorial(3)的栈帧] ← 收到返回值2计算3*26后返回 factorial(3) 返回后栈空3.3 递归深度与栈溢出每次递归调用都会消耗栈空间来存储局部变量和返回地址。如果递归层次太深可能导致栈溢出Stack Overflow。c/* 危险递归深度过大 */ void infinite_recursion(int n) { int large_array[1000]; /* 每个栈帧4KB */ infinite_recursion(n 1); /* 无限递归 */ }在常见的系统中栈大小通常只有几MB。因此当递归深度达到数千层时程序就可能崩溃。4 递归 vs 迭代以阶乘为例4.1 阶乘的递归实现c#include stdio.h /* 递归版阶乘 */ long factorial_recursive(int n) { if (n 1) return 1; /* 基本情况 */ return n * factorial_recursive(n - 1); /* 递归调用 */ }4.2 阶乘的迭代实现c/* 迭代版阶乘 */ long factorial_iterative(int n) { long result 1; for (int i 2; i n; i) { result * i; } return result; }4.3 对比分析对比维度递归版迭代版代码简洁性简洁直接对应数学定义略复杂可读性高易于理解算法思想需要理解循环逻辑执行效率较低函数调用开销高无额外开销内存占用O(n) 栈空间O(1) 额外空间适用场景n较小追求代码清晰n较大追求性能测试对比c#include stdio.h #include time.h int main(void) { int n 20; clock_t start, end; start clock(); long r1 factorial_recursive(n); end clock(); printf(递归结果%ld时间%ldms\n, r1, end - start); start clock(); long r2 factorial_iterative(n); end clock(); printf(迭代结果%ld时间%ldms\n, r2, end - start); return 0; }当 n 较小时两者差异不大但当 n 增大时递归的额外开销会变得明显。5 斐波那契数列递归的陷阱5.1 斐波那契数列的定义斐波那契数列Fibonacci sequence定义为F(1) 1F(2) 1F(n) F(n-1) F(n-2) n ≥ 35.2 递归实现c#include stdio.h /* 递归版斐波那契 */ long fibonacci_recursive(int n) { if (n 2) return 1; /* 基本情况 */ return fibonacci_recursive(n - 1) fibonacci_recursive(n - 2); /* 递归调用 */ }这段代码直接对应数学定义简洁优美。但是……它存在严重的问题。5.3 递归调用的爆炸性增长让我们分析一下fibonacci_recursive(5)的调用过程textfibonacci(5) ├── fibonacci(4) │ ├── fibonacci(3) │ │ ├── fibonacci(2) │ │ └── fibonacci(1) │ └── fibonacci(2) └── fibonacci(3) ├── fibonacci(2) └── fibonacci(1)调用次数统计fibonacci(5) 调用 fibonacci(3) 2次fibonacci(5) 调用 fibonacci(2) 3次总调用次数15次而 n5 只需要计算5个数更惊人的是这个数字增长极快n10 时fibonacci(3) 被调用 21 次n20 时fibonacci(3) 被调用 2584 次n30 时fibonacci(3) 被调用 317811 次5.4 为什么会有如此多的重复计算原因是递归树中包含了大量重复的子问题。每个fibonacci(k)被多次重复计算导致时间复杂度高达O(2ⁿ)——指数级爆炸。5.5 迭代实现c/* 迭代版斐波那契 */ long fibonacci_iterative(int n) { if (n 2) return 1; long a 1, b 1, c; for (int i 3; i n; i) { c a b; a b; b c; } return b; }时间复杂度O(n)空间复杂度O(1)。5.6 性能对比n递归版调用次数迭代版循环次数10约 177 次8 次20约 21891 次18 次30约 2692537 次28 次40约 3.3 亿次38 次50约 400 亿次48 次结论对于斐波那契数列递归实现是灾难性的绝对不应用在实际代码中。6 递归与迭代的综合对比对比维度递归迭代代码简洁性通常更简洁直接对应数学定义需要额外的循环控制变量可读性问题分解清晰需要理解循环逻辑执行效率有函数调用开销高效内存占用可能占用大量栈空间通常 O(1)适用范围树形结构、分治算法线性处理、简单循环重复计算可能重复计算子问题通常不会尾递归优化某些编译器支持优化不适用6.1 什么时候用递归问题天然具有递归结构如树的遍历、汉诺塔代码可读性优先于性能问题规模较小递归深度可控分治算法如快速排序、归并排序6.2 什么时候用迭代性能要求高递归深度可能很大如超过 1000 层存在大量重复计算如斐波那契内存受限的环境如嵌入式系统7 如何写好递归函数7.1 递归函数的三要素明确函数功能清楚定义函数要做什么确定基本情况找到递归的终止条件找到递推关系将原问题分解为子问题7.2 设计步骤以计算数组元素之和为例c/* 问题计算数组 arr[0..n-1] 的和 */ /* 1. 明确功能sum(arr, n) 返回数组前n个元素的和 */ int sum(int arr[], int n) { /* 2. 基本情况空数组和为0 */ if (n 0) return 0; /* 3. 递推关系sum(arr, n) sum(arr, n-1) arr[n-1] */ return sum(arr, n - 1) arr[n - 1]; }7.3 尾递归优化尾递归Tail Recursion是指递归调用是函数的最后一步操作。某些编译器可以对尾递归进行优化将其转换为迭代从而避免栈溢出。c/* 普通递归不是尾递归 */ int factorial(int n) { if (n 1) return 1; return n * factorial(n - 1); /* 最后一步是乘法不是递归调用 */ } /* 尾递归版本 */ int factorial_tail(int n, int accumulator) { if (n 1) return accumulator; return factorial_tail(n - 1, n * accumulator); /* 最后一步是递归调用 */ } /* 包装函数 */ int factorial(int n) { return factorial_tail(n, 1); }尾递归的好处编译器可以复用当前栈帧不需要为每次调用创建新栈帧。8 常见错误与注意事项8.1 忘记基本情况c/* 错误没有终止条件 */ int bad_recursion(int n) { return n * bad_recursion(n - 1); /* 无限递归栈溢出 */ }8.2 基本情况永远不会到达c/* 错误n 永远不等于 1 */ int wrong_recursion(int n) { if (n 1) return 1; /* 如果初始 n 1这个条件永远不会满足 */ return n * wrong_recursion(n - 2); /* n5 → 3 → 1 ✓但 n4 → 2 → 0 → -2 ... ✗ */ }8.3 递归深度过大c/* 危险递归深度 n当 n100000 时必然栈溢出 */ int sum(int n) { if (n 0) return 0; return n sum(n - 1); }8.4 重复计算子问题如前面斐波那契的例子应该避免这种指数级爆炸。9 综合示例汉诺塔汉诺塔是递归的经典案例c#include stdio.h /* 将 n 个盘子从 A 移到 C借助 B */ void hanoi(int n, char A, char B, char C) { if (n 1) { printf(将盘子从 %c 移到 %c\n, A, C); return; } /* 1. 将上面 n-1 个盘子从 A 移到 B借助 C */ hanoi(n - 1, A, C, B); /* 2. 将最大的盘子从 A 移到 C */ printf(将盘子从 %c 移到 %c\n, A, C); /* 3. 将 B 上的 n-1 个盘子移到 C借助 A */ hanoi(n - 1, B, A, C); } int main(void) { int n 3; printf(移动 %d 个盘子的步骤\n, n); hanoi(n, A, B, C); return 0; }这个问题的递归解法直接对应问题的自然分解如果用迭代实现会复杂得多。10 本章小结本章系统介绍了递归函数的原理与应用1. 递归的数学基础递归与数学归纳法一脉相承基础情况对应归纳基础递归调用对应归纳假设2. 递归的栈实现每次递归调用创建新的栈帧递归深度过大导致栈溢出3. 递归 vs 迭代阶乘递归简洁迭代高效两者均可斐波那契递归有大量重复计算绝对应该用迭代4. 递归的适用场景✅ 树形结构遍历✅ 分治算法✅ 问题天然有递归定义❌ 线性问题、深度很大、有重复子问题5. 写好递归的要点明确功能确定基本情况找到递推关系相信递归调用不要跟踪细节