Recursive statement calling another Recursive statement?

Question

public class Recursive_Prob
{    
    public static void main(String[] args)    
    {    
        out.print("\f");   
        out.print(m(4));   
    }   
    public static int m(int a)   
    {   
        if (a < 0)    
            return 0;    
        else    
            return m(a-2) + n(a-1);    
    }       
    public static int n(int b)     
    {     
        if (b <= 0)    
            return 0;     
        else     
            return 1 + n(b-1);     
    }       
}    

I had a question asking what the output would be when method m was called with out.print(m(4)); I tried working it out and came out with 0 but the answer was 4 when I ran the code. I ended up with m(a-2) being 0 and that part was right but using the same logic, n(a-1) was also 0 so clearly I'm doing something wrong. Could someone explain how this works?

Answer 1

The best way to find out the answer would be drawing a recursion tree . Let me try :

                    m(4)
                     /\
                    /  \
                   m(2) \
                   /\   n(3)
                  /  \     \
                 m(0) \     \
                 /\   n(1)  1+n(2)
                /  \    \      \
              m(-2) \  1+n(0)   \
               /   n(-1)   \   1+n(1)
              0       \     0      \   
                       0            \
                                   1+n(0)
                                      \
                                       0

Add them up , the result should be 4.

Answer 2

Here's a step by step calculation:

m(4) = m(2) + n(3)
     = m(0) + n(1) + n(3)
     = m(-2) + n(-1) + n(1) + n(3)
     = 0 + 0 + 1 + n(0) + 1 + n(2)
     = 0 + 0 + 1 + 0 + 1 + 1 + n(1)
     = 0 + 0 + 1 + 0 + 1 + 1 + 1 + n(0)
     = 0 + 0 + 1 + 0 + 1 + 1 + 1 + 0
     = 4

Answer 3

If you add up all the red lines it equals 4.

The left side of the tree actually goes to m(-2) but I didn't include it because it results in 0.

Answer 4

You have 1 + n(b-1) in n(int b) function. The call n(a-1) will do 4 recursive calls to n(int b) and return 4

Answer 5

Let's break it down:

m(4) = m(2) + n(3);
m(2) = m(0) + n(1);
m(0) = m(-2) + n(-1);
     =   0   +   0

n(3) = 1 + n(2);
n(2) = 1 + n(1);
n(1) = 1 + n(0);
     = 1 +  0 
n(1) = 2

Lets substitute all the values back:

n(2) = 1 + n(1) = 2
n(3) = 1 + n(2) = 3

m(2) = 0 + 1;
m(4) = 1 + 3 = 4

Answer 6

first call m(4) +n(3)
second call m(2) + n(1)
third call m(0) +n(-1)
fourth call m(-2) + n(-3)
the function m returns 0
so the fourth call becomes 0+n(-3)
n(-3) also returns 0 so overall the function in fourth call will return 0
now in third call we have m(0) = 0, now n(-1) will also return 0,so overall 
the third call will return 0 to second call.
now in second call m(2) = 0 , and now it call n(1) .. n(1) will return 1+n(0)=>1
so second call will return 0+1 to first call 
now in first call m(4) =1 ,now it will call n(3).
now in n(3)..it will call 1+n(2) => 1+n(1) => 1+n(0) =>1 so n(3) will return 3
so overall result is 1+3 =>4