How do I trace recursive function

Question

So in one of my class I am learning recursion and there is a question which I tried to trace through but couldn't get the right answer.

I keep geting 11 but the right answer is 6. Can someone help me get a better understanding and hopefully explain how you would trace through the code please. Thank you.

The way I tracing it right now:

int f(int x, int y) {
  if (x <= 0) {
     return y;
  }
  return f(x - 1, y + 1) - f(x / 2, y * 2);
}

What is f(4, -1)?

f(4,-1)
return   f(3,0) - f(2,-2)
return   f(2,1) - f(1,-4)
return   f(1,2) - f(0,-8)
return   f(0,3) - (-8)
return   3 + 8  = 11.

Answer 1

You are not taking into account that most of the calls to f() are then making 2 internal calls to f(). So the real trace would break down more like the following. The real answer is 2, not 6 like your professor told you:

f(4,-1) = f(3,0) - f(2,-2)
    (
    f(3,0) = f(2,1) - f(1,0)
        (
        f(2,1) = f(1,2) - f(1,2)
            (
            f(1,2) = f(0,3) - f(0,4)
                (
                f(0,3) = 3
                )
                (
                f(0,4) = 4
                )
            = (3) - (4) = -1
            )
            (
            f(1,2) = f(0,3) - f(0,4)
                (
                f(0,3) = 3
                )
                (
                f(0,4) = 4
                )
            = (3) - (4) = -1
            )
        = (-1) - (-1) = 0
        )
        (
        f(1,0) = f(0,1) - f(0,0)
            (
            f(0,1) = 1
            )
            (
            f(0,0) = 0
            )
        = (1) - (0) = 1
        )
    = (0) - (1) = -1
    )
    (
    f(2,-2) = f(1,-1) - f(1,-4)
        (
        f(1,-1) = f(0,0) - f(0,-2)
            (
            f(0,0) = 0
            )
            (
            f(0,-2) = -2
            )
        = (0) - (-2) = 2
        )
        (
        f(1,-4) = f(0,-3) - f(0,-8)
            (
            f(0,-3) = -3
            )
            (
            f(0,-8) = -8
            )
        = (-3) - (-8) = 5
        )
    = (2) - (5) = -3
    )
= (-1) - (-3) = 2

final answer: 2

Live Demo

Answer 2

Here is ASCII art with control flow for recursive call,

f(4,-1)-------->+
    .   //f(4 - 1, -1 + 1)
    .         f(3,0)------->+
    .           .           |
    .           .     //f(3-1,0+1)          
    .           .         f(2,1)----------->+
    .           .           .               |
    .           .           .      // f(2-1,1+1)    
    .           .           .           f(1,2)--------->+
    .           .           .               .           |
    .           .           .               .   //f(1-1,2+1)
    .           .           .               .       f(0,3)--------->+
    .           .           .               .           .       //as (x == 0) return 3
    .           .           .               .           .           |
    .           .           .               .           |<----(3)---+
    .           .           .               .           |
    .           .           .               .   //f(1/2,2*2)
    .           .           .               .       f(0,4)--------->+
    .           .           .               .           .       //as (x == 0) return 4
    .           .           .               .           .           |
    .           .           .               .           +<----(4)---+
    .           .           .               .           |
    .           .           .               .   //f(1-1,2+1) - f(1/2,2*2) = 3 - 4 = -1 
    .           .           .               +<---(-1)---+
    .           .           .               |
    .           .           .       // f(2/2,1*2)
    .           .           .           f(1,2)--------->+
    .           .           .               .           |
    .           .           .               .   //f(1-1,2+1)
    .           .           .               .       f(0,3)--------->+
    .           .           .               .           .    //as (x == 0) return 3
    .           .           .               .           .           |
    .           .           .               .           +<----(3)---+
    .           .           .               .           |
    .           .           .               .   //f(1/2,2*2)
    .           .           .               .       f(0,4)--------->+
    .           .           .               .           .   //as (x == 0) return 4
    .           .           .               .           .           |
    .           .           .               .           +<----(4)---+
    .           .           .               .           |
    .           .           .               .    //f(1-1,2+1) - f(1/2,2*2) = 3 - 4 = -1
    .           .           .               +<---(-1)---+
    .           .           +<----(0)-------+
    .           .           |
    .           .     //f(3/2,0*2)  
    .           .         f(1,0)----------->+
    .           .           .               |
    .           .           .       //f(1-1,0+1)
    .           .           .           f(0,1)--------->+
    .           .           .               .     //as (x == 0) return 1
    .           .           .               .           |
    .           .           .               +<----(1)---+
    .           .           .               |
    .           .           .       //f(1/2,0*2)
    .           .           .           f(0,0)--------->+
    .           .           .               .     //as (x == 0) return 0
    .           .           .               .           |
    .           .           .               +<----(0)---+
    .           .           .               |
    .           .           .       //f(0,1)-f(0,0) = 1- 0 = 0
    .           .           +<-----(1)------+
    .           .           |
    .           .   // f(3-1,0+1) - f(3/2,0*) = 0 - 1 = -1   
    .           +<----(-1)--+
    .           |
    .    //f(4/2,-1*2)
    .        f(2,-2)------->+
    .           .           |
    .           .       //f(2-1,-2+1)
    .           .         f(1,-1)---------->+
    .           .           .               |
    .           .           .       //f(2-1,-2+1)
    .           .           .           f(0,0)--------->+
    .           .           .               .   //as (x == 0) return 0
    .           .           .               .           |
    .           .           .               +<----(0)---+
    .           .           .               |
    .           .           .       //f(1/2,-1*2)
    .           .           .           f(0,-2)-------->+
    .           .           .               .   //as (x == 0) return -2
    .           .           .               .           |
    .           .           .               +<---(-2)---+
    .           .           .               |
    .           .           .       //f(0,0)-f(0,-2) = 0 - (-2) = 2
    .           .           +<----(2)-------+
    .           .           |
    .           .       //f(2/2,-2*2)
    .           .         f(1,-4)---------->+
    .           .           .               |
    .           .           .           f(0,-3)-------->+
    .           .           .               .   //as (x == 0) return -3
    .           .           .               .           |
    .           .           .               +<---(-3)---+
    .           .           .               |
    .           .           .           f(0,-8)-------->+
    .           .           .               .    //as (x == 0) return -8
    .           .           .               .           |
    .           .           .               +<---(-8)---+
    .           .           .               |
    .           .           .       //f(0,-3) -f(0,-8) = -3 -(-8) = 5
    .           .           +<-----(5)------+
    .           .           |
    .           .   //f(1,-1)-f(1,-4) = 2 - 5 = -3
    .           +<----(-3)--+
    .           |
    .   //f(4 - 1, -1 + 1) - f(4/2,-1*2) = -1 - (-3) = 2
    <----(2)----+

How to understand,

1. Each column represents a function call which makes 2 subsequent recursive calls.
2. <--(x)--- represents return value x

When function f(x,y) is called, recursive call for f(x-1,y+1) is called until x is zero and then f(x/2,y*2) is called recursively.

Consider below case with f(1,2) call makes two subsequent recursive call to f(0,3) and f(0,4) and return value from both is computed back as return value of f(1,2)

f(1,2)--------->+
    .           |
    .   //f(1-1,2+1)
    .       f(0,3)--------->+
    .           .       //as (x == 0) return 3
    .           .           |
    .           |<----(3)---+
    .           |
    .   //f(1/2,2*2)
    .       f(0,4)--------->+
    .           .       //as (x == 0) return 3
    .           .           |
    .           +<----(4)---+
    .           |
    .   //f(1-1,2+1) - f(1/2,2*2) = 3 - 4 = -1 
    +<---(-1)---+

Let me try to put it in different way,