首页 > 其他分享 >超详细明了的C语言函数递归,望周知。(包含求n的阶乘顺序打印⼀个整数的每⼀位求第n个斐波那契数递归代码详解)

超详细明了的C语言函数递归,望周知。(包含求n的阶乘顺序打印⼀个整数的每⼀位求第n个斐波那契数递归代码详解)

时间:2024-08-07 12:54:55浏览次数:16  
标签:1234 契数 递归 10 int Print 阶乘

1. 递归是什么?

递归是学习C语⾔函数绕不开的⼀个话题,那什么是递归呢? 递归其实是⼀种解决问题的⽅法,在C语⾔中,递归就是函数⾃⼰调⽤⾃⼰。 写⼀个史上最简单的C语⾔递归代码 #include <stdio.h> int main() { printf("hehe\n"); main(); //main函数中⼜调⽤了main函数 return 0; } 上述就是⼀个简单的递归程序,只不过上⾯的递归只是为了演⽰递归的基本形式,不是为了解决问题,代码最终也会陷⼊死递归,导致栈溢出(Stack overflow)。

1.1 递归的思想:

把⼀个⼤型复杂问题层层转化为⼀个与原问题相似,但规模较⼩的⼦问题来求解;直到⼦问题不能再 被拆分,递归就结束了。所以递归的思考⽅式就是把⼤事化⼩的过程。 递归中的递就是递推的意思,归就是回归的意思,接下来慢慢来体会。

1.2 递归的限制条件

递归在书写的时候,有2个必要条件: • 递归存在限制条件,当满⾜这个限制条件的时候,递归便不再继续。 • 每次递归调⽤之后越来越接近这个限制条件。 在下⾯的例⼦中,我们逐步体会这2个限制条件

2. 递归举例

递归代码及一定要包含递推部分跟回归部分。少了回归会导致栈溢出,而缺了递推部分则无法解决实际问题。

2.1 举例1:求n的阶乘

⼀个正整数的阶乘(factorial)是所有⼩于及等于该数的正整数的积,并且0的阶乘为1。 ⾃然数n的阶乘写作n!。 题⽬:计算n的阶乘(不考虑溢出),n的阶乘就是1~n的数字累积相乘。

2.1.1 分析和代码实现

我们知道n的阶乘的公式: n! =   n ∗ ( n − 1)! 举例: 5! = 5*4*3*2*1 4! = 4*3*2*1 所以:5! = 5*4! 这样的思路就是把⼀个较⼤的问题,转换为⼀个与原问题相似,但规模较⼩的问题来求解的 当 n==0 的时候,n的阶乘是1, 其余n的阶乘都是可以通过公式计算。 n的阶乘的递归公式如下 f0697292c3de4ad8934467934fc4ccd6.png 那我们就可以写出函数Fact求n的阶乘,假设Fact(n)就是求n的阶乘,那么Fact(n-1)就是求n-1的阶乘,函数如下: int Fact(int n) { if(n==0) return 1;                        //回归 else return n*Fact(n-1);       //递推 } 测试: #include <stdio.h> int Fact(int n) { if(n==0) 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太⼤存在溢出): 28e80e4ff57b46c3a5e77cc14dba4d80.png

2.1.2 画图推演

0e36f03c84274db08f1e925c81c1dfa6.png 每一次,递推都n--,越来越接近递推结束条件n=1。当n=1的时候开始回归从而算出结果。

2.2 举例2:顺序打印⼀个整数的每⼀位

输⼊⼀个整数m,打印这个按照顺序打印整数的每⼀位。 ⽐如: 输⼊:1234 输出:1 2 3 4 输⼊:520 输出:5 2 0

2.2.1 分析和代码实现

这个题⽬,放在我们⾯前,⾸先想到的是,怎么得到这个数的每⼀位呢? 如果n是⼀位数,n的每⼀位就是n⾃⼰ n是超过1位数的话,就得拆分每⼀位 1234%10就能得到4,然后1234/10得到123,这就相当于去掉了4 然后继续对123%10,就得到了3,再除10去掉3,以此类推 不断的 %10 和 /10 操作,直到1234的每⼀位都得到; 但是这⾥有个问题就是得到的数字顺序是倒着的 但是我们有了灵感,我们发现其实⼀个数字的最低位是最容易得到的,通过%10就能得到 那我们假设想写⼀个函数Print来打印n的每⼀位,如下表⽰: Print(n) 如果n是1234,那表⽰为Print(1234) // 打印 1234 的每⼀位 其中1234中的4可以通过%10得到,那么Print(1234)就可以拆分为两步: 1. Print(1234/10) // 打印 123 的每⼀位 2. printf(1234%10) // 打印 4 完成上述2步,那就完成了1234每⼀位的打印 那么Print(123)⼜可以拆分为Print(123/10) + printf(123%10) 以此类推下去,就有 Print(1234) ==>Print(123) + printf(4) ==>Print(12) + printf(3) ==>Print(1) + printf(2) ==>printf(1) 直到被打印的数字变成⼀位数的时候,就不需要再拆分,递归结束。 那么代码完成也就⽐较清楚: void Print(int n) {        if(n>9)   //回归     {         Print(n/10);            //递推    }    printf("%d ", n%10); } int main() { int m = 0; scanf("%d", &m); Print(m); return 0; } 029457f673e9449a81b8591e4268a700.png 在这个解题的过程中,我们就是使⽤了⼤事化⼩的思路 把Print(1234) 打印1234每⼀位,拆解为⾸先Print(123)打印123的每⼀位,再打印得到的4 把Print(123) 打印123每⼀位,拆解为⾸先Print(12)打印12的每⼀位,再打印得到的3直到Print打印的是⼀位数,直接打印就⾏。

2.2.2 画图推演

以1234每⼀位的打印来 85f1abe030ca49b8b00b4059caec476a.png

3. 递归与迭代

递归是⼀种很好的编程技巧,但是很多技巧⼀样,也是可能被误⽤的,就像举例1⼀样,看到推导的公 式,很容易就被写成递归的形式: 6f204af13e1444b2a5acc9885d39a245.png int Fact(int n) { if(n==0) return 1; else return n*Fact(n-1); } Fact函数是可以产⽣正确的结果,但是在递归函数调⽤的过程中涉及⼀些运⾏时的开销。 在C语⾔中每⼀次函数调⽤,都要需要为本次函数调⽤在栈区申请⼀块内存空间来保存函数调⽤期间 的各种局部变量的值,这块空间被称为运⾏时堆栈,或者函数栈帧。 函数不返回,函数对应的栈帧空间就⼀直占⽤,所以如果函数调⽤中存在递归调⽤的话,每⼀次递归 函数调⽤都会开辟属于⾃⼰的栈帧空间,直到函数递归不再继续,开始回归,才逐层释放栈帧空间。 所以如果采⽤函数递归的⽅式完成代码,递归层次太深,就会浪费太多的栈帧空间,也可能引起栈溢 出(stack overflow)的问题。 所以如果不想使⽤递归就得想其他的办法,通常就是迭代的⽅式(通常就是循环的⽅式)。 ⽐如:计算n的阶乘,也是可以产⽣1~n的数字累计乘在⼀起的。 int Fact(int n) { int i = 0; int ret = 1; for(i=1; i<=n; i++) { ret *= i; } return ret; } 上述代码是能够完成任务,并且效率是⽐递归的⽅式更好的。 事实上,我们看到的许多问题是以递归的形式进⾏解释的,这只是因为它⽐⾮递归的形式更加清晰, 但是这些问题的迭代实现往往⽐递归实现效率更⾼。 当⼀个问题⾮常复杂,难以使⽤迭代的⽅式实现时,此时递归实现的简洁性便可以补偿它所带来的运 ⾏时开销。

极端举例3:求第n个斐波那契数

我们也能举出更加极端的例⼦,就像计算第n个斐波那契数,是不适合使⽤递归求解的,但是斐波那契数的问题通过是使⽤递归的形式描述的,如下: f9ffc2ec64754e8b810db6d79b7e70df.png 看到这公式,很容易诱导我们将代码写成递归的形式,如下所⽰: int Fib(int n) { if(n<=2) return 1; else return Fib(n-1)+Fib(n-2); } 测试代码: #include <stdio.h> int main() { int n = 0; scanf("%d", &n); int ret = Fib(n); printf("%d\n", ret); return 0; ) 当我们n输⼊为50的时候,需要很⻓时间才能算出结果,这个计算所花费的时间,是我们很难接受的, 这也说明递归的写法是⾮常低效的,那是为什么呢? e07de947cbcc437f9c8b25c6e2f3fffc.png 其实递归程序会不断的展开,在展开的过程中,我们很容易就能发现,在递归的过程中会有重复计 算,⽽且递归层次越深,冗余计算就会越多。我们可以作业测试: #include <stdio.h> int count = 0; int Fib(int n) { if(n == 3) count++; //统计第3个斐波那契数被计算的次数 if(n<=2) 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; } a40eba895f614fa7911d5a47a90d42b4.png 这⾥我们看到了,在计算第40个斐波那契数的时候,使⽤递归⽅式,第3个斐波那契数就被重复计算了 39088169次,这些计算是⾮常冗余的。所以斐波那契数的计算,使⽤递归是⾮常不明智的,我们就得 想迭代的⽅式解决。 我们知道斐波那契数的前2个数都1,然后前2个数相加就是第3个数,那么我们从前往后,从⼩到⼤计算就⾏了。 这样就有下⾯的代码: int Fib(int n) { int a = 1; int b = 1; int c = 1; while(n>2) { c = a+b; a = b; b = c; n--; } return c; } 迭代的⽅式去实现这个代码,效率就要⾼出很多了。 有时候,递归虽好,但是也会引⼊⼀些问题,所以我们⼀定不要迷恋递归,适可⽽⽌就好。

标签:1234,契数,递归,10,int,Print,阶乘
From: https://blog.csdn.net/zzz87/article/details/140952848

相关文章

  • 二叉树递归解决问题刷题 (一)
    遇到和深度相关的题目,可以用dfs递归遍历深度获取bfs结果来做513.找树左下角的值如何找二叉树最底层最左边节点的值呢,就是dfs遍历深度,来获取,最后一层的第一个元素就是。classSolution:def__init__(self):#记录二叉树的最大深度self.maxDepth=......
  • C语言day11(string函数族、递归函数、结构体、共用体、枚举)
    【1】string函数族1.strlen头文件:#include<string.h>格式:size_tstrlen(constchar*s);功能:计算字符串实际长度,不包括\0参数:s:目标字符串首地址返回值:字符串实际长度2.strcpy    头文件:#include<string.h>    格式:char*strcpy(char*dest,......
  • c++递归
    这是我发的第一篇讲解类型的文章主要是报的班那边讲到了个很有趣的东西到时候会给些案例本期直接把花絮挂在最后面_____________________________________________________________________________c++里有两种函数一种是可以看成数据的(这种定义函数的类型有longlong,......
  • 快速幂的模板和维持动态变化中的最大值最小值,以及常见递归
      快速幂和大根堆小根堆都是一些需要记忆的东西,方便后面在题目中实现应用。图中的最短路径两个常用算法:  prim算法:通过小根堆来实现的,小根堆的作用是用来时刻维持状态的最小值。kruskal算法:核心手段(并查集)然后一开始是打算学习01bfs的,发现对于递归的过程确实还是理......
  • C++递归找规律典型题:派蒙的问题
    题目描述:有一天,旅行者和派蒙来到了一个未知的世界。这个世界充满了奇幻的景色和令人迷失的迷宫。他们决定一起探索这个神秘的地方,希望寻找宝藏和解开谜题。当他们穿越迷宫的时候,他们突然来到了一个巨大的房间。房间的中央有一个巨大的石头柱子,上面镶嵌着奇怪的符号和图案,上面......
  • c++递归算法较难题:分解数字
    题目描述:输入自然数 n,然后将其分拆成由若干数相加的形式,参与加法运算的数可以重复,要求输出降序排列。输入描述:一个待拆分的自然数n,(n≤50) 。输出描述:若干个拆分的加法等式。样例输入:5样例输出:5=55=4+15=3+25=3+1+15=2+2+15=2+1+1+15=1+1+1+1+1题目思想:将要分......
  • 「Day 1—递归问题」
    递归问题定义简洁来说就是一个函数不断调用自身的一个过程。习题汉诺塔问题思路对于这个经典的问题,我们考虑了使用递归的做法,由于盘子是在三个底座上来回辗转的,所以我们要确定起始座,辅助座,和目标座。我们专注于最下面的最大的那个盘子,先将盘子都放到辅助座上,等到只剩最大的,......
  • RAPTOR:索引树状RAG和递归推理检索系统
    RAPTOR论文和源码论文:https://arxiv.org/pdf/2401.18059代码:https://github.com/parthsarthi03/raptorRAPTOR(RECURSIVEABSTRACTIVEPROCESSINGFORTREE-ORGANIZEDRETRIEVAL),如这一论文标题中所述,这一方法是把文档按照树状结构进行索引组织,再使用递归推理来进行检索。RAP......
  • 如何为可以在递归调用中重新分配的 python 函数制定类型提示?
    采取以下最小示例:S=TypeVar("S",bound=int|str)defmeth(a:S)->S:ifa=="5":returnstr(meth(int(a)))returna特别是,上面的方法可以采用字符串或整数。它总是返回与其输入相同类型的值,但它可以递归地调用自身,在这种情况下,S的值......
  • 探秘斐波那契数列:如何在0.02毫秒内计算21亿
    针对斐波那契数列算法进行详细介绍和优化,从最简单的递归方法到更高效的迭代、缓存、动态规划、公式推导和矩阵解法,最终达到了时间复杂度为O(logn)的快速幂矩阵解法来感受算法的神奇之处,最后可以看到如何实现在输入n=2100000000(21亿)时仅耗时0.02毫秒的最佳效果。一、回顾斐波......