加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 编程开发 > Java > 正文

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)层).

想到它的一种方式就像一棵树:

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

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读