首页 > 其他分享 >【C语言】函数递归——高手都在用的小技巧

【C语言】函数递归——高手都在用的小技巧

时间:2024-04-04 23:30:25浏览次数:16  
标签:高手 递归 10 int C语言 阶乘 Print 我们

文章目录

1. 什么是递归

递归简单来说就是一个函数自己调用自己,是不是感觉很莫名其妙,我第一次学习的时候就觉得为什么函数会自己调用自己呢,别急,我们来看一个生活上常见的例子

试想一下这样的场景,妈妈在哄小孩子睡觉,说讲一个故事吧。从前有座山,山中有座庙,庙里有个老和尚,老和尚在给小和尚讲故事:“ 从前有座山,山中有座庙,庙里有个老和尚,老和尚在给小和尚讲故事:“ 从前有座山,山中有座庙,庙里有个老和尚,老和尚在给小和尚讲故事:“ 从前有座山,山中有座庙,庙里有个老和尚,老和尚在给小和尚讲故事:“太困了不讲了”,于是都回去睡觉了。”于是都回去睡觉了。”于是都回去睡觉了。”于是都回去睡觉了。

为什么妈妈讲了一个故事,似乎感觉讲了很多是的,造成这种感觉的原因故事里的内容是在又重复着做一件事情

再比如,有些领导讲话,看似讲的很多,本质上也就是重复地在说一个内容的重点,开玩笑的,领导讲话还是要仔细听的哈

递归有点像剥洋葱,由外向里一层一层嵌套的模型就是递归,一层套着一层,直到掰到最里层。

没听懂,没关系,再来看一个史上最简单的C语言递归代码:

#include<stdio.h>

int main()
{
    printf("hello,world\n");
    main();//main函数中调用main函数
    return 0;
}

上述就是一个简单的递归程序,只不过上面的递归只是为了演示递归的基本形式,不是为了解决问题,代码最终也会陷入死递归,F5开始调试,我们发现,代码死循环的原因是栈溢出(Stackoverflow)

在这里插入图片描述

2. 递归的主要思想

递归我们可以拆开来理解,一个是递,一个是归,“递”怎么理解,很简单,给它组一个词语,能组什么词语呢,递进,递推,递增…是吧,仔细想想会有很多,那“归”组什么词语,是不是归属,回归,归一…

我们如何准确的理解递归中的“递”和“归”,从组词中我们不难看出,递就是递推的意思,归就是回归的意思

有没有会打太极的小伙伴,这种感觉是不是和打太极一样,把一个大型复杂问题层层转化为一个与原问题相似,但规模较小的子问题来求解;直到子问题不能再被拆分,递归就结束了。所以递归的思考方式就是把大事化小的过程。没听的太明白也没关系,接下来让我们慢慢去体会递归的乐趣

3. 递归举例说明

在正试进入递归之前,我还想说明一下,递归的两个必要条件:

• 递归存在限制条件,当满⾜这个限制条件的时候,递归便不再继续。

• 每次递归调⽤之后越来越接近这个限制条件。

条件暂时看不懂也没有什么关系,在下面的例子中我们会更多的体会这两个条件

3.1 n的阶乘

题⽬:计算n的阶乘(不考虑溢出),n的阶乘就是1~n的数字累积相乘。

有些小伙伴看到这个题目是不是感觉很简单,一个简单的for循环就解决了

for (int i = 1; i <= n; i++)
{
	r = r * i;
}

很聪明哈,接下来我们重点来看看使用递归是怎么实现的

1! = 1

2! = 1 * 2

3! = 1 * 2 * 3

4! = 1 * 2 * 3 * 4

有没有什么规律,小伙伴就讲了这有什么规律,不就是阶乘的算法内容嘛,没看清楚,我们来换一种写法

1! = 1

2! = 1! * 2

3! = 2! * 3

4! = 3! * 4

现在呢,是不是发现了什么不得了的东西 n! = n * (n-1)! 当然了,这个东西也就是阶乘的公式,有什么作用呢,那可太有用了

我们讲递归的思想的时候提到了大事化小的过程,这样的思路就是把⼀个较⼤的问题,转换为⼀个与原问题相似,但规模较⼩的问题来求解的,然后我们通过小问题就能找到解决大问题的方法

当 n==0 的时候, n == 1

当 n > 0 的时候,n! = n * (n-1)!

那么就可以轻松写出来 n的阶乘 的递归公式:

在这里插入图片描述

那我们就可以很轻松地写出函数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 r = Fact(n);
    
	printf("%d的阶乘是%d\n", n, r);
	return 0;
}

在这里插入图片描述

代码运行成功没有什么问题

哎,讲得太快了,是不是还有小伙伴还没听懂啊,没关系,我们来画图分析一下代码加强自己的理解

我们来以5的阶乘来分析举例(绝对不是因为6的阶乘不好分析,好吧)

在这里插入图片描述

这样是不是就理解的更好了,还是有点晕的小伙伴也先别着急,我们还有几个例子,一起来看看吧

3.2 顺序打印⼀个整数的每⼀位

输⼊⼀个整数m,按照顺序打印整数的每⼀位。

⽐如:输⼊:1234 输出:1 2 3 4

输⼊:520 输出:5 2 0

这个题目是不是一开始就有点蒙,别急,我们先想想看怎么拿到整数 m 的每一位?

聪明的小伙伴就反应很快,说使用 m%10(取余符号)就行了,我们来解释一下吧

我们说如果n是⼀位数,n的每⼀位就是它自己

n是超过1位数的话,就得拆分每⼀位

1234%10就能得到4,然后就得思考一下怎么去掉4,得到123,是不是就得用 / (除号),对吧

1234/10得到123,这就相当于去掉了4

然后继续对123%10,就得到了3,再除10去掉3,以此类推

不断的 %10 和 /10 操作,直到1234的每⼀位都得到;

嗯嗯看来大家都很棒啊,但是当我们仔细想一想的时候会发现一点问题,我们想要得到的是 1 2 3 4 可是我们好像最先输出的是 4 然后是 3 这样的话最好的结果不就是 4 3 2 1 了嘛,哎,怎么办呀,我们预期的不一样,需要倒序输出吗,但是这样做是不是有点太麻烦了

想一想怎么办,我们不难发现其实⼀个数字的最低位是最容易得到的,即是通过 %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)

以此类推

在这里插入图片描述

这样的递归可以看的懂嘛,哎,对吧,就是运行递归思想来解决这个问题,可能有些小伙伴心里有点疑问,说这样可以做的到吗,不可以吗,来我们运行一下试试

#include<stdio.h>

void Print(int n)
{
	if (n > 9)
	{
		Print(n/10);
	}
	printf("%d ", n % 10);
}

int main()
{
	int n = 0;
	scanf("%d", &n);

	 Print(n);

	return 0;
}

在这里插入图片描述

没有什么问题,看来那些小伙伴多氯了哈

在这个解题的过程中,我们就是使⽤了大事化小的思路

把Print(1234) 打印1234每⼀位,拆解为⾸先Print(123)打印123的每⼀位,再打印得到的4

把Print(123) 打印123每⼀位,拆解为⾸先Print(12)打印12的每⼀位,再打印得到的3

直到Print打印的是⼀位数,直接打印就⾏

还没明白,我们来画个图增加我们的理解

在这里插入图片描述

看到这里,我相信你对递归有了一定的自己的了解,那么恭喜你

最后我想说一下,既然递归那么好用,那么我是不是看到题就递归,肯定不行对不对,递归呀它具有一定的局限性,这就不得不提一下迭代了

4. 递归与迭代

递归是⼀种很好的编程技巧,但是和很多技巧⼀样,也是可能被误⽤的,就像第一个例子⼀样,看到推导的公式,很容易就被写成递归的形式

在这里插入图片描述

int Fact(int n)
{
	if (n == 0)
	{
		return 1;
	}
	else
		return n * Fact(n - 1);
}

Fact函数是可以产⽣正确的结果,但是在递归函数调⽤的过程中涉及⼀些运⾏时的开销,函数调用的时候会向栈开辟一块内存,我们想想,如果函数不返回的时候,一片内存的空间是不是不会消失,这样就会很容易栈溢出(Stackoverflow)

所以如果不想使⽤递归就得想其他的办法,通常就是迭代的方式(通常就是循环的方式)

for (int i = 1; i <= n; i++)
{
	r = r * i;
}

上述代码是能够完成任务,并且效率是比递归的方式更好的

事实上,我们看到的许多问题是以递归的形式进⾏解释的,这只是因为它比非递归的形式更加清晰, 但是这些问题的迭代实现往往比递归实现效率更⾼

当⼀个问题非常复杂,难以使用迭代的方式实现时,此时递归实现的简洁性便可以补偿它所带来的运⾏时开销

4.1 求第n个斐波那契数

有很多人不知道斐波那契数是什么,我们百度搜一下

在这里插入图片描述

像计算第n个斐波那契数,其实是不适合使用递归求解的,但是斐波那契数的问题通过是使⽤递归的形式描述的

根据百度的提示,我们也可以很轻松的写出 斐波那契数 的递归公式:

在这里插入图片描述

看到这公式,很容易诱导我们将代码写成递归的形式,函数如下:

int Fib(int n)
{
	if (n <= 2)
	{
		return 1;
	}
	else return Fib(n - 1) + Fib(n - 2);
}

对吧,接下来就是测试一下

#include<stdio.h>

int Fib(int n)
{
	if (n <= 2)
	{
		return 1;
	}
	else return Fib(n - 1) + Fib(n - 2);
}

int main()
{
	int n = 0;
	scanf("%d", &n);

	int r = Fib(n);

	printf("%d\n", r);
	return 0;
}

写出来很简单,大家自己调试一下,会发现前几个数基本上都没有什么问题

但是当我们n输⼊为50的时候,需要很⻓时间才能算出结果,这个计算所花费的时间,是我们很难接受的, 这也说明递归的写法是⾮常低效的,那是为什么呢?

在这里插入图片描述

其实递归程序会不断的展开,在展开的过程中,我们很容易就能发现,在递归的过程中会有重复计算,而且递归层次越深,冗余计算就会越多,这个好理解吧

那怎么优化我们的代码呢,使用递归是⾮常不明智的,我们就得想迭代的方式解决

我们知道斐波那契数的前2个数都1,然后前2个数相加就是第3个数,那么我们从前往后,从小到大计算就行了

int Fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n > 2)
	{
		c = a + b;
		b = a;
		a = c;
		n--;
	}
	return c;
}

迭代的方式去实现这个代码,效率就要高出很多了

所以呀,我们说有时候,递归虽好,但是也会引入⼀些问题,所以我们⼀定不要迷恋递归,适可而止就好

感谢你能读到这里,希望这篇文章对你有用,溜了溜了,我们下周再见吧

标签:高手,递归,10,int,C语言,阶乘,Print,我们
From: https://blog.csdn.net/2302_78420373/article/details/137385427

相关文章

  • 杨氏矩阵(C语言)
    文章目录问题技术名词解释思路关键代码运行代码问题有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的,请编写程序在这样的矩阵中查找某个数字是否存在。要求:时间复杂度小于O(N);技术名词解释杨氏矩阵: 矩阵的每行从左到右是递增的,每列从上到下是递增的......
  • C语言—用EaxyX绘制实时钟表
     代码效果如图#undefUNICODE#undef_UNICODE#include<graphics.h>#include<conio.h>#include<math.h>#definewidth640#definehigh480#definePI3.14159intmain(){ initgraph(width,high); intcenter_x,center_y; center_x=width/2;......
  • C语言经典例题(17) --- 最小公倍数、单词倒置、你是天才吗?、完美成绩、判断整数的奇偶
    1.最小公倍数正整数A和正整数B的最小公倍数是指能被A和B整除的最小的正整数,设计一个算法,求输入A和B的最小公倍数。输入描述:输入两个正整数A和B。输出描述:输出A和B的最小公倍数。输入:57输出:35#include<stdio.h>intmain(){inta=0;intb=0;int......
  • C语言经典例题(18) --- 判断字母、三角形判断、衡量人体胖瘦程度、翻转金字塔图案、平
    1.判断是不是字母题目描述:KK想判断输入的字符是不是字母,请帮他编程实现。输入描述:多组输入,每一行输入一个字符。输出描述:针对每组输入,输出单独占一行,判断输入字符是否为字母,输出内容详见输出样例。输入:A6输出:Aisanalphabet.6isnotanalphabet......
  • 高手训练 负环 题解
    题目链接方向:枚举点的个数,找出其中边权和为负数的最小值。直接枚举显然会超时,不妨考虑使用倍增凑出点的个数(注意:点数不完全有单调性,但是后面会提到如何转化处理)。先预处理出\(dis_{t,i,j}\)表示经过\(t\)条边,从\(i\rightarrowj\)的最短路长度。那么类似\(Floyed\)显然......
  • 16.C语言错题整理
    一些C语言错题//求n的阶乘intsum=1;intn;printf("请输入n的值:");scanf("%d",&n);for(intj=1;j<n+1;++j){sum*=j;}printf("%d\n",sum);inthee=0;intb=1;for(......
  • 信息学奥赛一本通题目解析:1204:爬楼梯(记忆化递归)
    【题目描述】树老师爬楼梯,他可以每次走1级或者2级,输入楼梯的级数,求不同的走法数。例如:楼梯一共有3级,他可以每次都走一级,或者第一次走一级,第二次走两级,也可以第一次走两级,第二次走一级,一共3种方法。【输入】输入包含若干行,每行包含一个正整数N,代表楼梯级数,1≤N≤30。【......
  • DFS 全排列问题 C语言代码
    深度优先搜索(DFS)是一种遍历算法,尽可能深地向子树中的结点搜索,直到达到一定的深度,再回溯到上层的结点,继续搜索未被访问的结点。全排列问题给定4个数1234,求他们所有可能的排列结果。代码#include<stdio.h>voiddfs(intx);inti;inta[4];intresult[4];/......
  • C语言 | Leetcode C语言题解之第8题字符串转换整数atoi
    题目:题解:intmyAtoi(char*s){inti=0;intout=0;intpol=1;intlen=strlen(s);if(len==0)return0;while(s[i]=='')i++;//删除空格if(s[i]=='-'){//判断正负pol=-1;i++;}else......
  • c语言中关于字符数组赋值问题
    一维数组代码#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;constintN=1010;charstr[N];charst[N];chars1[N];chars2[N];/*abcdeabcdeabcdeabcde*/intmain(){ scanf("%s",&str+1); ......