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

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

虽然我知道你不希望试运行只是为了计算呼叫，但我想先做，看看发生了什么。所以，这里是：

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))

输出为：

2: 1
3: 3
4: 9
5: 27
6: 81
7: 243

因此，我们看到 d-s=k 的调用次数是 (k-1( 的 3 次方。 知道我们必须证明什么有时会大大简化找到证明的过程。

---

现在，到证明本身。 它将通过归纳来证明。 首先，请注意，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

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

伪代码中的示例：

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

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

这对你有帮助吗？

Answer 2

我认为一个位于函数之外的全局变量(如果在 Java 中是类的成员，或者在 C++/C 中是全局变量(，并在每次调用它时将其值增加一个，就可以了。