参考：Python 实现递归算法 - 另一个自己 - CSDN博客 

参考：一文读懂递归算法 - 我的笔记 - CSDN博客 

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 

用递归实现以下算法：

  • Factorial
  • Hannoi Tower
  • Fibonacci

 

使用递归计算组合（permutation）

  • 对于一个元素的集合，直接返回值即可
  • 对于多个元素的集合
    • 遍历所有元素
    • 对于任意一个元素与其他元素合并  

代码如下：

利用 set 可以进行简单的 + - 操作

返回结果为 迭代器，也是可以遍历的

def naive_recursive_permute(S):
    if len(S) <= 1:
        yield list(S)
    else:
        for x in S:
            for P in naive_recursive_permute(S - {x}):
                yield [x] + P
                
list(naive_recursive_permute({0}))
list(naive_recursive_permute({0, 1}))
list(naive_recursive_permute({0, 1, 2}))
list(naive_recursive_permute({0, 1, 2, 3}))

output：

[[0]]
Out[2]:
[[0, 1], [1, 0]]
Out[2]:
[[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
Out[2]:
[[0, 1, 2, 3],
 [0, 1, 3, 2],
 [0, 2, 1, 3],
 [0, 2, 3, 1],
 [0, 3, 1, 2],
 [0, 3, 2, 1],
 [1, 0, 2, 3],
 [1, 0, 3, 2],
 [1, 2, 0, 3],
 [1, 2, 3, 0],
 [1, 3, 0, 2],
 [1, 3, 2, 0],
 [2, 0, 1, 3],
 [2, 0, 3, 1],
 [2, 1, 0, 3],
 [2, 1, 3, 0],
 [2, 3, 0, 1],
 [2, 3, 1, 0],
 [3, 0, 1, 2],
 [3, 0, 2, 1],
 [3, 1, 0, 2],
 [3, 1, 2, 0],
 [3, 2, 0, 1],
 [3, 2, 1, 0]]

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄