Python递归生成N位格雷码实现详解

周予安

发布时间：2026-10-13| 3人浏览过

原创

本文介绍使用Python递归方法生成N位格雷码的实现方案。格雷码定义为相邻代码仅有一位二进制数不同的编码方式。文章提供了完整的递归函数代码，通过前缀添加0和1并反转列表的方式构建序列，并附带测试样例及运行结果，帮助开发者理解递归在编码生成中的应用。

本文分享一个使用Python实现生成格雷码功能的示例，供读者参考学习。

问题描述

在数字编码中，如果任意两个相邻的代码之间只有一位二进制数存在差异，这种编码被称为格雷码（Gray Code）。请编写一个函数，利用递归算法生成指定N位的格雷码。

解决方案思路

输入一个整数n，程序需返回n位格雷码的列表，输出顺序需从0开始递增。

测试用例

预期返回结果为：["0","1"]

题目看似简单但细节关键，题干简洁，样例直观。

关键在于发现格雷码生成的内在规律。

一旦掌握该规律，编写代码便水到渠成。

# -*- coding:utf-8 -*-
class GrayCode:
  def getGray(self, n):
    # write code here
    global maxn
    maxn = n
    return GrayCode.getGrace(self, ['0', '1'], 1)
  def getGrace(self, list_grace, n):
    global maxn
    if n >= maxn:
      return list_grace
    list_befor, list_after = [], []
    for i in xrange(len(list_grace)):
      list_befor.append('0' + list_grace[i])
      list_after.append('1' + list_grace[-(i + 1)])
    return GrayCode.getGrace(self, list_befor + list_after, n + 1)
gary = GrayCode()
print "本站测试结果："
print gary.getGray(3)

程序运行输出如下