C++中将嵌套for循环逻辑转换为递归方法的实现方案咨询

通用实现思路 #

嵌套循环转递归本质是把每层循环的遍历逻辑拆成递归的维度递进，核心逻辑固定：

• 把每一层循环对应为递归的一个维度，各层当前遍历到的索引作为递归函数的入参
• 递归终止条件：最外层循环的索引超出上限，或是所有维度都遍历完成
• 递归推进逻辑：如果当前维度是最内层，执行业务逻辑后推进当前层索引；如果当前层索引遍历完成，就推进上一层索引并重置当前层索引为0

针对示例两层循环的最优实现 #

你给出的示例两层循环逻辑为：外层i遍历范围[0, 2n-1]，每固定一个i，内层j遍历范围[0, n-1]，最优递归实现完全对齐原循环的遍历顺序，没有额外冗余逻辑：

#include <iostream>
using namespace std;

void recursiveLoop(int n, int i = 0, int j = 0) {
    // 外层i遍历完成，终止递归
    if (i >= 2 * n) return;
    // 内层j遍历完成，推进i，重置j为0进入下一轮外层遍历
    if (j >= n) {
        recursiveLoop(n, i + 1, 0);
        return;
    }
    // 此处替换为原嵌套循环内的业务逻辑
    cout << "i = " << i << ", j = " << j << "\n";
    // 推进内层j索引
    recursiveLoop(n, i, j + 1);
}

int main() {
    int n = 2;
    recursiveLoop(n);
    return 0;
}

这个实现的时间复杂度和原循环完全一致，空间复杂度为O(n)（递归栈深度对应内层循环长度），没有额外的堆内存开销，是该场景下的最优写法。

可扩展任意层嵌套的通用实现 #

如果嵌套层数不固定，可以用数组存储各层循环的上限，通过维度参数控制递归层级，适配任意层数的嵌套循环场景：

#include <iostream>
#include <vector>
using namespace std;

void generalRecursiveLoop(const vector<int>& upperLimits, int dim = 0, vector<int> indices = {}) {
    // 所有维度遍历完成，执行业务逻辑
    if (dim == upperLimits.size()) {
        for (int idx : indices) cout << idx << " ";
        cout << "\n";
        return;
    }
    // 遍历当前维度所有可能的索引值
    for (int cur = 0; cur < upperLimits[dim]; cur++) {
        indices.push_back(cur);
        generalRecursiveLoop(upperLimits, dim + 1, indices);
        indices.pop_back();
    }
}

int main() {
    int n = 2;
    // 示例为两层循环，对应上限2n和n，新增层数只需往数组添加上限值即可
    vector<int> limits = {2 * n, n};
    generalRecursiveLoop(limits);
    return 0;
}

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