CODEWITHSUNDEEP
javarecursion
user2879125
user2879125

Reputation: 183

Recursive method confusion

Given the below

public class Recursion {
    public static int magic(int a, int b) {
        if (b == 0) {
            return 0;
        } else {
            if (b % 2 == 0) 
              return magic(a + a, b / 2);
            else
              return magic(a + a, b / 2) + a;
        }
    } 

    public static void main(String[] args) {
        Recursion r = new Recursion();
        System.out.println(r.magic(3,11));
      //System.out.println(r.magic(2,25));
    }
}

When I use r.magic(3,11) I get an output of 33 and if I use r.magic(2.25) I get an output of 50, can someone explain the math behind it to me because I can't really seem to make sense of it.

Upvotes: 1

Views: 280

Answers (2)

Alperen
Alperen

Reputation: 4662

I guess you want some explanations, not steps of the program. Here it is:

return magic(a + a, b / 2)

is actually

return magic(2 * a, b / 2)

It means you multiply one of the numbers by 2, and divide the other one by 2. So, these operations will not change the result in Math.

ab = (2a)*(b/2)

But, you work with integers in this method. That's OK with even numbers. But, if you divide an odd number by 2, you will lose the floating part which is "0.5".

If b is odd, let's say b = 2*n+1

a*(2n+1) = (2a)((2n+1)/2)

2an + a = (2a)(n+0.5)

2an + a = 2an + a

When you work with integers, it will be that which is wrong:

2an + a = 2an

Recursively this additional a becomes 2a, 4a, ...

And you can derive a*b with summation of these multiples of a.

When b is 0, this is the end, there is no need to sum any multiples of a.

Upvotes: 1

Abhishek Honey
Abhishek Honey

Reputation: 645

Ok, here it is.

First of all you need to know the basics of recursion like how its returns the value and what is the exit condition.

Here is the stack trace for 2 and 25. In recursion we make a stack and this is the stack for 2 and 25. The first call value of a and b is in the bottom of the stack. i.e (2,25). You need to visualize it like this only.

a  b    called from return magic(a+a,b/2) or return magic(a+a,b/2)+a
64 0
32 1    2
16 3    2
8  6    1
4 12    1
2 25    2

Here 1 is for calling from magic(a+a,b/2) and 2 is for calling from return magic(a+a,b/2)+a.

So while returning from the function here is stack.If it is called from 1 then it will simply return the value else it will add a with the returned value.

a  b
64 0        returns 0
32 1    2   returns 32
16 3    2   returns 32+16
8 6     1   returns 32+16
4 12    1   returns 32+16
2 25    2   returns 32+16+2

So the final return statement returns 50

And for the second call similarly here is the stack trace.

a  b
48 0        returns 0
24 1    2   returns 24
12 2    1   returns 24
6 5     2   returns 24+6
3 11    2   returns 24+6+3

So the final return statement returns 33

So you can see now how the result is 50 and 33.

If you have any doubt you can comment.

Upvotes: 1

Related Questions