资讯 / 正文

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时代下的人们

← 返回资讯列表