带有两个变量的Java递归

Question

我一直在试图弄清楚这种递归方法的堆栈是什么样的.

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;

这显然既不真实也不完整.请帮我理解堆栈是如何构建的.

Answer 1

理论:

每次,此函数将q1(x/2)首先递减路径,直到达到结束条件.然后,q1(x-2)将处理所有待处理的呼叫.现在这是q1(x-2)我们第一次处理时变得棘手的地方q1(x/2).因此,我们现在回到与以前相同的位置,只有一层向下,重复直到我们处理所有q1(x-2)调用(在最后q1(x/2)一层).

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

我只认为堆栈按x/2增长

你是对的,如果通过上述你的意思是这个功能q1(x/2)在q1(x-2)方向上的速度要快得多.尽管如此,你所说的暗示它以lg(n)的方式增长(lg(n)是基数2).

但是,我们仍然需要分析其他堆栈帧,因此我们设置以下递归关系:

T(n)= T(n/2)+ T(n-2)+ c1