递归计算谢尔宾斯基地毯各阶正方形数量的技术问题

嘿，我来帮你解决谢尔宾斯基地毯的正方形计数问题！先给你梳理清楚规律，再把代码逻辑补全。

你给出的序列1、9、73、585、4681藏着清晰的递推关系：每一步的正方形总数等于前一步总数的8倍再加1，用公式表示为：
f(deep) = 8 * f(deep-1) + 1
初始条件为 f(0) = 1（对应未细分的初始正方形）

甚至可以推导出通项公式，不用递归也能直接计算：
f(deep) = (8^(deep+1) - 1) / 7
验证几个值：

• deep=0：(8¹-1)/7 = 1 ✔️
• deep=1：(8²-1)/7 = 63/7 =9 ✔️
• deep=2：(8³-1)/7=511/7=73 ✔️
  完全匹配你给出的数值！

回到你的printSquares方法，要让它同时绘制地毯并返回对应deep的正方形总数，只需要在递归逻辑中加入计数逻辑即可。核心思路：

1. 当deep=0时，仅绘制1个正方形，返回数量1；
2. 当deep>0时，先把当前大正方形计入总数，然后递归处理周围8个小正方形（跳过中间空白的那个），累加每个递归返回的子数量。

补全后的代码如下：

private int printSquares(Graphics g, int xi, int yi, int width, int height, int deep) {
    // 基础情况：deep为0，绘制单个正方形并返回数量1
    if (deep == 0) {
        g.fillRect(xi, yi, width, height);
        return 1;
    }

    int subW = width / 3;
    int subH = height / 3;
    int totalSquares = 1; // 当前层级的大正方形算1个

    // 遍历3x3的子区域，跳过中间的空白区域
    for (int row = 0; row < 3; row++) {
        for (int col = 0; col < 3; col++) {
            // 跳过中间的子正方形（第2行第2列，索引从0开始）
            if (row == 1 && col == 1) {
                continue;
            }
            // 计算子正方形的起始坐标
            int newXi = xi + col * subW;
            int newYi = yi + row * subH;
            // 递归绘制子正方形，并累加数量
            totalSquares += printSquares(g, newXi, newYi, subW, subH, deep - 1);
        }
    }

    return totalSquares;
}

调用这个方法时，传入对应的deep值，就能同时完成地毯绘制和正方形计数。如果只是单纯需要计算数量，直接用通项公式会更高效，无需走递归流程~

内容的提问来源于stack exchange，提问作者Fred Costa