10. 栈的应用（二）：函数调用栈与递归、递归转非递归（汉诺塔）、深度优先搜索（DFS）基础

各位同学，咱们接着聊栈。上一节我们讲了栈的基本操作和表达式求值，今天要聊的这几个话题，其实才是栈真正发光发热的地方。函数调用栈、递归、DFS——说白了，它们背后都是同一个东西在支撑：后进先出。

10.1 函数调用栈：你写的每一行代码，都在用它

你有没有想过，当你写一个函数调用另一个函数时，CPU是怎么知道执行完要回到哪里的？

答案就是栈。每个函数被调用时，系统会往栈里压入一个“栈帧”。这个栈帧里存了什么？返回地址、局部变量、参数……等函数执行完，这个栈帧就被弹出，CPU根据返回地址跳回去继续执行。

我当年刚入行时，遇到一个诡异的bug：一个嵌入式设备跑着跑着就重启了。查了三天，最后发现是一个递归函数把栈给撑爆了。嗯，从那以后，我对栈的大小就特别敏感。

看个简单的例子：

void funcB() {
    int b = 2;
    printf("B: %d\n", b);
}

void funcA() {
    int a = 1;
    funcB();
    printf("A: %d\n", a);
}

int main() {
    funcA();
    return 0;
}

执行流程是这样的：

1. main 被调用，压栈
2. main 调用 funcA，压栈
3. funcA 调用 funcB，压栈
4. funcB 执行完，弹栈
5. funcA 继续执行，完事后弹栈
6. main 结束，弹栈

你看，这就是栈的典型应用。后调用的函数先返回，完全符合LIFO特性。

10.2 递归的本质：函数调用自己，栈帧一层层叠

递归为什么能用栈来解释？因为递归就是函数调用自己，每次调用都会产生一个新的栈帧。递归深度就是栈帧的层数。

我见过不少新手写递归，写着写着就忘了终止条件，结果栈溢出。其实你只要记住：递归必须有两个部分——终止条件和递推关系。

举个经典的阶乘例子：

int factorial(int n) {
    if (n <= 1) return 1;  // 终止条件
    return n * factorial(n - 1);  // 递推关系
}

当 factorial(5) 被调用时，栈里会依次压入：

factorial(5) → factorial(4) → factorial(3) → factorial(2) → factorial(1)

然后从 factorial(1) 开始依次返回，逐层弹栈。

10.3 汉诺塔：递归转非递归，栈的经典实战

汉诺塔问题，大家应该都听过。三个柱子，一堆盘子，要把所有盘子从A移到C，每次只能移一个，大盘不能压小盘。

递归解法非常优雅：

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", from, to);
        return;
    }
    hanoi(n - 1, from, aux, to);
    printf("Move disk %d from %c to %c\n", n, from, to);
    hanoi(n - 1, aux, to, from);
}

但问题来了：如果盘子数量很大（比如64个），递归深度就是64层。虽然64层对现代计算机来说不算什么，但在嵌入式环境里，栈空间可能只有几KB，64层递归很可能就爆了。

所以，我们需要把递归转成非递归。怎么做？用栈模拟递归过程。

思路是这样的：把每次递归调用的状态（当前层数、三个柱子）打包成一个结构体，压入栈中。然后循环处理栈顶元素，直到栈为空。

typedef struct {
    int n;
    char from, to, aux;
    int stage;  // 0: 还没处理, 1: 已处理左子树, 2: 已处理完
} HanoiState;

void hanoi_nonrecursive(int n, char from, char to, char aux) {
    HanoiState stack[100];
    int top = -1;
    
    stack[++top] = (HanoiState){n, from, to, aux, 0};
    
    while (top >= 0) {
        HanoiState *cur = &stack[top];
        
        if (cur->n == 1) {
            printf("Move disk 1 from %c to %c\n", cur->from, cur->to);
            top--;
            continue;
        }
        
        if (cur->stage == 0) {
            cur->stage = 1;
            stack[++top] = (HanoiState){cur->n - 1, cur->from, cur->aux, cur->to, 0};
        } else if (cur->stage == 1) {
            printf("Move disk %d from %c to %c\n", cur->n, cur->from, cur->to);
            cur->stage = 2;
            stack[++top] = (HanoiState){cur->n - 1, cur->aux, cur->to, cur->from, 0};
        } else {
            top--;
        }
    }
}

这段代码的核心思想是：用 stage 字段标记当前状态，模拟递归中的“调用前”和“调用后”。说白了，就是把递归的隐式栈变成了显式栈。

10.4 深度优先搜索（DFS）基础：栈就是DFS的天然搭档

DFS，深度优先搜索，说白了就是“一条路走到黑，走不通再回头”。这种“回头”的行为，正好对应栈的弹栈操作。

DFS有两种实现方式：递归和显式栈。递归实现其实就是隐式地用函数调用栈，显式栈实现则是我们自己维护一个栈。

看个简单的图遍历例子：

// 邻接表表示的图
#define MAX_NODES 100
int graph[MAX_NODES][MAX_NODES];
int visited[MAX_NODES];

void dfs_recursive(int node) {
    visited[node] = 1;
    printf("Visited: %d\n", node);
    
    for (int i = 0; i < MAX_NODES; i++) {
        if (graph[node][i] && !visited[i]) {
            dfs_recursive(i);
        }
    }
}

void dfs_stack(int start) {
    int stack[MAX_NODES];
    int top = -1;
    
    stack[++top] = start;
    
    while (top >= 0) {
        int node = stack[top--];
        
        if (visited[node]) continue;
        visited[node] = 1;
        printf("Visited: %d\n", node);
        
        // 把邻接节点压栈（注意顺序，后进先出）
        for (int i = MAX_NODES - 1; i >= 0; i--) {
            if (graph[node][i] && !visited[i]) {
                stack[++top] = i;
            }
        }
    }
}

你发现没有？递归版的DFS和显式栈版的DFS，本质是一样的。递归版靠系统栈，显式版靠我们自己管理的栈。

我在实际项目中用DFS做过路径规划。一个机器人要在迷宫里找出口，用DFS配合栈，每次走到死胡同就回溯，直到找到出口。栈里保存的就是当前走过的路径，弹栈就是回溯。

10.5 知识体系总览

下面这张图，把今天讲的内容串起来了：

你看，函数调用栈、递归、DFS，这三者其实是一脉相承的。函数调用栈是系统帮我们管理的栈，递归是函数调用栈的典型应用，而DFS则是栈在算法中的直接体现。

我个人觉得，理解了栈，你就理解了程序执行的底层逻辑。不管是调试bug、优化性能，还是设计算法，栈都是绕不开的基础工具。

好了，今天的内容就到这里。栈的应用远不止这些，但函数调用栈、递归、DFS这三个，已经足够让你感受到栈的魅力了。下次写递归函数时，想想背后那个默默工作的栈，你会对代码有更深的理解。

---