Java递归与两个变量
发布时间:2020-12-14 05:07:13 所属栏目:Java 来源:网络整理
导读:我一直在试图弄清这个递归方法的堆栈如何. 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
我一直在试图弄清这个递归方法的堆栈如何.
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)层). 想到它的一种方式就像一棵树:
你是对的,如果通过上述你的意思是这个函数在q1(x / 2)中比在q1(x-2)方向上要快得多.尽管如此,你所说的意思是它以lg(n)的方式增长(lg(n)是基数2). 然而,我们仍然需要分析其他堆栈帧,因此我们设置以下重复关系: T(n)= T(n / 2)T(n-2)c1 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |