CODEWITHSUNDEEP
javarecursion
Eli
Eli

Reputation: 857

Recursion multiply method correct way to think about it?

    public static void main(String[]args){
multiply(2,4);

}
public static int multiply(int a, int b) {
       if (b == 0) {
          return 0;
       }
       return a + multiply(a, b - 1);
    }
}

I have this recursive statement, and I am wondering how it works, is this the correct way to think about it? 

return 2 + (2, 3);
return 2 + (2,2);
return 2 + (2,1);
return 2 + (2,0);

return 2 + 6;
return 2 + 4;
return 2 + 2;
return 2 + 0;

Upvotes: 1

Views: 53

Answers (3)

Artur Opalinski
Artur Opalinski

Reputation: 1092

You are almost perfect, just... Bear in mind that returning from recurence seems for us, poor humans, to revert the order of instructions as we tend to think about them.
Therefore:
YES, you are perfectly correct when analyzing nested calls.
NO, you make the mistake when analyzing returns, which happen in the following order (reverted compared to your feeling, but this makes sense if you think about the LAST function call returning FIRST): Returning: 2+0 Returning: 2+2 Returning: 2+4 Returning: 2+6 As a general solution is better than a specific one, here is your original program which employs 2 additional printfs() and one additional variable (res). You can track any recurrence this way. :-) public static void main(String[] args){ multiply(2,4); } public static int multiply(int a, int b) { int res; if (b == 0) { return 0; } System.out.printf("Calling: %d+multiply(%d, %d)\n", a, a, b-1); res = multiply(a, b - 1); System.out.printf("Returning: %d+%d\n", a, res); return a + res; }

Upvotes: 2

biziclop
biziclop

Reputation: 49814

The easiest way is to try it:

public static int multiply(int a, int b) {
       System.out.println("-->multiply("+a+", "+b+")");
       if (b == 0) {
          System.out.println("<--returning zero for "+a+"*"+b);
          return 0;
       }
       int ret = a + multiply(a, b - 1);
       System.out.println("<--returning "+a+"*"+b+" = "+ret);
       return ret;
}

Your output will be:

-->multiply(2, 4)
-->multiply(2, 3)
-->multiply(2, 2)
-->multiply(2, 1)
-->multiply(2, 0)
<--returning zero for 2*0
<--returning 2*1 = 2
<--returning 2*2 = 4
<--returning 2*3 = 6
<--returning 2*4 = 8

The arrows show you when the stack grows (-->) and when it shrinks (<--). This is a useful technique to visualise recursive calls in general: log the input after you enter the method, and log your result before returning it.

Upvotes: 3

forgivenson
forgivenson

Reputation: 4445

I'm not exactly clear on what you are showing, though it looks fairly correct (if I'm interpreting it correctly). You need to work through each call of the method until you hit the base case (in this instance, it is when b == 0). Then, you can work your way back up, substituting in the values that are returned.

multiply(2,4) returns 2 + multiply(2,3). multiply(2,3) returns 2 + multiply(2,2). multiply(2,2) returns 2 + multiply(2,1). multiply(2,1) returns 2 + multiply(2,0). multiply(2,0) returns 0.

So, if we substitute in the return values, working from the bottom up, you get:

return 2 + 2 + 2 + 2 + 0;

which equals 8. 2 x 4 = 8.

Upvotes: 2

Related Questions