一、从数学到代码：杨辉三角的递归本质

杨辉三角，你肯定在数学课上见过。就是那个每个数等于它上方两数之和的三角形。但你知道吗？这个看似简单的数学结构，其实是理解递归的绝佳教材。

我个人习惯把杨辉三角看作「递归的活化石」。为什么这么说？因为它的定义本身就是递归的——每个位置的值依赖于它上方的两个值。这不就是递归的典型特征吗？

1.1 杨辉三角的数学定义

先来回顾一下杨辉三角的数学定义。假设我们用 f(row, col) 表示第 row 行第 col 列的值（从0开始计数），那么：

• 当 col == 0 或 col == row 时，值为 1
• 否则，f(row, col) = f(row-1, col-1) + f(row-1, col)

你看，这简直就是递归函数的天然模板。边界条件有了，递推关系也有了。剩下的就是把它翻译成C代码。

1.2 递归函数的直接翻译

根据上面的定义，我们可以写出最直接的递归版本：

// 计算杨辉三角中第 row 行第 col 列的值
int yanghui(int row, int col) {
    // 边界条件：左右两侧都是1
    if (col == 0 || col == row) {
        return 1;
    }
    // 递归：上方两数之和
    return yanghui(row - 1, col - 1) + yanghui(row - 1, col);
}

嗯，代码就这么简单。但别高兴太早——这个版本在实际运行中会有大问题。我在项目中遇到过类似的情况，当时用递归算斐波那契数列，结果 n=40 就卡得不行。杨辉三角的递归也是同样的毛病。

二、递归的代价：为什么简单版本不实用？

2.1 重复计算的噩梦

你想想看，上面的递归函数在计算 yanghui(4, 2) 时，会去调用 yanghui(3, 1) 和 yanghui(3, 2)。而 yanghui(3, 1) 又会去调用 yanghui(2, 0) 和 yanghui(2, 1)。这里面有多少重复计算？

我算过一笔账：计算第 20 行第 10 列的值，递归调用次数高达 184,756 次！而实际上我们只需要计算 20 行以内的值，总共也就 210 个不同的位置。说白了，99.9% 的计算都是浪费的。

2.2 递归深度限制

还有一个实际问题：C语言的函数调用栈是有限的。一般默认栈大小在 1MB 到 8MB 之间。每次递归调用都会消耗栈空间。对于杨辉三角，递归深度等于行数。如果行数超过几千，程序就会栈溢出崩溃。

所以，直接递归虽然代码简洁，但只适合小规模数据。实际项目中，我们需要对它进行优化。

三、优化方案：记忆化递归

3.1 用空间换时间

解决重复计算的办法很简单：把已经算过的结果存起来，下次直接用。这就是「记忆化递归」，也叫「备忘录法」。

#include <stdio.h>
#include <stdlib.h>

// 记忆化数组，-1 表示未计算
int **memo;

int yanghui_memo(int row, int col) {
    // 边界条件
    if (col == 0 || col == row) {
        return 1;
    }
    // 如果已经计算过，直接返回
    if (memo[row][col] != -1) {
        return memo[row][col];
    }
    // 递归计算并保存结果
    memo[row][col] = yanghui_memo(row - 1, col - 1) + yanghui_memo(row - 1, col);
    return memo[row][col];
}

// 生成杨辉三角的前 n 行
void generate_yanghui(int n) {
    // 分配记忆化数组
    memo = (int **)malloc(n * sizeof(int *));
    for (int i = 0; i < n; i++) {
        memo[i] = (int *)malloc((i + 1) * sizeof(int));
        for (int j = 0; j <= i; j++) {
            memo[i][j] = -1;  // 初始化为未计算
        }
    }
    
    // 计算并打印
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            printf("%d ", yanghui_memo(i, j));
        }
        printf("\n");
    }
    
    // 释放内存
    for (int i = 0; i < n; i++) {
        free(memo[i]);
    }
    free(memo);
}

3.2 记忆化递归的适用场景

记忆化递归不是万能的。它适合那些「子问题重叠度高」的问题。杨辉三角就是典型——每个位置被多个上层位置依赖。但如果是子问题几乎不重叠的情况，记忆化就没什么意义了。

我建议你记住一个判断标准：如果递归树中有大量重复节点，就用记忆化；如果递归树是链状的，直接递归就够了。

四、知识体系总览

下面这张图总结了杨辉三角递归生成的核心知识脉络：

五、实战：完整代码示例

下面是一个完整的可运行程序，它使用记忆化递归生成杨辉三角的前 N 行：

#include <stdio.h>
#include <stdlib.h>

int **memo;

int yanghui(int row, int col) {
    if (col == 0 || col == row) {
        return 1;
    }
    if (memo[row][col] != -1) {
        return memo[row][col];
    }
    memo[row][col] = yanghui(row - 1, col - 1) + yanghui(row - 1, col);
    return memo[row][col];
}

int main() {
    int n = 10;  // 生成前10行
    printf("杨辉三角前 %d 行：\n\n", n);
    
    // 分配记忆化数组
    memo = (int **)malloc(n * sizeof(int *));
    for (int i = 0; i < n; i++) {
        memo[i] = (int *)malloc((i + 1) * sizeof(int));
        for (int j = 0; j <= i; j++) {
            memo[i][j] = -1;
        }
    }
    
    // 打印杨辉三角
    for (int i = 0; i < n; i++) {
        // 打印前导空格，让三角形居中
        for (int k = 0; k < n - i - 1; k++) {
            printf("  ");
        }
        for (int j = 0; j <= i; j++) {
            printf("%4d", yanghui(i, j));
        }
        printf("\n");
    }
    
    // 释放内存
    for (int i = 0; i < n; i++) {
        free(memo[i]);
    }
    free(memo);
    
    return 0;
}

运行结果：

杨辉三角前 10 行：

                 1
               1   1
             1   2   1
           1   3   3   1
         1   4   6   4   1
       1   5  10  10   5   1
     1   6  15  20  15   6   1
   1   7  21  35  35  21   7   1
 1   8  28  56  70  56  28   8   1
1   9  36  84 126 126  84  36   9   1

六、总结与思考

杨辉三角的递归生成，让我看到了数学与编程的完美结合。递归不是银弹，但它确实是解决某些问题的优雅方式。关键在于：理解问题的递归本质，然后选择合适的实现策略。

我个人经验是：遇到递归问题，先问自己三个问题——

1. 边界条件是什么？（递归什么时候停止）
2. 递推关系是什么？（如何把大问题拆成小问题）
3. 子问题是否重复？（需不需要记忆化）

想清楚这三点，递归代码基本就写出来了。剩下的就是调优和测试。

---