考虑以下递归函数。
int f(int n){
if(n<=0) return 1; return f(n-1)+f(n-1);
}
据说虽然有 2^N
(2 次幂为 N)次调用,但在给定时间仅存在 N
次调用。有人能解释一下怎么做吗?
最佳答案
当然。复杂性部分位于else部分:
return f(n-1)+f(n-1)
对于 n 处的每次调用,这会在 n-1 处生成两次调用。但是,请注意评估顺序:
call f(n-1) ... left side
save the value as temp1
call f(n-1) ... right side
add the value to temp1
return that value
整个左侧调用树必须在右侧调用树开始之前完成 - 这发生在每个深度级别。对于n的每个值,在任何时间点都只有一个调用处于事件状态。例如,f(2) 给我们一个像这样的序列:
call f(2)
n isn't <= 0 ...
call f(1) ... left
n isn't <= 0 ...
call f(0) ... left | left
n <= 0; return 1
save the 1
call f(0) ... left | right
n <=0; return 1
add the 1 to the temp value;
return 2
save the 2
call f(1) ... right
call f(0) ... left | left
n <= 0; return 1
save the 1
call f(0) ... left | right
n <=0; return 1
add the 1 to the temp value;
return 2
add this 2 to the temp value, making 4
return the 4
done ...
尽管我们最终执行了 2^(n+1)-1 次调用,但在每个点,事件调用都不超过 n+1 个(请参阅缩进级别)。我们偏离了 1(n+1 而不是 n),因为我们在 0 而不是 1 处终止。
这样就可以解决问题了吗?
关于recursion - 以下函数的空间复杂度是多少以及如何?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35214223/