c语言之堆栈溢出问题

逃离我推掉我的手 2022-12-25 13:56 216阅读 0赞

### 目录） ###

*  1.函数的调用，系统所作的工作
 *  2.函数调用时与内存管理
 *  3.递归函数

# 1.函数的调用，系统所作的工作 #

对于c来说，函数调用，系统要做三个工作：

*  1.函数在执行过程中，一但遇到函数调用，系统首先为每个形参分配存储单元，并计算实参表达式的值，然后把实参复制到对应形参的存储单元，实参和形参按照顺序一一对应
 *  2.将控制转移到被调用的函数，执行其函数体内的语句
 *  3.当执行到return语句或者函数结尾时，控制返回到调用函数，如果有返回值，回送一个值并返回控制，然后从函数调用点继续执行。函数调用点指的是：若函数调用出现在表达式中，则调用点是该表达式，若函数调用单独中作为一个语句出现，则返回时执行该语句的下一条语句。

**这里多提一下，关于数组作为形参调用函数时，为什么需要连同数组长度一起传进来？**  
这里是因为，数组作为参数传递的本质只是一个指针，也就是一个地址，编译器并不关心这个地址后边有多少有用数据，编译器只看得到指针所指的数据。所以在被调用函数中，无法直接知道这个数组的长度，所以当被调用函数想要使用数组长度时，最方便就是将数组长度作为形参传递进来，进而可以在传进来的数组的指针处依次往后读取数组长度个的数据。

# 2.函数调用时与内存管理 #

函数调用时，系统内存通常分为代码区、数据区和堆栈区，具体如下图：  
![在这里插入图片描述][20201205112304723.png]  
其中代码区和常量存储区属于只读存储区，用来存放程序代码和部分常量；静态存储区用来存放外部变量和静态局部变量，堆区是程序进行动态分配管理的内存区域；栈区是在函数调用过程中存放函数局部变量、函数参数和返回地址信息的内存区域。堆区和栈区通常合称为堆栈，属于动态存储区。

**系统在进行函数调用时需要用到堆栈**，堆栈是一种“**后进先出**”的数据结构。当程序调用一个函数时，被调函数必须知道如何返回到主调函数，所以主调函数的返回地址必须压入函数调用栈。如果发生了一系列的函数调用，其对应的一组返回地址将按照后进先出的顺序压入到函数调用栈，这样每个函数才能正确的返回到它的主调函数。

**函数的每次调用通常会产生一些局部变量，这些局部变量会保存在函数调用栈中**，这些数据被称为函数调用的活动记录。当发生一次函数调用时，它所对应的活动记录将被压入函数调用栈。当函数调用结束后返回到主调函数后，它对应的活动记录将被弹出函数调用栈，保存在其中的局部变量将不能被程序所访问。

**函数调用栈中用来保存活动记录的存储单元的总数有一个上限，如果连续发生的多次函数调用产生的活动记录超过了这一上限，将会发生堆栈溢出的错误。**

# 3.递归函数 #

> 递归函数就是直接或者通过其他函数间接的调用自己的函数。

下面以阶乘的递归函数进行介绍，

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

在main函数中有fact(4)调用，函数递归求解的过程如下所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70]  
根据上面关于函数调用和内存管理的概念，每调用一次递归函数，系统就在栈区为该函数的相关数据分配相应的存储空间，也就时入栈。当调用fact(4)，会将fact(4)，fact(3)，fact(2)，fact(1)的活动记录依次入栈，当调用fact(1)时，返回值为1，此时函数调用结束，fact(1)出栈，返回到函数调用点也就是2*fact(1)；接着fact(2)出栈，返回值2返回到到函数调用点3*fact(2)；接着fact(3)出栈，返回值6返回到函数调用点4\*fact(3)；接着fact(4)出栈，返回值24返回到main函数调用点。

有了上面的理解，我们可以看出**递归调用程序包括两部分**：

*  递归循环继续的过程
 *  递归调用结束的过程

**递归函数的形式**一般为：

if(递归终止条件成立)
    	return 递归公式的初值；
    else
    	return 递归函数调用返回的结果值；

**设计递归函数的注意点**：

*  注意防止递归调用无终止的进行，必须在函数内有终止递归调用的手段和递归出口，即到何时不再递归调用下去
 *  设计递归程序的时候，不要把眼光局限于实现细节，否则很难理出头绪，编写的程序只给出运算规律，具体实现细节应该让计算机去处理。
 *  复杂递归问题中，找出递归式子是关键，不要陷入实现细节的泥沼中。

**最近共同祖先应用案例**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 1]  
从图中可以看出孩子和双亲的关系，如果双亲编号为i，则左孩子编号为2*i，右孩子编号为2*i+1。  
在寻找两个结点最近公共祖先的过程，每次让比较大的数走向他们的双亲，直到他们相等，这个过程可以用递归实现：

int common(int x, int y)
    { 
        if(x == y)
            return x;
        if(x > y)
            return common(x/2, y);
        return common(x, y/2);      
    }

参考：  
c语言程序设计(第二版）甘勇

[20201205112304723.png]: /images/20221120/60bde24d847849e983fb0e23ff9c45a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70]: /images/20221120/b940fff68e484c0d8191e73afa71f859.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201205171246674.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2,size_16,color_FFFFFF,t_70