【C语言】函数重难点之函数递归

ゝ一世哀愁。 2023-10-14 09:32 6阅读 0赞

> 大家好，我是深鱼~

**目录**

一、函数递归知识讲解

1.什么是递归？

2.递归的两个必要条件

2.1练习1：

2.2练习2：

二、递归与迭代

2.1练习3

2.2练习4

--------------------

### 一、函数递归知识讲解 ###

#### 1.什么是递归？ ####

> 程序**调用自身**的编程技巧称为递归
> 
> 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂问题层层转化为一个与原问题相似的规模较小的问题来求解
> 
> 递归策略：只需少量的程序就可描述出解题过程所需要的**多次重复计算**，大大**减少了**程序的**代码量**
> 
> **递归的主要思考方式在于：把大事化小**

**最简单的递归：**main函数自己调用自己

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

**代码结果：**不停的打印hehe，直到程序崩溃才退出

![bccd66dfc35b432e886f1c3ef98478d1.png][]

**问：**那为什么程序会崩溃呢？

**原因：**stack overflow栈溢出了，对于每个程序而言，栈能使用的内存是有限的，如果程序使用的**栈空间超过最大值**，就会发生栈溢出，程序发生崩溃

![b6da2f0c0b0b494886103e5feff93f9b.png][]

虽然是个错误的程序，但是这个程序中main函数确实是不断的调用自己，然后不断递归，直到栈溢出

#### 2.递归的两个必要条件 ####

> **·**存在限制条件，当满足这个限制条件的时候，递归便不再继续
> 
> **·**每次递归调用以后不断接近这个限制条件

##### 2.1练习1： #####

> 接受一个整型值（无符号），按照顺序打印它的每一位
> 
> 例如：输入：1234，输出1 2 3 4

**最常见的做法：**让输入的数不断%10，/10，然后存起来放入数组，然后打印数组中的每一个元素

下面我们来看看使用**递归的方法**怎么写：

> 首先函数是自己调用自己，那就得写一个自定义函数，那我们就写一个Print函数将输入值的每一位打印在屏幕上，然后我们运用大事化小的思路:
> 
> Print（1234）//不断地简化，每一次把数字拿下来一位，直到数字只剩下一位，就直接打印
> 
> Print（123）+4
> 
> Print(12)+3 +4
> 
> Print(1)+2 +3 +4
> 
> 1+2+3+4

**代码实现：**

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

**画图加深理解：**

**递归：递推+回归**

> （1）如果输入的值为1234，当n=1234时，大于9直接进入if语句，n/10又进入下一个Print函数，**注意这个时候printf("%d ", n % 10);这条语句是没有执行的，**
> 
> （2）进入下一个Print函数时，n=123，又进入if语句，n/10进入下一个Print函数，这个时候printf("%d ", n % 10);这条语句还是没有执行的，
> 
> （3）进入下一个Print函数时，n=12，又进入if语句，n/10进入下一个Print函数，这个时候printf("%d ", n % 10);这条语句仍然是没有执行的，
> 
> （4）进入下一个Print函数时，n=1，直接跳过if语句，打印1
> 
> **但是这个时候为啥只打印了1 呢？**
> 
> （5）因为前三次调用Print函数时最后一行代码都没走完，也就是递归**只完成了递推**这一层，还没有进行回归，下面再分别回去打印printf("%d ", n % 10);这条语句就是回归的过程，可能这样讲还是有点不明白，铁汁们再来结合着图来看看（**红色**代表**递推**的过程，**蓝色**代表**回归**的过程）

![2e6a6a007a684ae78a2e05b2428a5a54.png][]

现在我们再来看看前面介绍的什么是递归，就会好理解一些，我们就是通过把大事化小的思想，把程序重复的部分进行合并，大大减少了代码量

当n=123时**函数栈帧**的创建我们可以看到开辟了三次Print函数的空间，每一次调用都为这个Print函数调用了空间

![65acc02ecbcb422e94092107d88f05b2.png][]

再来思考一个**问题：**如果把if语句去掉，可以吗？

**答：**肯定是不可以的，如果去掉了，直接进去就打印Print函数，一直递归，结果就会死递归，这也就是递归的必要条件之一：限制条件

还有一个问题：如果把Print函数中的Print（n/10）改为Print（n）可以吗？

**答：**这也是不行的，n一直变，那么永远都是自己调自己，正是因为n在不断的减小而递推，才使Print函数可以不断的回归，这也就是递归的另一个必要条件：每次递归调用后不断接近限制条件

##### 2.2练习2： #####

> 编写函数不允许创建临时变量，求字符串的长度

我们先来看看 strlen函数求字符串的长度：**strlen函数的返回类型是size\_t**

> **size\_t是一种类型，是无符号整形**
> 
> **size\_t就是为sizeof设计的**
> 
> **size\_t类型的数据打印的时候要用%zd**

#include<stdio.h>
    #include<string.h>
    int main()
    {
    	char arr[] = "abc";
    	size_t len = strlen(arr);
    	printf("%zd", len);
    	return 0;
    }

其实这个题目就是模拟实现strlen函数

（1）**非递归**的方法实现strlen函数：我们看到在求长度时，创建了一个变量count，这就不符题意

#include<stdio.h>
    size_t my_strlen(char* arr)
    {
    	size_t count = 0;
    	while (*arr != '\0')
    	{
    		arr++;
    		count++;
    	}
    	return count;
    }
    int main()
    {
    	char arr[] = "abc";
    	size_t len = my_strlen(arr);//这里的arr传递的是数组首元素的地址
    	printf("%zd", len);
    	return 0;
    }

（2）**递归**的方法实现strlen函数：

> 运用把大事化小的思想：
> 
> my\_strlen("abc")
> 
> 1+my\_strlen("bc")
> 
> 1+1+my\_strlen("c")
> 
> 1+1+1+my\_strlen("")
> 
> 1+1+1+0

**代码实现：**

#include<stdio.h>
    size_t my_strlen(char* str)
    {
    	if (*str != '\0')
    		return 0;
    	else
    		return 1 + my_strlen(str + 1);
    }
    int main()
    {
    	char arr[] = "abc";
    	size_t len = my_strlen(arr);//这里的arr传递的是数组首元素的地址
    	printf("%zd", len);
    	return 0;
    }

**【温馨提示】：在函数递归中最好不要写++**，直接写str+1，因为str++和++str有很大的区别，如果这个代码函数递归部分写出return 1 + my\_strlen(str++)，将无法得出结果（因为后者++是先把str的值给赋进去，再++，这个过程就相当于一直str没变，也就没有结果）；这个地方应该写++str，但是不建议这样写，很容易出错，而且如果存在str返回的情况，这两种都会错误

**画图分析：**

> **递推：**
> 
> 当str指向a的时候，\*str为a，return 1 + my\_strlen(str+1)，进入下一次 my\_strlen函数
> 
> 下一次进入函数str指向b，仍然return 1 + my\_strlen(str+1)，继续进入下一次 my\_strlen函数
> 
> 再进入下一次函数str指向c，还是return 1 + my\_strlen(str+1)，进入下一次 my\_strlen函数
> 
> 这一次进入函数str指向\\0,return 0，就开始回归
> 
> **回归：**
> 
> 返回my\_strlen(str+1)=0，并加上倒数第三个自定义函数的1，return 1；
> 
> return 1又返回上一层my\_strlen(str+1)，并加上倒数第二个自定义函数的1，return 2；
> 
> return 2又返回上一层my\_strlen(str+1)，并加上倒数第一个自定义函数的1，return 3；
> 
> 最后将自定义函数的值传到main函数，打印结果

![4879f920cb68489c83df021e5dd2c61b.png][]

### 二、递归与迭代 ###

迭代简单理解：就是循环

##### 2.1练习3 #####

> 求n的阶乘（不考虑溢出）

在数学中，n<=1,阶乘为1；n>1,阶乘为n\*Fac（n-1）

5！=5\*4！（这样就可以简化代码，不至于从1乘到n）

**代码实现：**

#include<stdio.h>
    int Fac(int n)
    {
    	if (n <= 1)
    		return 1;
    	else
    		return n*Fac(n - 1);
    }
    int main()
    {
    	int n = 0;
    	scanf("%d", &n);
    	int r=Fac(n);
    	printf("%d", r);
    	return 0;
    }

但是这个代码还是存在问题：当输入值为100时，输出的结果却是0；当输入值为10000，直接就栈溢出了（原因就是这个递归函数一直递推，却没有回归，消耗了大量的栈区空间

我们可以将上面代码改为**迭代（循环）的方式**进行改进：

#include<stdio.h>
    int Fac(int n)
    {
    	int i = 0;
    	int r = 1;
    	for (i = 1; i <= n; i++)
    	{
    		r = r * i;
    	}
    	return r;
    }
    int main()
    {
    	int n = 0;
    	scanf("%d", &n);
    	int r = Fac(n);
    	printf("%d\n", r);
    	return 0;
    }

虽然这个代码求出的结果也会有错误，但是不会存在栈溢出的情况

这两个代码我们可以发现，递归其实可以用循环来代替，两者有利有弊

##### 2.2练习4 #####

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

**思路：** 数学公式

![21ba27fa02134744b67ee96f6164f7ea.png][]

**代码实现：**

#include<stdio.h>
    int Fbi(int n)
    {
    	if (n <= 2)
    		return 1;
    	else
    		return Fbi(n - 1) + Fbi(n - 2);
    }
    int main()
    {
    	int n = 0;
    	scanf("%d", &n);
    	int ret = Fbi(n);
    	printf("%d", ret);
    	return 0;
    }

但是这个代码还是存在**问题：**

> 当输入数字较大时，计算所需时间很长，一时半会出不来，比如：输入50，就需要算很久

> 我们来看看这个代码是**如何计算的：**
> 
> 当输入50，就需要计算49和48，计算49又需要计算48和47，计算48又需要47和46，以此类推，计算第50个斐波那契数需要大量计算，所以程序才会走这么久，我们会发现一个数字重复计算了多次，就浪费了很多的时间
> 
> 但是这个代码是**不存在栈溢出**的情况的：
> 
> 虽然存在这么多分支，但是递归的深度其实也就只有50，因为算第50个斐波那契数时，先算第49个斐波那契数，这个数没有算完，就不会进行下一个斐波那契数（也就是第48个数）的计算，以此类推，直到算完最左边这一条50到1，递归的深度也就只有50次，所以不会存在栈溢出的情况

![5f6e0d95e3e947b08cc1fafd5becb59f.png][]

我们可以将上面代码改为**迭代（循环）的方式**进行改进：

> 其实我们正常计算应该是从前往后算的，1，1，2，3，5，8，前面两个数相加等于第三个数，然后再循环，下一次循环就需要把第二个斐波那契数当作第一个数，第三个斐波那契数当作第二个数，这样进行相加，直到算到我们需要的数，循环停止

**代码实现：**

**【注意】：**c要初始化为1，不然输入的n为2时，不进入循环，直接就输出c初始化的值

#include<stdio.h>
    int Fbi(int n)
    {
    	int a = 1;
    	int b = 1;
    	int c = 1;
    	while (n > 2)
    	{
    		c = a + b;
    		a = b; 
    		b = c;
    		n--;
    	}
    	return c;
    }
    int main()
    {
    	int n = 0;
    	scanf("%d", &n);
    	int ret = Fbi(n);
    	printf("%d", ret);
    	return 0;
    }

这个代码的**优点**：计算快，不用重复计算

**缺点：**int类型存不下太大的数，数字大了就放不下了，结果就是错误的

**【总结】：**

> 如果使用递归很容易想到，写出来的代码没有明显的缺陷，那就可以使用递归的方法；但是如果递归的方法存在问题，比如:栈溢出，效率低下等，我们还是考虑用迭代（循环）的方法来解决问题，也可以采用static静态变量来减轻栈区空间不足的压力

这次函数递归的内容就到此啦，对于初学者这一块内容还是难理解的，题目也是比较难的，以后还会出一些相关内容：汉诺塔问题，青蛙跳台阶问题，这些都是函数递归的典型题目，有什么问题欢迎评论区或者私信交流，觉得笔者写的还可以，或者自己有些许收获的，麻烦铁汁们动动小手，给俺来个一键三连，万分感谢 !  
![a8feceaffb624f088c47f2f6d19c6853.jpeg][]

[bccd66dfc35b432e886f1c3ef98478d1.png]: https://img-blog.csdnimg.cn/bccd66dfc35b432e886f1c3ef98478d1.png
[b6da2f0c0b0b494886103e5feff93f9b.png]: https://img-blog.csdnimg.cn/b6da2f0c0b0b494886103e5feff93f9b.png
[2e6a6a007a684ae78a2e05b2428a5a54.png]: https://img-blog.csdnimg.cn/2e6a6a007a684ae78a2e05b2428a5a54.png
[65acc02ecbcb422e94092107d88f05b2.png]: https://img-blog.csdnimg.cn/65acc02ecbcb422e94092107d88f05b2.png
[4879f920cb68489c83df021e5dd2c61b.png]: https://img-blog.csdnimg.cn/4879f920cb68489c83df021e5dd2c61b.png
[21ba27fa02134744b67ee96f6164f7ea.png]: https://img-blog.csdnimg.cn/21ba27fa02134744b67ee96f6164f7ea.png
[5f6e0d95e3e947b08cc1fafd5becb59f.png]: https://img-blog.csdnimg.cn/5f6e0d95e3e947b08cc1fafd5becb59f.png
[a8feceaffb624f088c47f2f6d19c6853.jpeg]: https://img-blog.csdnimg.cn/a8feceaffb624f088c47f2f6d19c6853.jpeg