我正在复习我的数据结构和算法类(class)的旧考试集,但似乎无法弄清楚如何解决这个问题。
问题 (d) 通过以下递归方法找到乘法次数的递推关系:
static int f(int N)
{
if (N > 1) return 2*f(N - 1);
else return 3;
}
答案: T(N) = T(N − 1) + 1
我不是很明白这个关系是怎么求乘法数的?
T(2) = T(2 - 1) + 1 = 2
T(3) = T(3 - 1) + 1 = 3
我尝试在关系中插入 2 和 3,但我仍然看不出乘法的数量。我走在正确的轨道上吗?
最佳答案
f(N)
比f(N-1)
多了一次递归调用,所以多了一次乘法,因此
T(N) = T(N-1) + 1
基本情况 T(1) = 0
。
关于algorithm - 如何从给定的递归函数中找到递归关系,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55617518/