C语言函数递归详解（能看懂文字就能明白系列）_c语言递归

目录

递归的概念

最简单的递归演示

递归的思想

递归的限制条件

尾递归（阶乘演示）

递归的优缺点(斐波那契数列演示）

补充

---

递归的概念

C语言允许函数调用它自己，这种调用过程称为递归。递归有时难以捉摸，有时却很方便实用。

结束递归是使用递归的难点，因为如果递归代码中没有终止递归的条件测试部分，一个调用自己的函数会无限递归。

可以使用循环的地方通常都可以使用递归，有时用循环解决问题比较好，但有时用递归更好。递归方案更简洁，但效率却没有循环高（有时候可能会导致栈溢出）

最简单的递归演示

接下来写一个简单的递归代码来体会一下

#include<stdio.h>
int main()
{
	printf("digui\n");
	main();
 
	return 0;
}

上述就是一个简单的递归程序——main()函数中又调用了main()函数，重复调用。只不过上面的递归只是为了演示递归的基本形式，不是为了解决问题，代码最终也会陷入死递归，导致栈溢出（Stack overflow）

递归的思想

把一个大型的复杂问题层层转化为一个与原问题相似，但规模较小的子问题求解，直到子问题不能再被拆分，递归就结束了。所以递归的思考方式就是把大事化小的过程。

递归中的递就递推的意思，归就是回归的意思。

递归的限制条件

递归在书写的时候，有2个必要条件：

• 递归存在限制条件，当满足这个限制条件的时候，递归便不再继续。
• 每次递归调用之后 越来越接近这个限制条件。

在下面的例子中，我们逐步体会这2个限制条件。

尾递归（阶乘演示）

最简单的递归形式是把递归调用置于函数的末尾，即正好在return语句之前。这种形式的递归被称为尾递归，因为递归调用在函数的末尾。尾递归是最简单的递归形式，因为它相当于循环。

下面分别用递归和循环计算阶乘。一个正整数的阶乘是从1到该整数的所有整数的乘积，特别，0！等于1，负数没有阶乘。

这样的思路就是把一个较大的问题，转换为一个与原问题相似，但规模较小的问题来解决的。

n!——>n*(n-1)!

                (n-1)!——>(n-1)*(n-1)!

直到n是1或者0的时候，不再拆解

再稍微分析一下，当n<=1的时候，n的阶乘是1，其余n的阶乘都是可以通过上述公式计算。

公式如下：

int fact(int n)
{
	if (n <= 0)
		return 1;
	else
		return n * fact(n - 1);
}
 
 
 
#include<stdio.h>
int main()
{
	int n = 0;
	scanf("%d",&n);
	int rs=fact(n);//定义一个计算n的阶乘的函数
	printf("%d\n", rs);
	return 0;
}

测试的时候要把输入限制在0到12。因为12！已经快接近五亿，而13！比62亿还大，已经超过我们系统中long 类型能表示的范围。要计算超过12！，必须使用能表示更大范围的类型，如double或者long long。

 这是递归的流程图：

#include<stdio.h>
int fact(int n)//这里用循环定义一个计算阶乘的函数
{
	int i = 0;
	int ret = 1;
	for (i = 1; i <= n; i++)
	{
		ret *= i;
	}
	return ret;
}
int main()
{
	int n = 0;
	scanf("%d",&n);
	int rs=fact(n);
	printf("%d\n", rs);
	return 0;

既然用递归和循环来计算都没问题，那么到底应该使用哪个呢？一般而言，选择循环比较好，首先，每次递归都会创建一组变量，所以递归使用的内存更多，而且每次递归调用都会把创建的一组新变量放在栈中。递归调用的数量受限于内存空间，其次，由于每次调用函数都需要花费一定的时间，所有递归的执行速度较慢，但在某些情况下，不能用简单的循环代替递归，因此各位伙伴还是要好好理解递归。

递归的优缺点(斐波那契数列演示）

递归既有优点也有缺点。优点是递归为某些编程问题提供了最简单的解决方案。缺点是一些递归算法会快速消耗计算机的内存资源。另外，递归不方便阅读和维护。我们用一个例子来说明递归的优缺点。

斐波那契数列的定义如下：第一个和第二个数字都是1和2，而后面的数字都是其前两个数字之和。

例如:该数列的前几个数是1、1、2、3、5、8、13。

可以利用上面数字的规律写出以下公式，再用代码写出来即可

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，然后在该函数中药要调用Fib()两次，在第二级递归调用要分别创建两个变量n，这两次调用中的每次调用又会进行两次调用，因而在第三级递归中要创建4个名为n的变量。此时总共创建7个变量。由于每次递归创建的变量都是上一级递归的两倍，所以变量的数量呈现指数增长！所以在这个例子中，指数增长的变量数量很快就消耗掉计算机的大量内存，导致程序崩溃。

虽然这是个极端的例子，但是该例子说明，在程序中使用递归要特别注意，尤其是效率优先的程序。

补充

递归函数调用的过程中涉及一些运行时的开销：

在C语言中每一次函数调用，都需要为本次函数调用在栈区申请一块内存空间来保存函数调用期间的各种局部变量的值，这块空间被称为运行时堆栈，或者函数栈帧。

函数不返回，函数对应的栈帧空间就一直占用，所以如果函数调用中存在递归调用的话，每一次递归函数调用都会开辟属于自己的栈帧空间，直到函数递归不再继续，开始回归，才逐层释放栈帧空间。

所以如果采用函数递归的方式完成代码，递归层次太深，就会浪费太多的栈帧空间，也可能引起栈溢出的问题。

所有如果不想使用递归就得想其他的办法，通常就是迭代的方式（通常就是循环的方式）。