c - 递归中的 Big Theta

Question

作为学期的一部分，我们正在使用 C 进行编程，这是一个座谈会测试问题的示例:

unsigned f(unsigned n) {
if(n<=1) return 1;
return f(n-2)+f(n-2);
}

如果我为 f(4) 调用该函数，堆栈框架如何查找该函数以及它的 Big Theta 是多少(返回 f(n-2) + f(n-2) 算作 2 次调用)相同功能或与 1)

Answer 1

问题“堆栈帧是什么样的？”没有单一的答案。答案取决于我们在什么时候查看堆栈帧。

调用顺序如下:

f(4)
  f(2)
    f(0)
    f(0)
  f(2)
    f(0)
    f(0)

如果我们在 n <= 1 的返回处设置断点并调用f(4) ，我们会在第一次调用 f(0) 时命中断点。在上面的序列中。堆栈帧看起来像这样(假设堆栈从分配的帧顶部向下增长，并且我们将内存从 SP 转储到顺序更高的内存，这两种情况都是典型的):

0
PC of f(0) call
2
PC of f(2) call
4
PC of f(4) call

对于这个函数，bigO 与 big theta 相同，我相信 Mike P 说得对:2^(n/2)。要了解原因，请尝试编写 f(6) 的调用序列和f(8)希望您会看到这种模式:每次向参数添加两个时，调用次数都会加倍。

有关更完整的答案，请参阅 Computational complexity of Fibonacci Sequence 。这不是斐波那契数列，但算法具有相同的复杂性。