如何实现生成无相邻1的n位0-1序列？递归思路求指引

嘿，其实这个问题非常适合用递归解决，可能你只是还没摸到递归的核心逻辑～我给你拆解下思路，顺便也提个迭代的方法作为补充：

一、递归的核心切入点 #

递归的关键在于每一步的选择依赖于前一步的结果，我们可以这样设计递归逻辑：

• 终止条件：当当前生成的序列长度等于n时，直接输出这个序列。
• 分支选择：
  • 如果是第一次构建序列（还没有任何字符），那么第一个字符可以选0或者1，分别开启两个递归分支。
  • 如果当前序列的最后一个字符是0，那么下一个字符既可以选0也可以选1，两个分支都要走。
  • 如果当前序列的最后一个字符是1，为了避免相邻1，下一个字符只能选0，走这一个分支。

举个n=3的例子帮你理解：

1. 初始分支：生成0和1两个初始序列
2. 对0分支：
   • 加0得到00，再对00分支：
     • 加0→000（长度3，输出）
     • 加1→001（长度3，输出）
   • 加1得到01，对01分支：
     • 只能加0→010（长度3，输出）
3. 对1分支：
   • 只能加0得到10，对10分支：
     • 加0→100（长度3，输出）
     • 加1→101（长度3，输出）

这样走下来正好就是你要的5个结果，是不是很清晰？

二、迭代解法（用队列实现） #

如果你还是对递归有点懵，也可以用迭代的方式，思路其实和递归是相通的：

1. 初始化一个队列，把"0"和"1"放进去（作为长度为1的序列）
2. 循环处理队列里的元素：
   • 取出队首的序列，如果它的长度等于n，就输出它。
   • 如果长度小于n，看序列最后一个字符：
     • 是0的话，把序列+"0"和序列+"1"都加入队列
     • 是1的话，只把序列+"0"加入队列
3. 直到队列里所有元素的长度都等于n为止。

这个方法相当于把递归的“分支”用队列来存储，一步步迭代生成所有符合条件的序列。

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