【C语言】递归的内存占用过程

递归

递归是函数调用自身的一种编程技术。在C语言中，递归的实现会占用内存栈（Call Stack），每次递归调用都会在栈上分配一个新的 “栈帧（Stack Frame）”，用于存储本次调用的函数局部变量、返回地址、参数等信息。简单点说：自己调自己。

顾名思义：

例子： 
    fun(void)
    {
        //一定要有结束条件 
        fun()
    }
    
例子： 
	从 1 + 2 + 3 + ... + 100

函数递归的缺陷： 非常耗内存 不建议在函数中使用递归，如果将栈的内存耗尽，程序执行会出现报错：Segmetation fault (core dumped)

那么，在递归的过程中到底发生了什么事情呢？以下将通过文字解析和图示说明递归对内存的占用情况，让大家直观的看见递归的过程。

栈帧（Stack Frame）的组成

每次函数调用（包括递归调用），都会在内存栈区中分配一个栈帧，主要用于存储以下内容：

函数参数：函数调用时传入的参数。
返回地址：函数执行完后需要返回到调用函数的位置，返回地址存储在栈帧中。
局部变量：函数内部定义的局部变量。
其他信息：如寄存器保存、栈指针、帧指针等（具体取决于编译器和硬件架构）。

递归调用时，每次调用都会创建一个新的栈帧，压入到内存栈中。递归结束时，函数逐层返回，栈帧依次弹出释放。

递归的内存占用过程

代码一：（上述示例）
使用递归的方式从 1 + 2 + 3 + … + 100 ：
递归分析
递归代码
代码图示
下面举一个更复杂的例子。
代码二：

#include <stdio.h>

void recursiveFunction(int n) {
    if (n == 0) {
        printf("Recursion ends.\n");
        return;
    }
    printf("Entering recursion: n = %d\n", n);

    // 递归调用
    recursiveFunction(n - 1);

    printf("Exiting recursion: n = %d\n", n);
}

int main() {
    recursiveFunction(3);
    return 0;
}

执行过程分析：

初次调用 recursiveFunction(3)，程序会在栈中分配一个栈帧，用于存储 n = 3 的值。
函数内部调用 recursiveFunction(2)，再次分配栈帧，存储 n = 2。
如此递归，直到 n = 0，递归结束，开始逐层返回，栈帧依次弹出。

图示解析（递归占用内存的变化）

假设每个栈帧包含以下内容：

函数参数 n。
函数的返回地址。
函数内部的局部变量（假设没有其他局部变量）。

调用栈变化过程

1. 初始状态（main 函数调用 recursiveFunction(3)）：

|--------------------|
|  main() Frame      |  <-- 栈顶
|--------------------|

2. 第一次递归调用（recursiveFunction(3)）：

|--------------------|
|  recursiveFunction |
|  参数: n = 3       |
|  返回地址: main()  |
|--------------------|
|  main() Frame      |
|--------------------|

3. 第二次递归调用（recursiveFunction(2)）：

|--------------------|
|  recursiveFunction |
|  参数: n = 2       |
|  返回地址: recursiveFunction(3) |
|--------------------|
|  recursiveFunction |
|  参数: n = 3       |
|  返回地址: main()  |
|--------------------|
|  main() Frame      |
|--------------------|

4. 第三次递归调用（recursiveFunction(1)）：

|--------------------|
|  recursiveFunction |
|  参数: n = 1       |
|  返回地址: recursiveFunction(2) |
|--------------------|
|  recursiveFunction |
|  参数: n = 2       |
|  返回地址: recursiveFunction(3) |
|--------------------|
|  recursiveFunction |
|  参数: n = 3       |
|  返回地址: main()  |
|--------------------|
|  main() Frame      |
|--------------------|

5. 第四次递归调用（recursiveFunction(0)）：

|--------------------|
|  recursiveFunction |
|  参数: n = 0       |
|  返回地址: recursiveFunction(1) |
|--------------------|
|  recursiveFunction |
|  参数: n = 1       |
|  返回地址: recursiveFunction(2) |
|--------------------|
|  recursiveFunction |
|  参数: n = 2       |
|  返回地址: recursiveFunction(3) |
|--------------------|
|  recursiveFunction |
|  参数: n = 3       |
|  返回地址: main()  |
|--------------------|
|  main() Frame      |
|--------------------|

6. 递归返回（n = 0 开始返回）：

栈帧逐层弹出，释放内存，最终只剩下 main() 的栈帧。

递归的内存占用与栈深度

递归深度与内存占用的关系

每次递归调用会分配一个新的栈帧，因此递归深度越大，占用的栈内存越多。
如果递归深度过大，可能导致栈溢出（Stack Overflow）。

栈溢出代码：

#include <stdio.h>

void recursiveFunction(int n) {
    printf("n = %d\n", n);
    recursiveFunction(n + 1);  // 无限递归
}

int main() {
    recursiveFunction(1);
    return 0;
}

运行上述程序会导致栈溢出，因为递归调用的栈帧无限增长，超过了栈的容量。

ulimit -a // 自行查看 stack size 栈的内存空间大小，开发过程中注意栈的使用量

优化递归的内存占用

1. 尾递归优化

尾递归是指递归调用发生在函数的最后一步，编译器可以优化为循环，避免创建多个栈帧。
代码：

#include <stdio.h>

void tailRecursiveFunction(int n, int result) {
    if (n == 0) {
        printf("Result: %d\n", result);
        return;
    }
    tailRecursiveFunction(n - 1, result + n);
}

int main() {
    tailRecursiveFunction(5, 0);  // 计算 1+2+3+4+5
    return 0;
}

尾递归可以被优化为循环，避免栈溢出。

2. 转换为迭代

如果递归深度过大，可以将递归转换为迭代，用循环替代递归。
代码：

#include <stdio.h>

void iterativeFunction(int n) {
    while (n > 0) {
        printf("n = %d\n", n);
        n--;
    }
}

int main() {
    iterativeFunction(5);
    return 0;
}