Reputation:
I was reading about recursion in Java. I found this example in my course page for calculating the multiplication of two numbers recursively :
public class bst {
public static void main(String[] args) {
bst b = new bst();
b.mult(2, 4);
System.out.println(b.mult(2, 4));
}
public static int mult(int a, int b) {
if (b == 0) {
return 0;
} else {
return a + mult(a, b - 1);
}
}
}
I used debug to see how it works but I still do not understand how it works to calculate 2*4 = 8
.
Upvotes: 0
Views: 677
Reputation: 71
Well, let's take your example 2 * 4
, it is exactly the same as doing 2 + 2 + 2 + 2
. Translating this to your code (note the recursion will stop when b = 0
), we would have by calling mult(2, 4)
:
mult(2, 4) = 2 + mult(2, 3)
mult(2, 3) = 2 + mult(2, 2)
mult(2, 2) = 2 + mult(2, 1)
mult(2, 1) = 2 + mult(2, 0)
mult(2, 0) = 0
Replacing mult(2, 0)
in mult(2, 1)
, mult(2, 1)
in mult(2, 2)
and so o on, we obtain: 2 + 2 + 2 + 2 + 0 = 8
Upvotes: 1
Reputation: 79
multiplying A and B is nothing but adding A, B number of times. In this example of yours, you are adding A to the result and decrementing B each time till B reach zero(This is the Base Case). That is ideally adding A to the result B number of times.
Upvotes: 0
Reputation: 1183
For a = 2, b = 4, Now as b is not 0, so a would be added and it would go into recursion with b = 3. Same happen for till b = 0, when 0 is return which keeps on returning the intermediate calculations.
**
> Ex : b = 4 Stack : a + mul(3) - > a + mul(2) -> a +mul(1) -> a + mul(0)
> mul(0) = 0 which is return to calling function
> Now mul(1) = a + mul(0), which is a + 0 = a;
then, a + mul(1) = a + a = 2a, which would be returned to mul(2)
then a + mul(2) = a + 2a = 3a
then a + 3a = 4a, which would be return to calling function.
**
Upvotes: 0
Reputation: 30849
This is how it loops through calls. Mind the step numbers and indentations:
1. starts with 2,4
2. goes into else, returns 2 + <starts again>
3. starts with 2,3
4. goes into else, returns 2 + <starts again>
5. starts with 2,2
6. goes into else, returns 2 + <starts again>
7. starts with 2,1
8. goes into else, returns 2 + <starts again>
9. starts with 2,0
10. goes into if, returns 0 to step 8
11. goes to step 8, returns 2 + 0 (=2) to step 6
12. goes to step 6, returns 2 + 2 (=4) to step 4
13. goes to step 4, returns 2 + 4 (=6) to step 2
14. goes to step 2, returns 2 + 6 (=8) to the main call
Upvotes: 3
Reputation: 21269
The best way to see how recursion, or loops, work, is to 'unwind' it:
mult
the first time with 2
and 4
as parameters in main
.mult
checks to see if b
(which is 4
) is equal to 0. It is not.mult
then adds a
(which is 2
) to the result of mult
when called with a
and one less than b
(which would be 3
). mult
checks to see if b
(which is 3
) is equal to 0. It is not.mult
then adds a
(which is 2
) to the result of mult
when called with a
and one less than b
(which would be 2
). mult
checks to see if b
(which is 2
) is equal to 0. It is not.mult
then adds a
(which is 2
) to the result of mult
when called with a
and one less than b
(which would be 1
). mult
checks to see if b
(which is 1
) is equal to 0. It is not.mult
then adds a
(which is 2
) to the result of mult
when called with a
and one less than b
(which would be 0
). mult
checks to see if b
(which is 0
) is equal to 0. It is! 0
is returned.a
(which is 2
) and returns the result (2
).a
(which is 2
) and returns the result (4
).a
(which is 2
) and returns the result (6
).a
(which is 2
) and returns the result (8
).The best way to think about recursion is that there are two cases: the first case where 'the problem cannot get any smaller' and 'any case that is larger than that'. In the first, or 'base case' you return some easily understood amount. In this case it is 0
. In every other case you calculate an incremental difference to a slightly smaller problem.
In your example we are reducing one factor by 1
(making the problem smaller) and adding the other factor to the result of the smaller problem (calculating the incremental difference). The 'base case' is if one factor is 0
: we know that any number multiplied by 0
is 0
, so it is trivial to return this amount.
Upvotes: 2
Reputation: 724
your recursive funtion mult
gets called b
number of times. And at each time, you call the function you accumulate a
to the returned value. So you basically add a
b
number of times, hence resulting in the a*b
.
I would suggest you store change the line :
return a + mult(a, b - 1);
to
int temp = a + mult(a, b - 1); return temp
and watch the value of temp as your recursion unfolds.
Upvotes: 0