当函数中存在循环时，将递归转换为迭代

Question

我正在将代码库中的一些递归调用转换为迭代。多亏了这个博客和这个问题，这一切都很简单。然而，有以下模式(作为一个最小的例子(，这让我很难过。它基本上给出了m位置(此处为n=4、m=3(的n数的n^m排列(具有重复(：

def f (i, arr):
if i < len(arr):
for j in [2,3,5,8]:
arr[i] = j
f(i+1, arr)
else:
print(arr)
f(0, [0,0,0])

输出：

[2, 2, 2]
[2, 2, 3]
[2, 2, 5]
...
[8, 8, 3]
[8, 8, 5]
[8, 8, 8]

根据这次讨论，这应该是可能的。如果有人能分享一些关于如何进行这种转换的指导，那就太好了？

Answer 1

从代码中退一步，转而思考您试图在这里生成什么模式可能会有所帮助。例如，想象一下，每个插槽有十个数字选项可供选择，它们分别是0、1、2、。。。，9.在这种情况下，你所做的基本上是从000开始向上计数，直到你最终达到999。你是怎么做到的？井：

• 如果最后一个数字不是9，就加一个
• 否则，数字为9。将其回滚到0，然后移动到前一位

在你的情况下，是数字2、3、5和8，但这并不重要。

你可以把它转化为一个很好的过程，来解决一个更普遍的问题，列出从k个选项列表中写出n个符号的所有方法：

def list_all_options(length, options):
# Initially, pick the first option in each slot. This array stores
# indices rather than values.
curr = [0] * length

while True:
# Print what we have, mapping from indices to values.
print([options[index] for index in curr])

# Roll over all copies of the last digit from the end, backing
# up as we go.
pos = len(curr) - 1
while pos >= 0 and curr[pos] == len(options) - 1:
curr[pos] = 0
pos -= 1

# If we rolled all digits, we're done!
if pos == -1: break

# Otherwise, increment this digit.
curr[pos] += 1