文章目录1. 什么是递归1.1 最简单的递归演示1.2 递归的思想1.3 递归的限制条件2. 递归举例2.1 举例1求n的阶乘2.2 举例2顺序打印一个整数的每一位3. 递归与迭代3.1 递归的优缺点3.2 迭代的优势3.3 举例3求第n个斐波那契数递归vs迭代3.4 递归的适用场景4. 拓展学习1. 什么是递归递归是C语言函数学习中的重要话题本质是一种解决问题的方法在C语言中表现为函数自己调用自己。1.1 最简单的递归演示以下代码演示了递归的基本形式但未设置终止条件会陷入死递归并导致栈溢出Stack overflow#includestdio.hintmain(){printf(hehe\n);main();// main函数中调用自身return0;}运行结果1.2 递归的思想递归的核心思想是大事化小将一个大型复杂问题层层拆分为与原问题相似但规模更小的子问题直到子问题无法再拆分递归终止最后通过子问题的解逐步推导原问题的解。“递”指递推拆分问题“归”指回归合并结果。1.3 递归的限制条件书写递归代码必须满足两个必要条件否则会导致死递归存在限制条件当满足该条件时递归停止每次递归调用后问题规模越来越接近限制条件。2. 递归举例2.1 举例1求n的阶乘正整数n的阶乘n!是所有小于等于n的正整数的乘积0的阶乘为1公式为n ! n × ( n − 1 ) × ( n − 2 ) × . . . × 1 n! n \times (n-1) \times (n-2) \times ... \times 1n!n×(n−1)×(n−2)×...×1通过推导可将问题拆分n ! n × ( n − 1 ) ! n! n \times (n-1)!n!n×(n−1)!有⼀种有特殊情况是当n0的时候n!是1其余n!都可以通过上面的公式计算。这样就能写出n!的递归公式如下F a c t ( n ) { 1 ( n 0 ) n × F a c t ( n − 1 ) ( n 0 ) Fact(n) \begin{cases} 1 (n0) \\ n \times Fact(n-1) (n0) \end{cases}Fact(n){1n×Fact(n−1)​(n0)(n0)​完整代码#includestdio.hintFact(intn){if(n0)return1;// 递归终止条件elsereturnn*Fact(n-1);// 递推调用自身解决更小问题}intmain(){intn0;scanf(%d,n);intretFact(n);printf(%d\n,ret);return0;}运行结果不考虑n太大溢出的情况5 120画图推演以n5为例2.2 举例2顺序打印一个整数的每一位输入一个整数m按顺序打印其每一位如输入1234输出1 2 3 4输入520输出5 2 0。核心思路通过n%10可获取最低位但顺序颠倒递归拆分先打印n的前n-1位Print(n/10)再打印最低位n%10限制条件n为个位数时n≤9直接打印。完整代码#includestdio.hvoidPrint(intn){if(n9)// 递归条件n不是个位数{Print(n/10);// 递推打印前n-1位}printf(%d ,n%10);// 回归打印当前最低位}intmain(){intm0;scanf(%d,m);Print(m);return0;}运行结果1234 1 2 3 4画图推演以n1234为例3. 递归与迭代3.1 递归的优缺点优点代码简洁逻辑清晰符合“大事化小”的思维习惯适合解决复杂问题如树/图遍历、分治算法迭代实现难度高。缺点每次递归调用需在栈区开辟函数栈帧保存局部变量、返回地址等存在运行时开销递归层次过深可能导致栈溢出Stack overflow部分场景存在大量冗余计算效率低下。3.2 迭代的优势迭代通常指循环无需函数调用开销不存在栈溢出风险多数场景下效率更高。对于可拆分的简单问题优先考虑迭代实现。3.3 举例3求第n个斐波那契数递归vs迭代斐波那契数定义第1、2个数为1从第3个数开始每个数等于前两个数之和公式为F i b ( n ) { 1 ( n 2 ) F i b ( n − 1 ) F i b ( n − 2 ) ( n 2 ) Fib(n) \begin{cases} 1 (n 2) \\ Fib(n-1) Fib(n-2) (n 2) \end{cases}Fib(n){1Fib(n−1)Fib(n−2)​(n2)(n2)​递归实现不推荐#includestdio.hintFib(intn){if(n2)return1;elsereturnFib(n-1)Fib(n-2);}intmain(){intn0;scanf(%d,n);intretFib(n);printf(%d\n,ret);return0;}问题存在大量冗余计算。例如当n输入为50的时候需要很长时间才能算出结果说明递归的写法是非常低效的。迭代实现推荐核心思路从前往后计算用变量保存前两个数逐步推导第n个数。#includestdio.hintFib(intn){inta1;// 第1个斐波那契数intb1;// 第2个斐波那契数intc1;// 存储第n个斐波那契数初始值适配n≤2while(n2)// 循环推导n2的情况{cab;ab;// 更新前两个数bc;n--;}returnc;}intmain(){intn0;scanf(%d,n);intretFib(n);printf(%d\n,ret);return0;}优势无冗余计算时间复杂度O(n)效率远超递归。3.4 递归的适用场景递归并非万能需根据场景选择优先使用迭代问题简单、可循环推导如阶乘、斐波那契数考虑使用递归问题复杂、迭代实现难度高如树遍历、汉诺塔、回溯算法。4. 拓展学习以下问题适合用递归解决可进一步练习青蛙跳台阶问题一只青蛙一次可跳1级或2级台阶求跳上n级台阶的总方式数汉诺塔问题将n个盘子从A柱移动到C柱中间可借助B柱每次只能移动1个盘子且大盘不能压小盘。