如何计算在递归中特定函数将被执行的次数？

Question

如何计算在递归中特定函数将被执行的次数？

20

这个问题是与下面的代码有关：

cost = [[1, 10, 75, 92],
         [-1, 0, 35, 50],
         [-1, -1, 0, 80],
         [-1, -1, -1, 0]]

def min_cost(source, destination):
   if s==d or s == d-1:
       return cost[s][d]
    mc = cost[s][d]
    for i in range(s+1, d):
        tmp = min_cost(s, i) + min_cost(i, d)
    if tmp < mc:
        mc = tmp
return mc

当我进行同样的干运行时，我看到min_cost(1,3)被执行了两次。我在一本书中读到过作者提到，如果我们有10个站点，则min_cost(1, 3)将运行144次。

我们如何在不实际运行的情况下找出这些数字？我知道使用递归方程我们可以找出函数所需的时间，但是我们如何说特定的函数将执行这么多次？

当我dry run相同代码时，我发现min_cost（1,3）被执行了两次。我曾在一本书中阅读到，如果有10个站点，则min_cost（1,3）将运行144次。那么，我们如何在实际干运行之前计算这些数字？虽然我们可以使用递归公式来计算函数的运行时间，但我们如何确定特定函数将被执行的次数呢？

- Raghav salotra

3

Alan Turing和Gödel已经证明，你不能在不执行函数的情况下知道某个代码中函数执行的次数。这个问题类似于停机问题，该问题陈述了在执行期间无法预先确定程序是否会停止。详情请参阅https://en.wikipedia.org/wiki/Halting_problem。 - David Lemon

3个回答

3

当使用递归计算时，有几个选项可用来计算该金额。最简单的方法是向递归方法添加另一个变量，每次递归时增加该变量，在返回最后一个金额的语句中不会增加变量，而只是返回最后一个金额，这将递归“回到”上一请求。

伪代码示例：

function recursionfunction(x, y, recursioncount) {
    if(expressionIsFalse) {
        recursionfunction(x, y, recursioncount+1);
    } else {
        return recursioncount;
    }
}

print recursionfunction('','', 0);

另一种工作方式是通过引用、指针或全局变量（取决于编程语言）分配变量并增加计数器。

这有帮助吗？

- Tim B.

我正在寻找一些数学解决方案，如果不运行程序，我们就可以看到并告诉同一个函数将在 RAM 的激活堆栈中执行这么多次。 - Raghav salotra

我不确定，但那听起来更像是汇编/C++类型的活动，需要启用调试器/监视器。也许你需要研究一下作为其他应用程序主进程运行的应用程序，这样主进程就可以监视应用程序调用...但我不确定你能很快达到那里。 - Tim B.

希望这些能帮助你找到正确的方向：http://www.rohitab.com/apimonitor，https://dev59.com/TXVC5IYBdhLWcg3wYQEp或https://learn.microsoft.com/en-us/sysinternals/downloads/process-explorer。 - Tim B.

以上代码是递归的，如果你绘制递归调用栈，你可以看到使用这些或任何类似这样的度量标准来调用min_cost(1, 3)两次。我认为应该有一种方法来推断轨迹并获取调用次数。 - Raghav salotra

2

我认为在函数外部创建一个全局变量（如果是Java中的类成员，或者在C++/C中的全局变量），每次调用该变量时将其值增加1，这样就可以解决问题了。

- Pipe Runner

2

问题设定者要求找到一种方法来解决这个问题，而不需要进行干运行。 - Kevin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gassa · Accepted Answer

我知道你不想进行无意义的模拟通话，但我还是希望先这样做一次，以便查看情况。下面开始：

def min_cost(s, d):
    global count
    count += 1
    if s==d or s == d-1:
        return cost[s][d]
    mc = cost[s][d]
    for i in range(s+1, d):
        tmp = min_cost(s, i) + min_cost(i, d)
    if tmp < mc:
        mc = tmp
    return mc

for n in range (2, 8):
    cost = [[0 for i in range (n)] for j in range (n)]
    count = 0
    min_cost(0, n-1)
    print (str (n) + ': ' + str (count))

输出结果为：

因此，我们可以看到对于d-s=k的通话数量是3的(k-1)次方。有时候知道我们需要证明什么会大大简化找出证明的过程。

现在进入证明本身。这将采用数学归纳法来证明。首先，注意min_cost(s, d)的调用次数仅取决于d-s的值，而不取决于s和d的具体值。

基础部分是，对于d-s=1，我们得到一次调用。对于d-s>1，我们进行一个调用，然后从它进行以下调用：

min_cost(s, s+1) and min_cost(s+1, d)
min_cost(s, s+2) and min_cost(s+2, d)
...
min_cost(s, d-1) and min_cost(d-1, d)

因此，对于 d-s=k，调用数量为 f(k)：

f(k) = 1 +
       f(1) + f(k-1) +
       f(2) + f(k-2) +
       ... +
       f(k-1) + f(1)
     = 2 * (f(1) + f(2) + ... + f(k-1))

如果根据归纳假设，我们已经证明对于所有v < k都有f(v) = 3^v，那么f(k)是：
1 + 2 * (3¹ + 3² + ... + 3^k-1)，这显然地是3^k，从而完成了我们的证明。

最后，请注意，虽然所提出的算法是指数级的，但基础问题可以在多项式时间内解决，最简单的方法是通过为我们已经完成所有工作的调用进行记忆化来实现O((d-s)^2)。