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

Question

本题参考以下代码：

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 次。

我们如何在不实际做空运行的情况下计算出这些数字？我知道使用递归方程我们可以算出函数所花费的时间，但是我们怎么能说一个特定的函数会执行这么多次呢？

Answer 1

在使用递归时，有几种方法可以计算该数量。最简单的方法是向递归方法添加另一个变量，每次递归时该变量都会增加，并且在最后一个 returned 的语句中它不会增加，而只是 return 最后一个数量，这将递归 'back' 到上层请求。

伪代码示例：

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

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

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

对你有帮助吗？

Answer 2

虽然我知道您不希望干涸运行只是计算通话次数，但我还是想先做一下，看看发生了什么。所以，这里是：

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) 次方。知道我们必须证明什么有时会大大简化寻找证明的过程。

现在，到证明本身。它将是 proof by induction。首先，请注意 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) ，即 trivially 3^k，完成我们的证明。

最后，请注意，虽然所提出的算法是指数算法，但潜在的问题可以在多项式时间内解决，最简单的是 O((d-s)^2) 通过记住我们已经完成所有工作的调用.

Answer 3

我认为一个位于函数外部的全局变量（如果在 Java 中，则为 class 的成员，或者在 C++/C 中为全局变量）并且每次都将其值增加 1你叫它，就可以了。

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

How can I calculate the number of times a specific function will get executed in recursion?

algorithm

recursion

analysis