当函数中有循环时将递归转换为迭代

Question

我正在将代码库中的一些递归调用转换为迭代。多亏了 this blog, and this question，这非常简单。但是，有以下模式（作为一个最小的例子），这让我很难过。它基本上给出 n^m n 数字在 m 位置的排列（重复）（这里 n=4，m=3）：

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]

根据this discussion，这应该是可以的。如果有人可以分享一些关于如何进行此转换的指导，那就太好了？

Answer 1

从代码中退后一步，转而考虑您要在此处生成的模式可能会有所帮助。想象一下，例如，您有 10 个数字选项可供每个插槽选择，它们是 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

当函数中有循环时将递归转换为迭代

Convert recursion to iteration when there are loops in the function

python

iteration

algorithm

recursion

enumeration