Java recursion with two variables

Question

I've been trying to figure out how the stack of this recursive method will look like.

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;
    }
}

But so far, I only think that the stack grows according to 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;

This is obviously neither true nor complete. Please help me understand how does the stack build up.

Answer 1

Theory:

Each time, this function will recurse down the q1(x/2) path first, until it reaches the ending condition. Then, all pending q1(x-2) calls will be handled. Now this is where it gets tricky, at every q1(x-2) we first handle q1(x/2). Thus, we are now back to the same spot as before, just one layer down, repeating until we handle all the q1(x-2) calls (in the last q1(x/2) layer).

One way to think of it is like a tree:

I only think that the stack grows according to x/2

You are right, if by the above you mean that this function recurses much faster in the q1(x/2) than in the q1(x-2) direction. Nonetheless, what you are saying implies it grows in lg(n) fashion (lg(n) is base 2).

However, we still need to analyze the other stack frames, so we set up the following recurrence relation:

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