函数的递归

心已赠人 2024-04-01 14:17 78阅读 0赞

#### 函数的递归 ####

*  一.递归的定义
 *  二.递归的条件
 *  三.递归的限制
 *  四.更深的理解

![在这里插入图片描述][d85e57ed0bbb41018b7ffa156e58ccba.png]

## 一.递归的定义 ##

> **程序调用自身的编程技巧称为递归**

![在这里插入图片描述][1fd3beb4a0b94c22a1e0498f336a1a98.png]  
**递归的主要思考方式是：把大事化小。**

例如：我们想要计算n的阶乘，我们可以这样写

void Factorial(int n)
    {
        
    	int i = 0;
    	int a = 1;
    	for (i = 1; i <= n; i++)
    	{
        
    		a = a * i;
    	}
    	printf("%d", a);
    }

我们用一个循环可以求出n的阶乘，但如果换成递归该怎么写呢？

**我们可以把n！拆分为n和(n-1)!**，这样就把一个问题拆分为两个小的问题

int Factorial(int n)
    {
        
    	if (n > 1)
    	    return n * Factorial(n - 1);
    	if (n == 1)
    		return 1;

我们知道当n=1时，那么它的阶乘就为1，那么我们就可以返回1，如果n>1，那么我们就把n拆分为n\*(n-1)!，我们就return n \* Factorial(n - 1)  
**Factorial(n - 1)是求出(n-1)的阶乘**,那么递归具体是如何运行的呢？

例如，我们令n=3

![在这里插入图片描述][07baff441b5946f9b9e2283baf0d6aa0.png]  
**我们可以发现函数是先递后归的，也就是它是从前至后运算，但它返回是从后至前**

## 二.递归的条件 ##

![在这里插入图片描述][32819a4a6035492aa390e179c4fcdc61.png]

> **像上题，n==1时就是它的限制条件，因为当n=1时，程序就不再进入函数，直接返回1；**  
> **n-1就是使n在每次调用后都更接近n=1这一限制条件，如果缺少这两个条件，那么这个递归就是错误的**

## 三.递归的限制 ##

![在这里插入图片描述][e26580405dda46ef84a7c02815bf61cb.png]  
![在这里插入图片描述][f557b2ae2da44fde9b8b864d78e8f12c.png]  
我们可以比较这两种写法，第一张图是用循环写的，当n特别大时，虽然不能计算出正确的值(那是因为int只能容纳一定的数，它超出了)，但程序并未崩溃。第二张图是用递归写的，程序并未给出任何结果，程序崩溃了(栈溢出)。由此可以看出，递归如果次数过多，就很容易导致程序崩溃。

> **简而言之，写循环废人，但有利于计算机；写递归，废计算机，但方便人**

## 四.更深的理解 ##

> **想要更好的理解递归，需要了解[二叉树][Link 1]和[函数栈帧][Link 2]，再自己多画画递归图和做题，再递归理解清楚后就会发现递归真的很好用。**

![在这里插入图片描述][3e2bff30474941f6a27927a201e68973.png]

[d85e57ed0bbb41018b7ffa156e58ccba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/903d1b13a69147258d482e3ae19315e5.png
[1fd3beb4a0b94c22a1e0498f336a1a98.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/9827f9a362b44e0ba83b94c61fb19c10.png
[07baff441b5946f9b9e2283baf0d6aa0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/774a13bace004dfe96394a9e97285ccc.png
[32819a4a6035492aa390e179c4fcdc61.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/9d8624fabcb74faf926c8df414f5d614.png
[e26580405dda46ef84a7c02815bf61cb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/2ca57b1e396b431c8da1f4d34510d807.png
[f557b2ae2da44fde9b8b864d78e8f12c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/782129c6a8c1476083074907d5e85911.png
[Link 1]: http://t.csdn.cn/hd3gt
[Link 2]: http://t.csdn.cn/pquij
[3e2bff30474941f6a27927a201e68973.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/58e8d560dc6544419663212344e5519a.png