CODEWITHSUNDEEP
javarecursion
user5704428
user5704428

Reputation:

How to calculate multiplication of two numbers recursively

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

Answers (6)

Rodrigo M. Racanicci
Rodrigo M. Racanicci

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

Harsha
Harsha

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

Rishi
Rishi

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

Darshan Mehta
Darshan Mehta

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

Nathaniel Ford
Nathaniel Ford

Reputation: 21269

The best way to see how recursion, or loops, work, is to 'unwind' it:

  • You call 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.
  • The calling function then adds a (which is 2) and returns the result (2).
  • The previous calling function then adds a (which is 2) and returns the result (4).
  • The previous calling function then adds a (which is 2) and returns the result (6).
  • The previous calling function then adds 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

rahulbmv
rahulbmv

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

Related Questions