【c语言】一篇文章搞懂函数递归

一、递归的概念

递归是什么？其实，递归是一种解决问题的方法，体现在c语言中就是函数自己调用自己。让我们举一个最史上最简单的递归代码：

#include<stdio.h>

int main()
{
	printf("hello world!\n");
	main();
    return 0;
}

上述代码当中，主函数main自己调用了自己，不难看出，这是一个死递归。主函数会无限调用自己，最终导致栈区内存不够而溢出，程序崩溃。不过这只是一个最简单的递归演示，真实的递归可不是这么使用的。

1.递归思想

那么递归为什么会被使用呢？这就要提到递归思想了。递归思想，就是在解决一个难以求解的大型问题时，像剥洋葱皮一样，一层一层逐步推进，直到问题被解决。说白了，递归就是把大事化小的过程。

2.递归的限制条件

在我们刚才编写的代码当中，由于没有限制条件，所以主函数会不断地调用自己而导致栈溢出。所以一个递归的完成，限制条件是不可或缺的。当程序运行到满足这个限制条件的时候，递归就会停止。而每一次的递归，都会不断接近这个限制条件。我们在编写递归的时候，一定要先确定好限制条件。

二、递归举例

有了以上基础知识，接下来我会用一些例子来帮助大家理解递归的精髓。

1.求一个数的阶乘

一个整数n的阶乘就是1~n之间的整数全部相乘。既然这样，那么我们就会想到：使用循环语句产生从1到n之间的所有整数，然后将他们全部相乘就可以了。好，我们先用代码实现：

#include<stdio.h>

int main()
{
	int n = 0;
	scanf("%d", &n);
	int i = 0;
	int ret = 1;//记录乘积
	for (i = 1; i <= n; i++)
	{
		ret *= i;
	}
	printf("%d\n", ret);
}

运行结果：

没错，5的阶乘就是120。那么，能不能用递归实现阶乘呢？

还记得求阶乘有一个公式吗？

n! = n * ( n - 1 )!

n的阶乘就是n乘n-1的阶乘。那么这里我们就可以用到递归思想了：为了求得n的阶乘，我们可以先求出n-1的阶乘，为了求得n-1的阶乘，我们需要求出n-2的阶乘......直到求出1的阶乘为止（因为1的阶乘就是1）。

不过，我们好像遗漏了一个问题：0的阶乘是不是也是1？所以我们应该计算到0的阶乘为止，这样，用户输入0程序就不会出现问题了。

好了，让我们画一个简图便于我们创造出限制条件：

接下来我们用代码实现一下：

#include<stdio.h>

int fact(int n)
{
	if (n == 0)
	{
		return 1;
	}
	if (n > 0)
	{
		return n * fact(n - 1);
	}
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d\n", fact(n));
	return 0;
}

运行结果：

可以看出，运行结果是正确的。如果你还是难以理解，我们画一张图来显示它的详细流程：

程序前半部分逐层深入，从求5的阶乘深入到求0的阶乘，这个过程叫做递推，由于我们递归的限制条件是n==0，当计算到0的阶乘时，此层递归传入的参数刚好是0，满足条件，就不会继续深入了。这时候，1就是此层递归的返回值，便于前一层递归计算1的阶乘，直到最后得出最后结果。这个过程叫做回归。

现在，想必你对递归已经有一定的认知了。不过，在这个例子当中，如果输入的数过大，会出现栈溢出的情况，因为每一次的递归深入都是在调用函数，而函数的调用是要消耗栈区的内存空间的。当内存空间被占满时，就会发生栈溢出。

2.打印一个整数的每一位

接下来我们思考一下这个问题：用递归打印一个整数的每一位。我们都知道，对于一个一位数而言，它的每一位就是他自己，如果它超过一位，就要一个一个地得到它的每一位。

比如现在有一个数1234，1234%10就能得到个位数4，之后我们把1234/10，得到123，相当于去除了这个4，接着继续%10，就得到3，然后再/10，再%10...以此类推，在每一步都将得到的数打印出来，我们就可以分别打印出这个数地每一位。

有了基本想法之后，我们来想想限定条件：由于可以用取模的方法直接求得个位数，我们就将功能分为两步：第一步判断一个数是否是一位数，如果是就直接打印它，如果不是就对它除以10的结果进行判断。第二步，打印一个数%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;
}

运行结果：

程序运行过程中，传入1234到函数当中，由于1234不是一位数，我们就将这个四位数拆解为打印123的每一位，并且打印出4，当进入123作为参数的递归时，将其拆解为打印12的每一位并且打印出3，直到得到1，递归就不继续进行，逐层深入解决问题。

我们再用流程图来表示以下整个过程：

按照这个流程，屏幕就会依次打印出1，2，3，4。如果你想要将这四个数倒着打印，那么只需要将printf函数写在判断语句之前即可。

这样看来，递归是不是在某些情况下比循环更简单？如果这个程序用循环来写，那么就有很多细节需要处理。而使用递归的方法，虽然会牺牲一些运行效率，但是能够避免使用复杂逻辑，减少代码冗余，提高程序的简洁性。

接着，我们再来写一个程序：

3.求第n个斐波那契数

首先来介绍一下什么叫做斐波那契数列。所谓斐波那契数列，就是说一个正整数数列，前两个数都是1，从第三个数开始，每一个数都是它之前的两个数之和。我们列举一下前几个数：1，1，2，3，5，8，13，21，34......

我们从它的概念上入手：由于从第三个数开始每一个数就是它之前的两个数之和，言外之意就是我们可以求出它的前两个数，然后相加。如果前两个数不是第一，第二个数，就继续求下去。。。直到求到最开始的数为止。我们画一个简图来表示限制条件：

这样是不是就感觉很简单了？我们来实现一下：

#include<stdio.h>

int fib(int n)
{
	if (n >= 3)
	{
		return fib(n - 1) + fib(n - 2);
	}
	if (n == 1 || n == 2)
	{
		return 1;
	}
}

int main()
{
	int n = 0;
	while (scanf("%d", &n) != EOF)//这里进行多组输入
	{
		printf("%d ", fib(n));
	}
	return 0;
}

运行结果：

三、递归的潜在问题

对于之前求斐波那契数的程序，如果我们输入一个较大数字比如40，50等，你会发现它需要很久才能算出结果。这是为什么呢？由于我们的函数设计是要先求出前两个数，对于第50个斐波那契数，我们就要先求第48个数和第47个数，要求出这两个数，又要求第47个数，第46个数，第46个数，第45个数......这样就导致好多的数被重复计算了，而且计算次数是成指数级增长的。我们在刚才的代码中增加一个变量来记录一下第三个斐波那契数数被计算的次数：

#include<stdio.h>

int count = 0;

int fib(int n)
{
	if (n >= 3)
	{
		if (n == 3)
		{
			count++;
		}
		return fib(n - 1) + fib(n - 2);
	}
	if (n == 1 || n == 2)
	{
		return 1;
	}
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d\n", fib(n));
	printf("%d次\n", count);
	return 0;
}

运行结果：

求第40个数的时候，第三个斐波那契数就被计算了三千九百多万次。这种计算量，就算是计算机也是心余力绌。在这种情况下，递归虽然易于写出，但是运行效率也太差了。我们尝试用循环来实现一下它：

#include<stdio.h>

int fib(int n)
{
	int a = 1, b = 1, c = 1;
	while (n >= 3)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d ", fib(n));
	return 0;
}

运行结果：

可以看出，运行结果与递归的方式是相同的，而且用时在包括调试时间的情况下也只有不到8毫秒。

所以，递归虽好，但是有时候会出现运行效率低、栈溢出的情况。我们在使用的时候要合理考虑是否使用递归。

总结

函数递归是一种解决问题的方法，它的表现形式是函数自己调用自己，核心思想是把大事化小。递归是有限制条件的，否则就会成为死递归。在编写程序的时候，一定要思考其限制条件。递归不是万能的，它可能出现运行效率低，栈溢出的情况。在编写程序时要根据实际情况进行思考是否使用递归。

到这里，想必你对递归已经有了新的认知了吧！后续博主主要会与大家探讨指针方面的内容，感谢大家的支持❤❤❤