资讯 / 正文
C语言递归从入门到吃透|7道必考真题逐行拆解(零基础可懂)
C语言递归从入门到吃透|7道必考真题逐行拆解(零基础可懂)#信安萌新笔记 很多同学学C语言,最难跨的坎就是递归。 看得懂概念、写不出代码、会抄不会改、一跑栈溢出、完全看不懂递归调用过程。 今天这篇文章,从「递归核心原理」→「两大必备条件」→「新手高频踩坑」→「7道从易到难必考真题」,带你彻底搞定C语言递归。 一、到底什么是递归? 递归:函数自己调用自己 本质逻辑就一句话: 把一个大问题,拆解成结构完全一样、规模更小的子问题,直到拆到可以直接出结果的终点。 递归永远只有两个部分: 1. 递归出口(基线条件):停止递归,直接返回值(没有它必死循环、栈溢出) 2. 递归递推(拆分条件):大事化小,自己调用自己 二、递归必须满足的两个条件(必考) 1. 有明确递归出口 必须存在一个确定条件,让函数停止调用自己、直接return。 没有出口 = 无限递归 = 程序崩溃栈溢出。 2. 每次递归问题规模必须缩小 每一次自我调用,处理的数据范围一定要变小,无限趋近出口。 三、递归3大致命坑 1. 没写递归出口 / 出口写错:直接死递归、栈溢出报错 2. 递归参数没有缩小:问题规模不变,永远到不了出口 3. 分不清递推、回溯:只懂往下拆,不懂回来赋值,算不出正确结果 四、全真例题7道 例题1:递归求 n的阶乘 题目要求 输入正整数n,用递归计算 n! = 1*2*3*...*n 规定: 0! = 1、1! = 1 #include <stdio.h> // 递归求阶乘 int fact(int n) { // 递归出口:0和1的阶乘都是1 if(n == 1 || n == 0) { return 1; } // 递归递推:n! = n * (n-1)! return n * fact(n - 1); } int main() { int n; scanf("%d", &n); printf("%d", fact(n)); return 0; } 递归完整拆解(以n=4举例) - fact(4) = 4 * fact(3) - fact(3) = 3 * fact(2) - fact(2) = 2 * fact(1) - fact(1) = 1(触发出口,停止递归) 回溯计算 fact(2)=21=2 fact(3)=32=6 fact(4)=4*6=24 核心总结 阶乘是最标准递归模型:先递推拆解,再回溯累积结果 例题2:递归求 1+2+3+...+n 累加和 题目要求 输入n,递归计算1到n的整数和 #include <stdio.h> int sum(int n) { // 递归出口:n=1时和为1 if(n == 1) { return 1; } // 递推:sum(n) = n + sum(n-1) return n + sum(n - 1); } int main() { int n; scanf("%d", &n); printf("%d", sum(n)); return 0; } 递归拆解(n=5) sum(5)=5+sum(4) sum(4)=4+sum(3) sum(3)=3+sum(2) sum(2)=2+sum(1) sum(1)=1 回溯:5+4+3+2+1=15 例题3:递归实现斐波那契数列(考试高频) 题目要求 斐波那契规则: F(1)=1,F(2)=1 F(n)=F(n-1)+F(n-2)(n≥3) 输入n,输出第n项斐波那契数 #include <stdio.h> int fib(int n) { // 双出口 if(n == 1 || n == 2) { return 1; } // 双向递归拆分 return fib(n-1) + fib(n-2); } int main() { int n; scanf("%d", &n); printf("%d", fib(n)); return 0; } 核心考点 这是双向递归经典模板,区别于前面的单向递归,是期末考试、PTA常考题。 例题4:递归反转输出整数 题目要求 输入一个整数,递归倒序输出每一位数字 例:输入1234 → 输出4321 #include <stdio.h> void reverse(int n) { // 负数处理 if(n < 0) { printf("-"); reverse(-n); return; } // 递归出口:个位数直接输出 if(n < 10) { printf("%d", n); return; } // 先递归后输出,实现倒序 reverse(n % 10); printf("%d", n / 10 % 10); } int main() { int n; scanf("%d", &n); reverse(n); return 0; } 关键逻辑 普通循环是先取数、先输出 递归是先递推到底、再逐层输出,利用回溯实现反转,是递归独有的思维。 例题5:递归求数组最大值 题目要求 给定数组,用递归查找数组中最大值 完整代码 #include <stdio.h> // a数组、当前下标、数组长度 int getMax(int a[], int i, int len) { // 递归出口:遍历到最后一个元素 if(i == len - 1) { return a[i]; } // 递归:当前元素 和 后续数组最大值 对比 int max = getMax(a, i+1, len); return a[i] > max ? a[i] : max; } int main() { int arr[5] = {12,45,7,89,23}; int max = getMax(arr, 0, 5); printf("最大值:%d", max); return 0; } 解题思路 把「整个数组找最大值」拆成: 第一个元素 VS 剩余所有元素的最大值,逐层拆分回溯比较。 例题6:递归跳台阶 题目题意 一只青蛙跳台阶,n级台阶,每次跳1级或2级,求总共有多少种跳法。 核心思路 - 最后一步跳1级:前面n-1级的跳法 - 最后一步跳2级:前面n-2级的跳法 总跳法 = f(n-1) + f(n-2) #include <stdio.h> int jump(int n) { if(n == 1) return 1; if(n == 2) return 2; return jump(n-1) + jump(n-2); } int main() { int n; scanf("%d", &n); printf("%d", jump(n)); return 0; } 重点总结 跳台阶本质变种斐波那契,是递归拆分思想的经典应用题。 例题7:汉诺塔递归(递归天花板、必考压轴) 游戏规则 1. 三根柱子A、B、C,n个从小到大盘子在A柱 2. 大盘永远不能压小盘 3. 借助中间柱B,把所有盘子从A全部移到C 递归核心三步 1. 将n-1个盘子:起始柱 → 借助中间柱 → 临时柱 2. 将最底下最大1个盘子:起始柱 → 目标柱 3. 将n-1个盘子:临时柱 → 借助起始柱 → 目标柱 #include <stdio.h> // n盘子、起始from、借助temp、目标to void hanoi(int n, char from, char temp, char to) { // 递归出口:只剩1个盘子,直接移动 if(n == 1) { printf("盘子1:%c → %c\n", from, to); return; } // 1. n-1个盘子 from移到temp,借助to hanoi(n-1, from, to, temp); // 2. 移动最底下大盘 printf("盘子%d:%c → %c\n", n, from, to); // 3. n-1个盘子 temp移到to,借助from hanoi(n-1, temp, from, to); } int main() { int n; scanf("%d", &n); hanoi(n, 'A', 'B', 'C'); return 0; } 为什么是递归天花板? 不需要手动模拟每一步! 递归只需要定义整体规则,机器自动完成千万次重复操作,完美体现递归“大事化小”的核心优势。 五、递归万能解题模板 1. 找出口:确定最小问题的结果(终止条件) 2. 找拆分:大问题 = 若干个小一号同结构子问题 3. 写递归式:根据拆分逻辑写return递归公式 4. 验证缩小:确认每次参数趋近出口 六、递归vs循环 - 循环:重复做同一件事,逻辑直观、占用栈少 - 递归:重复拆解同结构问题,代码极简、适合树形、分治、汉诺塔、数列问题 能用循环不一定能用递归,能用递归基本都能转循环,但递归代码更简洁、思维更高级。 七、新手递归学习建议 1. 先背熟:阶乘、累加、斐波那契三道基础模板 2. 手动画递归拆解图,看懂「递推+回溯」全过程 3. 所有错题优先排查:出口是否正确、参数是否缩小 4. 复杂题(汉诺塔、跳台阶)不要硬模拟,记递归逻辑 这7道题覆盖C语言递归入门、作业、考试、刷题全部场景,保存这一篇,彻底吃透递归! 欢迎留言讨论! #C语言#程序设计 #ai时代下的人们