位置：首页-资讯-后端开发

C语言的递归函数详解

2024-04-02 19:55

短信预约 -IT技能 免费直播动态提醒

函数递归

程序调用自身的编程技巧称为递归 recursion）

函数自己调用自己就是递归

你也可以理解成是一种嵌套结构，但递归分为俩部分，第一是“递”，进入嵌套结构。第二是”归“，最终会一步一步返回。第一次接触递归都会很懵，慢慢理解这个过程就明白了。

什么是递归？

递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，

递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的主要思考方式在于：把大事化小

递归的俩个必要条件

代码引例1

接受一个整型值（无符号），按照顺序打印它的每一位。

例如：

输入：123，输出 1 2 3

参考代码：

#include <stdio.h>
void print(int n) {
 if(n>9)
 {
 print(n/10);
 }
 printf("%d ", n%10);
}
int main()
{
 int num = 123;
 print(num);
 return 0; }

运行结果如下：

我们要怎么理解这个函数递归的实现呢

我们可以采用画图方式理解这个过程

所以我们可以看到，递归必须满足俩个必要条件：

1.存在限制条件，当满足这个限制条件的时候，递归便不再继续。

2.每次递归调用之后越来越接近这个限制条件。

题中的限制条件就是（n>9),当我们的n通过（n/10)越来越少，直至n=1，无法满足时，递归停止，并开始返回。

这里有一个重要点就是print（n/10),如果没有这个条件，换成print（n）的话，n一直无法减小，一直进行递归。最后会导致栈溢出(Stack Overflow)。

栈溢出（Stack Overflow）

关于栈溢出，我就先简单介绍一下栈

栈：栈是一种计算机系统中的数据结构，它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来），是一种特殊的线性表。栈的操作常用的有进栈（PUSH），出栈（POP），还有常用的标识栈顶和栈底。

可以把栈想象成一摞扑克牌一样，一张一张叠加起来。

而栈溢出呢是缓冲区溢出的一种，缓冲区溢出：简单的说，缓冲区溢出就是超长的数据向小缓冲区复制，导致数据超出了小缓冲区，导致缓冲区其他的数据遭到破坏，这就是缓冲区溢出。而栈溢出是缓冲区溢出的一种，也是最常见的。只不过栈溢出发生在栈，堆溢出发生在堆，其实都是一样的。

而在代码引例1中

系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者（死递归），这样有可能导致一

直开辟栈空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出

合理使用递归

使用递归的宗旨是把大事化小

所以遇到问题时，我们应该明白是要把问题简单化，而不是习惯用递归，就一直用递归思考问题

我们应该清楚是不是用递归的思想会比较简单，或者换成递归的思想也可以实现，我们可以通过例题明白

代码引例3

求n的阶乘

用循环的方法，代码如下：

int main()
{
	int n = 0;
	int ret = 1;
	scanf("%d", &n);
	//循环产生1~n的数字
	int i = 0;
	for (i = 1; i <= n; i++)
	{
		ret = ret * i;
	}
	printf("ret = %d\n", ret);

	return 0;
}

而采用递归的话，代码如下：

int fac(int n)
{
	if (n <= 1)
		return 1;
	else
		return n * fac(n - 1);
}

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

很多人刚学递归，都是懂了，但不知道怎么用。

而这道题可以先用公式来理解题目，再来用递归就容易多了

再来对比一下函数的代码，是不是清晰明了呢

代码引例4

求第n个斐波那契数。（不考虑溢出）

代码如下：

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

这道题同样我们也可以利用公式构造一个函数实现递归

具体思路如下：

解释要合理使用递归

通过以上俩个例题，我们可以发现俩个问题：

在使用 fib 这个函数的时候如果我们要计算第50个斐波那契数字的时候特别耗费时间。

使用 factorial 函数求10000的阶乘（不考虑结果的正确性），程序会崩溃。

为什么呢？

我们发现 fib 函数在调用的过程中很多计算其实在一直重复。

如果我们把代码修改一下：

int count = 0;//全局变量
int fib(int n) {
 if(n == 3)
 count++;
 if (n <= 2)         
 return 1;
    else
    return fib(n - 1) + fib(n - 2);

最后我们输出看看count，是一个很大很大的值。

那我们如何改进呢？

在调试 factorial 函数的时候，如果你的参数比较大，那就会报错： stack overflow（栈溢出）

这样的信息。

那如何解决上述的问题：

1.将递归改写成非递归。

2.使用static对象替代 nonstatic 局部对象。在递归函数设计中，可以使用 static 对象替代

nonstatic 局部对象（即栈对象），这不仅可以减少每次递归调用和返回时产生和释放 nonstatic 对象的开销，而且 static 对象还可以保存递归调用的中间状态，并且可为各个调用层所访问

比如，下面代码就采用了，非递归的方式来实现：

//求n的阶乘
int factorial(int n) {
        int result = 1;
        while (n > 1)
       {
             result *= n ;
             n -= 1;
       }
        return result; }
//求第n个斐波那契数
int fib(int n) {
     int result;
     int pre_result;
     int next_older_result;
     result = pre_result = 1;
     while (n > 2)
     {
           n -= 1;
           next_older_result = pre_result;
           pre_result = result;
           result = pre_result + next_older_result;
     }
     return result; 
     }

提示：

1.许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。

2.但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。

3.当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销