探索递归的乐趣：探秘C语言中的递归

目录

1.什么是递归？

2.无返回值的递归

3.有返回值的递归

4.递归的弊端

---

1.什么是递归？

用博主的话讲，一个函数在其内部自己反复调用自己的的过程就是“递”，调用结束后的层层返回则是“归”。无论是有返回值还是没有返回值的函数，在其递归的过程中，都需要一个条件去限制它递归的次数，以防止“死递归”的产生，那递归究竟该如何去使用呢？我们通过一个简单的案例的解释一下。

2.无返回值的递归

我们看一下下面这道题：

用递归实现数字的正序打印。

题的意思很简单，就是给出一个数，让我们从第一位到最后一位一次打印出来。

比如输入 1234 这个数字，打印出来的效果就是1 2 3 4。

那么用递归该如何去实现这个打印呢？

我们并不知道这个数字有多少位，只能从最后一位进行依此拆分也就是每一次都打印n%10，再让n/10，直到n只剩下一位数字的时候停止，但是按照这个思路来实现好像会逆序打印出数字的每一次，这个时候递归的作用就体现出来了。

如果我们让递归的最后一层打印数字的第一位，倒数第二层打印数字的倒数第二位...这样下来就可以依此打印出每一位的数字，达到正序打印的目的，也就是说我们在函数调用自己之后在去打印n%10的操作就可以实现正序打印了，接下来我们实践一番。

#include <stdio.h>
//                   一
void Point(int n)//1234->4
{
	if (n > 9)
	{//                   二      三     四
		Point(n / 10);//123->3  12->2   1->1
	}
	printf("%d ", n % 10);//归的时候按照四三二一的顺序 打印出来也就是1 2 3 4
}
int main()
{
	int n;
	scanf("%d", &n);
	Point(n);
	return 0;
}

打印出来也确实如此：

3.有返回值的递归

无返回值的递归我们进行了说明，那么有返回值的递归该怎么实现呢？

还是用一个案例来说明：

用递归实现n的阶乘

可能会有小伙伴有疑问，我会用递归得到1 2 3 4 5，可怎么把它们乘到一起去呢？

不要着急，我们对每一次递归都进行分析，有了上一个案例的解释，我们很容易就可以得到1,2,3,4,5这5个数字，只需要每次递归传入（n-1）就行了，那么将它们想乘也用同样的道理就可以了，首先我们先来确定一下递归停止的条件，我们知道阶乘是肯定不能把0成进去的，所以条件显而易见：当n > 1的时候进行递归（因为n = 0的时候递归为0），那么1怎么办呢？我们可以多判断一次，当n = 1的时候返回值为1，也就是return 1。1的返回有了着落我们开始进行2的操作。

我们既然要返回阶乘，那么返回的数自然也是数字相乘的结果，那我们为什么不把返回的结果和n相乘一起返回去呢？1的返回我们已经有了，到2的时候我们返回1*2；到3的时候我们返回（1*2）*3...以此类推，那我们n > 1时的返回结果就也可以确定了，就是return n*fac（n - 1）。（fac是函数名）。

#include <stdio.h>

int fac(int n)
{
	if (n == 1)
		return 1;
	else
		return n * fac(n - 1);
}
int main()
{
	int n, m;
	scanf("%d", &n);
	m = fac(n);
	printf("%d\n", m);
	return 0;
}

4.递归的弊端

小伙伴们们可能有疑惑，递归这么好用，代码量又少，怎么会有弊端呢？

弊端是肯定有的，只不过上面的题目表现不出来罢了，递归虽然可以用少量的代码就可以实现复杂的操作，但是这通常是以牺牲时间为代价的。比如 我们来看一下下面这道题：

用递归求斐波那锲数

（斐波那锲数是 1 1 2 3 5 8 13.... 除了前两个数是1不变，后面的数字都是它前面两个数的相加之和）

这是一道很经典的题目，这道题目有了上面两道题做铺垫相信已经难不倒大家，这里我们直接给出源码。

#include <stdio.h>

int fbn(int n)
{
	if (n == 1 || n == 2)//1,2的时候是1
		return 1;
	else
		return fbn(n - 1) + fbn(n - 2);//返回前两项相加之和
}
int main()
{
	int n, m;
	scanf("%d", &n);
	m = fbn(n);
	printf("%d\n", m);
	return 0;
}

我们测试一下就可以知道，当传入的数字超过40的时候，通常要等好长时间才可以得到答案，这是为什么呢，我们进行测试一下就知道了

 我们用了一个全局变量count来记录这个递归计算了多少次n = 3的斐波那锲数

结果发现非常的惊人，当n = 40的时候，n = 3的情况被计算了将近4千万次，由此想一想其他的数字，计算量加起来可能已经冲破天际了，也就是有了这样的计算量，计算的才如此之慢。

由此可见，也不是什么情况下都应该使用递归，有时可能会适得其反。

好了， 到了这里文章就结束了，感谢小伙伴们的观看，以后会有更多知识点进行分享。