递归的入门

电玩女神 2023-09-26 10:45 50阅读 0赞

### 函数递归入门学习 ###

*   *   *  1.介绍递归
         *   *  1.什么是递归
             *  2.递归的两个必要条件
         *  2.实现递归（简单练习题）
         *   *  1.接下来我先带大家了解一下不用递归的解法
             *  4.用递归
         *  3.递归实现斐波那契数列
         *   *  1.介绍斐波那契数列
             *  2.不用递归完成斐波那契数列（不太易懂，后面的可以选择跳过）

### 1.介绍递归 ###

> 递归，分成两个字来解读的话就是递（递推）不断地推进，归（回归）将得到的值传递回原函数.

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

程序调用自身的编程技巧称为递归（recursion）  
递归是用来将那些大型复杂的问题层层转化为与原问题相似的规模较小的问题来求解。  
只需要少量的程序就可以描述出解题过程所需要的多次重复计算，大大减少了代码量！！！

> 主要思想就是：大事化小

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

1.存在限制条件，当满足这个限制条件，递归将不再继续，意思如下图：  
![在这里插入图片描述][08b7865e664d4b8ea7403d4e7e3523c2.png]  
大家看见了，当我们的a<10的时候我们就不再进行下面的print函数了，又因为返回类型是void所以我们打印完a就可以回到上一个函数

2.每次递归后越来越接近这个限制目标（后面讲解）

### 2.实现递归（简单练习题） ###

我们先来完成一个简单的练习题

> 接受一个无符号整型值，按照顺序打印他的每一位

#### 1.接下来我先带大家了解一下不用递归的解法 ####

![在这里插入图片描述][673e4d44601d44bd8ff5098188a6d26b.png]  
到下面的循环判断条件是a，当a不为0时为真，当a为0时就是假退出循环，但其实这样做不太好因为会改变a本身的值，更好的情况是将a存起来，再去对a进行修改,由于这道题修改a没什么影响，所以就这样写了。  
![在这里插入图片描述][b09e0d201c824c16ba4d488d682f31e6.png]  
大概的意思如下图（当然我们的主要任务是讲解递归，我就草草的解释一下）  
![在这里插入图片描述][57ceab6583ed478ea953b859011380bb.png]

右边的红框是解析，左边的黄框是过程，这个大概就是不用递归完成的练习题，是不是有点麻烦呀，还有一种方法用数组去完成这个练习题，这个就不再去讲解了

#### 4.用递归 ####

我先将代码给大家打印出来

void  print(unsigned int a)
    {
        
    	if (a > 9)
    	{
        
    		print(a / 10);
    	}
    	printf("%u ", a % 10);
    }
    int main()
    {
        
    	unsigned int a = 0;
    	scanf("%u", &a);
    	print(a);
    	return 0;
    }

大家可能不了解这个代码的意思，但是可以发现，我们在print函数里面又进行了调用print函数

> 注意！！！print是自定义函数，printf才是库函数

那大家看上面的代码是不是就符合我们写递归的两个必要条件  
1.存在限制条件，当满足这个限制条件函数递归将不再继续，  
![在这里插入图片描述][f73817978efa466ab31188c0df3836e5.png]

也就是当我们的a<9时便不再进行函数调用，而是经过下面的函数打印之后返回上一个函数，因为是void类型所以不需要返回值,打印函数执行完毕自己就会返回  
2.每次递归后越来越接近这个目标  
大家可以看到，我们假设刚开始的a是1234，那么进入函数之后如图所示  
![在这里插入图片描述][302e22919aaf47eeb1ee9c7dc801ce7c.png]  
这个是我们的主函数，假设我们输入的a为1234时  
![在这里插入图片描述][d0d34ecda833428580c2f5869974d4dc.png]  
大家看到我们的红色线条，总共进行了四次，每一次我们的a都更接近小于10的值，直到最后为1，不再进行函数调用，这个是递推，下面就是回归了  
![在这里插入图片描述][ade0d09ca9ec4a43990cafe61d539831.png]  
画的有点丑，紫色线条就是回归，我们先打印1，打印1之后返回上面的函数打印2，因为12%10=2，再之后继续如紫色线条的路径进行打印，直到最后返回主函数，这个就是用递归进行整形数字按顺序打印，结果如下  
![在这里插入图片描述][048526272f5f4763be89b6f4fb03f68b.png]  
想要写一个递归函数必须具备上面两个必要条件，如果不具备这两个必要条件一定不是递归。

### 3.递归实现斐波那契数列 ###

#### 1.介绍斐波那契数列 ####

> 斐波那契数：斐波那契数列指的是1、1、2、3、5、8、13、21、······这样一个数列，我们可以发现它后面的一个数是前两个数之和。而在这个数列中的数就被称为斐波那契数。

关于斐波那契数列的空间复杂度和时间复杂度，等博主后续学习的知识更加多的时候再去进行讲解，这里我们先完成斐波那契数列的递归算法

#### 2.不用递归完成斐波那契数列（不太易懂，后面的可以选择跳过） ####

代码如下

#include<stdlib.h>
    int Fib(int a)
    {
        
    	int* p = NULL;
    	p=(int*)malloc(sizeof(int) * (a + 1));//开辟一个空间存放数组，
    	if (p == NULL)//空间开辟失败直接返回0
    	{
        
    		return 0;
    	}
    	p[1] = 1;
    	p[2] = 1;
    	int i = 0;
    	for (i = 3; i <= a; i++)
    	{
        
    		p[i] = p[i - 1] + p[i - 2];//前一项和前二项之和
    	}
    	return p[a];
    }
    int main()
    {
        
    	int a = 0;//输入想要求到第几项的斐波那契数列
    	scanf("%d", &a);
    	//这里用函数完成斐波那契数列
    	int ret=Fib(a);
    	printf("%d ", ret);
    	return 0;
    }

![在这里插入图片描述][72acfaa9fbbb4e2abcb66bdcef4c7553.png]  
p\[0\]的位置由于我们的第一项是从1开始的，所以便不用对他进行修改，即使是随机数也没关系，因为用不到，  
大家看到，第一项加第二项为第三项，那么第二项加第三项又为第四项，就这样重复，后面一项等于前两项之和，便是斐波那契数列，因为我们用的是数组，所以时间复杂度就是O(n)（牺牲空间换取时间）,如果用递归的话，时间复杂度就是O(2^n),关于时间复杂度，大家可以去看关于时间复杂的想关信息，给大家举个例子吧，如果我要求第50项的斐波那契数列，那么我们的第一种解法也就是不用递归的需要进行50次，但是，我们的第二种解法也就是递归算法计算第50项需要进行百万亿次计算！！！，是不是不可思议，好了，先不跟大家讲这个了，我们回归正题  
下面是递归的代码

#include<stdlib.h>
    int Fib(int a)
    {
        //1 1 2 3 5 8 13 21
    	if (a < 3)//当a小于3时斐波那契数为1
    	{
        
    		return 1;
    	}
    	return Fib(a - 1) + Fib(a - 2);
    }
    int main()
    {
        
    	int a = 0;//输入想要求到第几项的斐波那契数列
    	scanf("%d", &a);
    	//这里用函数完成斐波那契数列
    	int ret = Fib(a);
    	printf("%d ", ret);
    	return 0;
    }

大家是不是可以发现，代码量好少才就短短几行，没错递归的优势就是大大减少了代码量，将大的问题层层化简为与原规模相似的小问题，接下来上画图讲解  
![在这里插入图片描述][2ca1d35dc8764a1bb6f2aa1561e5e7c3.png]  
这个就是，斐波那契数列的画图，这是第5项，当我们求第五项时，就化简为求一个第三项和一个第四项，再层层化简，直到Fib(1)和Fib(2)因为这两个数都是1，将一个大问题层层化简为小问题，上述的if判断是因为a<3时，也就是第一项和第二项都是1，所以直接返回1，不再进行函数调用，这个就是用递归的解法进行斐波那契数列的代码，以及概念，给大家看看最后输出的结果  
![在这里插入图片描述][c35aa75daa044551a8e9a660182d824a.png]  
其实这篇博客我自己写的也不是很好，自己感觉的到，不知道怎么去简洁地形容递归，后续如果有机会，会再写汉诺塔或者是青蛙跳台等函数递归解法，

[08b7865e664d4b8ea7403d4e7e3523c2.png]: https://img-blog.csdnimg.cn/08b7865e664d4b8ea7403d4e7e3523c2.png
[673e4d44601d44bd8ff5098188a6d26b.png]: https://img-blog.csdnimg.cn/673e4d44601d44bd8ff5098188a6d26b.png
[b09e0d201c824c16ba4d488d682f31e6.png]: https://img-blog.csdnimg.cn/b09e0d201c824c16ba4d488d682f31e6.png
[57ceab6583ed478ea953b859011380bb.png]: https://img-blog.csdnimg.cn/57ceab6583ed478ea953b859011380bb.png
[f73817978efa466ab31188c0df3836e5.png]: https://img-blog.csdnimg.cn/f73817978efa466ab31188c0df3836e5.png
[302e22919aaf47eeb1ee9c7dc801ce7c.png]: https://img-blog.csdnimg.cn/302e22919aaf47eeb1ee9c7dc801ce7c.png
[d0d34ecda833428580c2f5869974d4dc.png]: https://img-blog.csdnimg.cn/d0d34ecda833428580c2f5869974d4dc.png
[ade0d09ca9ec4a43990cafe61d539831.png]: https://img-blog.csdnimg.cn/ade0d09ca9ec4a43990cafe61d539831.png
[048526272f5f4763be89b6f4fb03f68b.png]: https://img-blog.csdnimg.cn/048526272f5f4763be89b6f4fb03f68b.png
[72acfaa9fbbb4e2abcb66bdcef4c7553.png]: https://img-blog.csdnimg.cn/72acfaa9fbbb4e2abcb66bdcef4c7553.png
[2ca1d35dc8764a1bb6f2aa1561e5e7c3.png]: https://img-blog.csdnimg.cn/2ca1d35dc8764a1bb6f2aa1561e5e7c3.png
[c35aa75daa044551a8e9a660182d824a.png]: https://img-blog.csdnimg.cn/c35aa75daa044551a8e9a660182d824a.png