将其中包含 for 循环的递归函数更改为迭代函数？

Question

所以我有这个函数，我试图将它从递归算法转换为迭代算法。我什至不确定我是否有正确的子问题，但这似乎以正确的方式确定了我需要什么，但是不能使用递归，您需要使用动态编程，所以我需要将其更改为迭代自下而上或顶部下动态规划。

基本的递归函数如下所示：

Recursion(i,j) {
    if(i > j) {
        return 0;
    }
    else {
        // This finds the maximum value for all possible
        // subproblems and returns that for this problem
        for(int x = i; x < j; x++) {
            if(some subsection i to x plus recursion(x+1,j) is > current max) {
                max = some subsection i to x plus recursion(x+1,j)
            }
        }  
    }
}

这是一般的想法，但由于递归通常没有 for 循环，我不确定如何将其转换为迭代。有人有什么想法吗？

Answer 1

你有一个递归函数，可以总结如下：（

recursive(i, j):
    if stopping condition:
        return value

    loop:
        if test current value involving recursive call passes:
            set value based on recursive call

   return value # this appears to be missing from your example

我将在这里对伪代码进行相当宽松的处理，以强调代码的结构而不是具体的实现）

并且你想将其扁平化为纯粹的迭代方法。首先，最好准确描述一下一般情况下涉及的内容，因为您似乎对此感兴趣。然后我们可以继续扁平化上面的伪代码。

现在，扁平化原始递归函数非常简单。当您获得如下代码时：

simple(i):
    if i has reached the limit: # stopping condition
        return value

    # body of method here

    return simple(i + 1) # recursive call

您可以很快看到递归调用将继续，直到 i 达到预定义的限制。发生这种情况时，将返回值。其迭代形式是：

simple_iterative(start):
    for (i = start; i < limit; i++):
        # body here

    return value

这是有效的，因为递归调用形成以下调用树：

simple(1)
  -> simple(2)
    -> simple(3)
      ...
        -> simple(N):
            return value

我将该调用树描述为一段字符串。它有开始、中间和结束。不同的调用发生在字符串上的不同点。

这样的一串调用非常像一个 for 循环 - 函数完成的所有工作都会传递到下一个调用，并且递归的最终结果会被传回。 for 循环版本仅获取将传递到不同调用的值并对其运行主体代码。

到目前为止很简单！

现在您的方法在两个方面更加复杂：

• 有多个单独的语句进行递归调用
• 这些语句本身位于 for 循环内

所以您的调用树类似于：

recursive(i, j):
  for (v in 1, 2, ... N):
    -> first_recursive_call(i + v, j):
      -> ... inner calls ...
    -> potential second recursive call(i + v, j):
      -> ... inner calls ...

正如您所看到的，这根本不像字符串。相反，它实际上就像一棵树（或灌木丛），每次调用都会导致另外两次调用。此时实际上很难将其转回完全迭代的函数。

这是因为循环和递归之间的基本关系。任何循环都可以重新表述为递归调用。然而，并不是所有的递归调用都可以转化为循环。

可以转换为循环的递归调用类称为原始递归。您的功能最初似乎已经超越了这一点。如果是这种情况，那么您将无法将其转换为纯粹的迭代函数（缺少在函数中实际实现调用堆栈和类似函数）。

该视频解释了原始递归与以下基本递归类型之间的区别：

https ://www.youtube.com/watch?v=i7sm9dzFtEI

我想补充一点，您的条件和您分配给 max 的值似乎是相同的。如果是这种情况，那么您可以删除其中一个递归调用，从而使您的函数成为包装在循环中的原始递归的实例。如果你这样做了，那么你也许可以把它压平。

Answer 2

好吧，除非尚未包含逻辑问题，否则

对于 & 来说 应该没问题。虽然在递归中可以，

但请确保在可能发生的每种情况下都返回