一、递归是什么递归其实是一种解决问题的方法在C语言中递归就是函数自己调用自己。 下面我们看最简单的递归代码代码语言cAI代码解释#include stdio.h int main() { printf(hehe\n); main(); return 0; }运行后提示报错这里的代码会导致栈溢出虽然是个错误的代码但是能够很明确的表达出递归的意思在这里我们可以看出这个代码一直在执行打印操作体现了函数递归的现象但是由于死循环的打印导致了栈溢出的现象。递归的思想把⼀个大型复杂问题层层转化为⼀个与原问题相似但规模较小的子问题来求解直到子问题不能再被拆分递归就结束了。即就是把大事化小的过程。递归中的递就是递推的意思归就是回归的意思。1.1尾递归尾递归是指一个递归函数在调用自身时该递归调用是函数的最后一条语句。换句话说函数在调用自身之后不再执行任何操作而是直接返回递归调用的结果。这种特殊形式的递归称为尾递归。二、递归的限制条件递归在书写的时候有2个必要条件 ①递归存在限制条件当满足这个限制条件的时候递归便不再继续。 ②每次递归调用之后越来越接近这个限制条件。 在下面的例子中我们逐步体会这2个限制条件三、递归举例3.1举例一求n的阶乘⼀个正整数的阶乘factorial是所有小于及等于该数的正整数的积并且0的阶乘为1。 自然数n的阶乘写作n!。题目计算n的阶乘不考虑溢出n的阶乘就是1~n的数字累积相乘。分析和实现示例 我们知道n的阶乘的公式 n n ∗ (n − 1)! 举例说明 5 1 * 2 * 3 * 4 * 5 4 1 * 2 * 3 * 4即 5就等4* 5。 当 n0 的时候n的阶乘是1其余n的阶乘都是可以通过公式计算。如图所示实现代码如下代码语言cAI代码解释#include stdio.h int Fact(int n) { if(n0) return 1; else return n*Fact(n-1); } int main() { int n 0; scanf(%d, n); int ret Fact(n); printf(%d\n, ret); return 0; }运行结果当然这里不考虑n太大的情况n太大存在栈溢出的现象如图下面我们画图推演3.2举例二顺序打印一个整数的每一位题目输入⼀个整数m按照顺序打印整数的每⼀位。 比如 输入1234 输出1 2 3 4 输入520 输出5 2 0分析和实现示例 怎么得到这个数的每⼀位呢 如果n是⼀位数n的每⼀位就是n自己。 n是超过1位数的话就得拆分每⼀位1234%10就能得到4然后1234/10得到123这就相当于去掉了4然后继续对123%10就得到了3再除10去掉3以此类推不断的%10 和 /10 操作直到得到1234的每一位。想到这里我们便有了思路 把Print(1234) 打印1234每⼀位拆解为首先Print(123)打印123的每⼀位再打印得到的4。 把Print(123) 打印123每⼀位拆解为首先Print(12)打印12的每⼀位再打印得到的3。 直到Print打印的是⼀位数直接打印就行。代码实现如下代码语言cAI代码解释void Print(int n) { if(n9) { Print(n/10); } printf(%d , n%10); } int main() { int m 0; scanf(%d, m); Print(m); return 0; }运行结果如图画图推演四、递归与迭代递归是⼀种很好的编程技巧但是和很多技巧⼀样也是可能被误用的就像举例1一样看到推导的公式很容易就被写成递归的形式代码语言cAI代码解释int Fact(int n) { if(n0) return 1; else return n*Fact(n-1); }Fact函数是可以产生正确的结果但是在递归函数调用的过程中涉及⼀些运行时的开销。 在C语言中每⼀次函数调用都要需要为本次函数调用在栈区申请⼀块内存空间来保存函数调用期间的各种局部变量的值这块空间被称为运行时堆栈或者函数栈帧。 函数不返回函数对应的栈帧空间就⼀直占用所以如果函数调用中存在递归调用的话每⼀次递归函数调用都会开辟属于自己的栈帧空间直到函数递归不再继续开始回归才逐层释放栈帧空间。所以如果采用函数递归的方式完成代码递归层次太深就会浪费太多的栈帧空间也可能引起栈溢出stackoverflow的问题。所以如果不想使用递归就得想其他的办法通常就是迭代的方式通常就是循环的方式。 比如计算n的阶乘也是可以产生1~n的数字累计乘在⼀起的。代码语言cAI代码解释int Fact(int n) { int i 0; int ret 1; for(i1; in; i) { ret * i; } return ret; }上述代码是能够完成任务并且效率是比递归的方式更好的。4.1举例三求第n个斐波那契数计算第n个斐波那契数是不适合使用递归求解的但是斐波那契 数的问题通过是使用递归的形式描述的如下看到上图我们就会想到用递归的形式去做如下代码代码语言cAI代码解释#include stdio.h int Fib(int n) { if(n2) return 1; else return Fib(n-1)Fib(n-2); } int main() { int n 0; scanf(%d, n); int ret Fib(n); printf(%d\n, ret); return 0; }当我们n输⼊为50的时候需要很⻓时间才能算出结果这个计算所花费的时间是我们很难接受的这也说明递归的写法是非常低效的那是为什么呢其实递归程序会不断的展开在展开的过程中我们很容易就能发现在递归的过程中会有重复计算而且递归层次越深冗余计算就会越多。我们可以一个测试代码语言cAI代码解释#include stdio.h int count 0; int Fib(int n) { if(n 3) count;//统计第3个斐波那契数被计算的次数 if(n2) return 1; else return Fib(n-1)Fib(n-2); } int main() { int n 0; scanf(%d, n); int ret Fib(n); printf(%d\n, ret); printf(\ncount %d\n, count); return 0; }如图所示计算第40个斐波那契数时需要计算 39088169次可想而知这种方法是冗杂的那这种问题就不适合用递归的方式来来解决问题接下来我们使用迭代的方式来解决这个问题。我们知道斐波那契数的前2个数都1然后前2个数相加就是第3个数那么我们从前往后从小到大计算就行了。 代码如下代码语言cAI代码解释int Fib(int n) { int a 1; int b 1; int c 1; while(n2) { c ab; a b; b c; n--; } return c; }迭代的方式去实现这个代码效率就要高出很多了。五、拓展学习青蛙跳台问题问题有一只青蛙一次可以跳1个台阶一次也可以跳2个台阶问如果跳到第n个台阶有多少种跳法 分析与实现问题 这只青蛙第一次条有两种跳法 ①跳一个台阶剩余n-1个台阶 ②跳两个台阶剩余n-2个台阶 不难发现这是一个斐波那契数列即用以下方法代码语言cAI代码解释#define _CRT_SECURE_NO_WARNINGS 1 #includestdio.h int Jump(int n) { if (n 2) return n; else return Jump(n - 1) Jump(n - 2); } int main() { int x 0; scanf(%d, x); int ret Jump(x); printf(func(%d)%d\n, x, ret); return 0; }