C++利用递归实现格雷码的生成

在C++中，格雷码（Gray Code）是一种二进制数字序列，相邻两个数之间仅有一位不同。递归是一种很好的方式来生成格雷码，特别是当每个位置的改变只影响其前一位的值时。以下是使用递归思想在C++中生成格雷码的一个简单示例：

#include <iostream>
#include <vector>

std::vector<int> grayCode(int n) {
    std::vector<int> result;
    if (n == 0) { // 基础情况：长度为1的格雷码只有一个元素0
        result.push_back(0);
    } else {
        // 通过将当前位的格雷码与前一位置格雷码相加（异或操作），生成新位的格雷码
        for (int i = 0; i < (1 << n); ++i) {
            result.push_back(grayCode(n - 1)[i] ^ grayCode(n - 1)[i >> 1]);
        }
    }
    return result;
}

// 示例：打印8位格雷码
int main() {
    int bits = 3; // 生成3位格雷码（共8个）
    std::vector<int> code = grayCode(bits);
    for (int Gray : code) {
        std::cout << Gray << " ";
    }
    std::cout << "\n";
    return 0;
}

在这个例子中，`grayCode`函数接受一个整数n表示要生成的格雷码的位数。递归地调用自身，每次减少一位，并结合每一位的原码和前一位的格雷码，直到达到基础情况n=0。