我一直在试图弄清这个递归方法的堆栈如何.
public class Apples {
public static void main (String [] args) {
q1(5);
}
public static int q1 (int x) {
if (x < 1) {
System.out.println(x);
return 1;
}
int a = 3 + q1(x / 2);
int b = 2 * q1(x - 2) + 1;
System.out.println(x + ";" + a + ";" + b);
return a + b;
}
}
但到目前为止,我只认为堆栈根据x / 2增长：
x=0 returns 1; x=1 a=4 b=3 returns 7; x=2 a=10 b=3 returns 13; x=5 a=16 b=9 returns 19;
这显然既不真实也不完整.请帮助我了解堆栈如何建立.
解决方法
理论：
每次,这个函数将首先递减q1(x / 2)路径,直到达到结束条件.然后,所有待处理的q1(x-2)调用将被处理.现在这是它变得棘手的地方,在每个q1(x-2)我们首先处理q1(x / 2).因此,我们现在回到与以前相同的地方,只有一层,重复,直到我们处理所有的q1(x-2)调用(在最后的q1(x / 2)层).
想到它的一种方式就像一棵树：
I only think that the stack grows according to x/2
你是对的,如果通过上述你的意思是这个函数在q1(x / 2)中比在q1(x-2)方向上要快得多.尽管如此,你所说的意思是它以lg(n)的方式增长(lg(n)是基数2).
然而,我们仍然需要分析其他堆栈帧,因此我们设置以下重复关系：
T(n)= T(n / 2)T(n-2)c1
