递归函数详解

递归函数详解——用递归改写谭浩强《C 程序设计》经典例题📚 基于谭浩强《C 程序设计》经典例题💡 一套代码看懂递归的本质与应用🎯 适合 C 语言进阶学习者📋 目录1. 递归函数入门基础2. 递归的三要素3. 经典例题递归改写4. 递归进阶应用[5. 递归 vs 迭代对比](#5-递归 vs 迭代对比)6. 递归的优缺点分析7. 实战练习题8. 常见问题解答1. 递归函数入门基础1.1 什么是递归？递归（Recursion）是指函数在定义中调用自身的过程。简单来说，就是"函数自己调用自己"。递归的核心思想：将复杂问题分解为规模更小但结构相似的子问题。1.2 递归的形象理解递归就像俄罗斯套娃 🪆 ┌─────────────────────────────┐ │ 大娃娃 (原问题) │ │ ┌─────────────────────┐ │ │ │ 中娃娃 (子问题 1) │ │ │ │ ┌─────────────┐ │ │ │ │ │ 小娃娃 │ │ │ │ │ │ (子问题 2) │ │ │ │ │ │ ┌─────┐ │ │ │ │ │ │ │最小娃│ │ │ │ │ │ │ │(基准)│ │ │ │ │ │ │ └─────┘ │ │ │ │ │ └─────────────┘ │ │ │ └─────────────────────┘ │ └─────────────────────────────┘ 打开过程：递归调用（递推） 合上过程：返回结果（回归）1.3 递归的执行过程以 factorial(4) 为例： 调用阶段（递推） 返回阶段（回归） fact(4) fact(4) = 4 × 24 = 96 │ ▲ ├─ 4 × fact(3) │ │ │ │ │ ├─ 3 × fact(2) │ │ │ │ │ │ │ ├─ 2 × fact(1) │ │ │ │ │ │ │ │ │ └─ 1 × fact(0) │ │ │ │ │ │ │ │ │ └─ 1 │ │ │ │ │ │ │ └─ 2 × 1 = 2 │ │ │ │ │ └─ 3 × 2 = 6 │ │ │ └─────────────────────────────────┘2. 递归的三要素任何一个递归函数都必须具备三个要素，缺一不可！要素 1：基准情形（Base Case）递归必须有终止条件，否则会造成无限递归，导致栈溢出。if(n==0)// 基准情形return1;要素 2：递归调用（Recursive Call）函数在定义中调用自身，每次调用都向基准情形靠近。returnn*factorial(n-1);// 递归调用要素 3：状态变化（State Change）每次递归调用时，问题规模必须减小。factorial(n)→factorial(n-1)→factorial(n-2)→...→factorial(0)↓ 规模减小完整示例intfactorial(intn){// 要素 1：基准情形if(n==0)return1;// 要素 2 + 3：递归调用 + 状态变化returnn*factorial(n-1);}3. 经典例题递归改写本章将谭浩强《C 程序设计》中的经典例题用递归方式重新实现，并与原迭代版本对比。3.1 例题 1：计算阶乘原题：求 n 的阶乘 n!🔁 迭代版本（原教材）longfactorial_iterative(intn){longresult=1;for(inti=1;i=n;i++){result*=i;}returnresult;}🔄 递归版本（改写）longfactorial_recursive(intn){// 基准情形：0! = 1, 1! = 1if(n==0||n==1)return1;// 递归调用：n! = n × (n-1)!returnn*factorial_recursive(n-1);}📊 执行过程图解factorial_recursive(4) 第 1 层：4 * factorial_recursive(3) ↓ 第 2 层： 3 * factorial_recursive(2) ↓ 第 3 层： 2 * factorial_recursive(1) ↓ 第 4 层： 1 ← 基准情形 返回： 第 4 层返回 1 第 3 层返回 2 * 1 = 2 第 2 层返回 3 * 2 = 6 第 1 层返回 4 * 6 = 24 最终结果：24🧪 完整测试代码#includestdio.hlongfactorial_recursive(intn){if(n0){printf("错误：负数没有阶乘\n");return-1;}if(n==0||n==1)return1;returnn*factorial_recursive(n-1);}intmain(){printf("=== 阶乘计算（递归版）===\n\n");for(inti=0;i=10;i++){printf("%d! = %ld\n",i,factorial_recursive(i));}return0;}输出结果：=== 阶乘计算（递归版）=== 0! = 1 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 362880 10! = 36288003.2 例题 2：斐波那契数列原题：求斐波那契数列的第 n 项数列：1, 1, 2, 3, 5, 8, 13, 21, 34…规律：F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2) (n≥3)🔁 迭代版本（原教材）intfibonacci_iterative(intn){if(n=2)return1;inta=1,b=1,c;for(inti=3;i=n;i++){c=a+b;a=b;b=c;}returnc;}🔄 递归版本（改写）intfibonacci_recursive(intn){// 基准情形：F(1) = 1, F(2) = 1if(n=2)return1;// 递归调用：F(n) = F(n-1) + F(n-2)returnfibonacci_recursive(n-1)+fibonacci_recursive(n-2);}📊 递归树展开fibonacci_recursive(5) ├── fibonacci_recursive(4) │ ├── fibonacci_recursive(3) │ │ ├── fibonacci_recursive(2) = 1 │ │ └── fibonacci_recursive(1) = 1 │ └── fibonacci_recursive(2) = 1 └── fibonacci_recursive(3) ├── fibonacci_recursive(2) = 1 └── fibonacci_recursive(1) = 1 结果：5 + 3 = 8🧪 完整测试代码#includestdio.hintfibonacci_recursive(intn){if(n=0){printf("错误：n 必须为正整数\n");return-1;}if(n=2)return1;returnfibonacci_recursive(n-1)+fibonacci_recursive(n-2);}intmain(){printf("=== 斐波那契数列（递归版）===\n\n");printf("前 15 项：");for(inti=1;i=15;i++){printf("%d ",fibonacci_recursive(i));}printf("\n\n");printf("第 10 项：%d\n",fibonacci_recursive(10));printf("第 15 项：%d\n",fibonacci_recursive(15));return0;}输出结果：=== 斐波那契数列（递归版）=== 前 15 项：1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 第 10 项：55 第 15 项：610⚠️注意：递归版斐波那契存在大量重复计算，效率较低。实际应用中建议使用迭代版或记忆化递归。3.3 例题 3：汉诺塔问题原题：将 n 个盘子从 A 柱移到 C 柱，每次只能移动一个盘子，大盘子不能放在小盘子上面。🔁 迭代版本（原教材：较复杂，需要栈模拟）// 迭代版本非常复杂，这里略过// 需要使用栈来模拟递归过程🔄 递归版本（改写：简洁优雅）#includestdio.hintmove_count=0;// 记录移动次数/** * 汉诺塔递归函数 * n: 盘子数量 * from: 起始柱 * to: 目标柱 * aux: 辅助柱 */voidhanoi(intn,charfrom,charto,charaux){// 基准情形：只有一个盘子if(n==1){move_count++;printf("第%d步：%c → %c\n",move_count,from,to);return;}// 递归步骤：// 1. 将 n-1 个盘子从 from 移到 aux（借助 to）hanoi(n-1,from,aux,to);// 2. 将第 n 个盘子从 from 移到 tomove_count++;printf("第%d步：%c → %c\n",move_count,from,to);// 3. 将 n-1 个盘子从 aux 移到 to（借助 from）hanoi(n-1,aux,to,from);}intmain(){intn;printf("=== 汉诺塔问题（递归版）===\n\n");printf("请输入盘子数量：");scanf("%d",n);printf("\n移动步骤：\n");move_count=0;hanoi(n,'A','C','B');printf("\n总共需要 %d 步\n",move_count);printf("理论最少步数：%d\n",(1n)-1);// 2^n - 1return0;}📊 3 个盘子的执行过程hanoi(3, A, C, B) │ ├─ hanoi(2, A, B, C) │ │ │ ├─ hanoi(1, A, C, B) → A → C │ │ │ └─ A → B │ │ │ └─ hanoi(1, C, B, A) → C → B │ └─ A → C │ └─ hanoi(2, B, C, A) │ ├─ hanoi(1, B, A, C) → B → A │ └─ B → C │ └─ hanoi(1, A, C, B) → A → C 最终步骤： 第 1 步：A → C 第 2 步：A → B 第 3 步：C → B 第 4 步：A → C 第 5 步：B → A 第 6 步：B → C 第 7 步：A → C🧪 运行示例=== 汉诺塔问题（递归版）=== 请输入盘子数量：3 移动步骤： 第 1 步：A → C 第 2 步：A → B 第 3 步：C → B 第 4 步：A → C 第 5 步：B → A 第 6 步：B → C 第 7 步：A → C 总共需要 7 步 理论最少步数：73.4 例题 4：求最大公约数（辗转相除法）原题：求两个正整数 m 和 n 的最大公约数🔁 迭代版本（原教材）intgcd_iterative(intm,intn){inttemp;while(n!=0){temp=m%n;m=n;n=temp;}returnm;}🔄 递归版本（改写）intgcd_recursive(intm,intn){// 基准情形：n 为 0 时，返回 mif(n==0)returnm;// 递归调用：g