函数递归知识文章目录函数递归知识一.什么是递归一递归的思想二递归的限制条件二.递归举例一举例1求n的阶乘1.分析和代码实现2.画图推演二举例2顺序打印一个整数的每一位1.分析和代码实现2.画图推演三.递归与迭代一递归的缺陷二举例求第n个斐波那契数1.递归方式2.迭代方式一.什么是递归递归其实是一种解决问题的方法在C语言中递归就是函数自己调用自己。最简单的C语言递归代码#includestdio.hintmain(){printf(hehe\n);main();//main函数中⼜调⽤了main函数return0;}上面的递归只是为了演示递归的基本形式代码最终也会陷入死递归导致栈溢出Stack overflow。一递归的思想递归就是递推回归的意思。把⼀个大型复杂问题层层转化为一个与原问题相似但规模较小的子问题来求解直到子问题不能再被拆分递归就结束了。所以递归的思考方式就是把大事化小的过程。二递归的限制条件递归在书写的时候有2个必要条件递归存在限制条件当满足这个限制条件的时候递归便不再继续。每次递归调用之后越来越接近这个限制条件。二.递归举例一举例1求n的阶乘一个正整数的阶乘factorial是所有小于及等于该数的正整数的积并且0的阶乘为1自然数n的阶乘写作 n!。题目计算n的阶乘不考虑溢出n的阶乘就是1~n的数字累积相乘。1.分析和代码实现n的阶乘的公式 n n * (n − 1)!n的阶乘和n-1的阶乘是相似的问题但是规模要少了n。有一种有特殊情况是当 n0 的时候n的阶乘是1而其余n的阶乘都是可以通过上面的公式计算。写出 n 的阶乘的递归公式如下假设Fact(n)就是求n的阶乘那么Fact(n-1)就是求n-1的阶乘函数如下intFact(intn){if(n0){return1;}else{returnn*Fact(n-1);}}运行测试不考虑n太大的情况n太大存在溢出2.画图推演该递归限制条件是n0每次递推n-1越来越接近这个限制条件当满足这个限制条件的时候递推便不再继续开始回归。二举例2顺序打印一个整数的每一位输入一个整数m按照顺序打印整数的每一位。比如输入1234 输出1 2 3 41.分析和代码实现关于这个题目首先想到的是怎么得到这个数的每一位。如果n是一位数就是n自己n超过1位数就得拆分每一位。1234%10就能得到4然后1234/10得到123这就相当于去掉了4 然后继续对123%10就得到了3再除10去掉3以此类推不断的 %10 和 /10 操作直到1234的每一位都得到。但是有个问题就是得到的数字顺序是倒着的。假设想写一个函数Print来打印n的每一位Print(1234)//打印1234的每⼀位其中1234中的4可以通过%10得到那么Print(1234)就可以拆分为两步Print(1234/10)//打印123的每一位printf(%d ,1234%10)//打印4Print(1234)打印1234每一位拆解为先Print(123)打印123的每一位再打印得到的4。Print(123)打印123每一位拆解为先Print(12)打印12的每一位再打印得到的3。直到Print打印的是一位数直接打印就行。函数如下voidPrint(size_tn)//打印n的每一位{if(n9){Print(n/10);}printf(%zu ,n%10);}运行测试2.画图推演该递归限制条件是n为个位数n9)每次递推n/10越来越接近这个限制条件当满足这个限制条件的时候递推便不再继续开始回归,逐个打印。三.递归与迭代一递归的缺陷递归是一种很好的编程技巧但是可能被误用就像举例1一样看到推导的公式很容易就被写成递归的形式intFact(intn){if(n0){return1;}else{returnn*Fact(n-1);}}Fact函数可以产生正确的结果但是在递归函数调用的过程中涉及一些运行时的开销。在C语言中每一次函数调用都需要在内存的栈区申请一块内存空间用于保存函数调用期间的各种局部变量的值这块空间被称为运行时堆栈或者函数栈帧。函数不返回函数对应的栈帧空间就一直占用所以如果函数调用中存在递归调用每一次递归函数调用都会开辟属于自己的栈帧空间直到函数递归不再继续开始回归才逐层释放栈帧空间。如果采用函数递归的方式完成代码递归层次太深就会浪费太多的栈帧空间也可能引起栈溢出stack overflow的问题。如果不想使用递归通常就是迭代循环的方式。例如计算 n 的阶乘可以产生1~n的数字累计乘在⼀起的。许多问题是以递归的形式进行解释的这只是因为它比非递归的形式更加清晰但是这些问题的迭代实现往往比递归实现效率更高。当一个问题非常复杂难以使用迭代的方式实现时此时递归实现的简洁性便可以补偿它所带来的运行时开销。二举例求第n个斐波那契数1.递归方式计算第n个斐波那契数是不适合使用递归求解的但是斐波那契数的问题通过是使用递归的形式描述的如下看到这公式很容易诱导我们将代码写成递归的形式intFib(intn){if(n2){return1;}else{returnFib(n-1)Fib(n-2);}}运行测试当n输入为50的时候需要很长时间才能算出结果这也说明递归的写法是非常低效的。原因递归程序会不断的展开在展开的过程中在递归的过程中会有重复计算而且递归层次越深冗余计算就会越多。代码测试在计算第30个斐波那契数的时候使用递归方式光是第3个斐波那契数就被重复计算了317811次这些计算是非常冗余的。2.迭代方式斐波那契数的前2个数都为1然后前2个数相加就是第3个数从前往后从小到大计算就行了。#includestdio.hintFib(intn){inta1,b1,c1;while(n2)//不知循环次数用while循环n2时不用计算直接返回1所以c初始化1{cab;ab;bc;n--;}returnc;}