递归解的公式（循环变量）

Question

请考虑以下算法：

  for(j1 = n upto 0)
     for(j2 = n-j1 upto 0)
       for(j3 = n-j1-j2 upto 0)
        .
         .
           for (jmax = n -j1 - j2 - j_(max-1))
            {
             count++;
             product.append(j1 * j2 ... jmax); // just an example
            }

如您所见，关于上面的algo片段的一些相关要点：

1. 我列出了一个具有可变for循环数的算法。在
2. 我在每个最内层循环处计算的结果都会附加到一个列表中。此列表将增长到“count”维度。在

这个问题适合递归吗？如果是，我真的不知道该如何解决这个问题。我正在尝试用python编写代码，我不希望你们有任何代码。只是一些指向正确方向的指示或例子。非常感谢。在

下面是示例案例http://pastebin.com/PiLNTWED的初始尝试

Answer 1

您也可以考虑使用来自itertools模块的置换、组合或乘积。 如果你想要所有可能的i，j，k的组合。。。（即嵌套for循环） 您可以使用：

for p in product(range(n), repeat=depth):
    j1, j2, j3, ... = p # the same as nested for loops
    # do stuff here

但是要注意，循环中的迭代次数是指数级增长的！在

Answer 2

您的算法是找到所有的m-元组（m是伪代码中j的max下标），这些非负整数加起来等于或小于n。在Python中，最自然的表达方式是使用递归生成器：

def gen_tuples(m, n):
    if m == 0:
        yield ()
    else:
        for x in range(n, -1, -1):
            for sub_result in gen_tuples(m-1, n-x):
                yield (x,)+sub_result

输出示例：

^{pr2}$

Answer 3

这个玩具示例将转换为一种尾部递归，因此，就个人而言，我不希望递归版本对代码检查和维护更具洞察力。在

但是，为了了解这个原理，尝试从单个循环中找出不变部分/公共项，并尝试识别一个模式（最好在之后证明它！）。您应该能够修复要编写的递归过程的签名。用循环体固有的部分充实它（不要忘记终止条件）。在