CODEWITHSUNDEEP
javafunctionrecursion
doniyor
doniyor

Reputation: 37846

Recursive definition of integer multiplication

This is the function that multiplies a and b: 

0    int mult(int a, int b){
1      if(a==0){
2        return 0;
3      } else{
4        a=a-1;
5        int c = mult(a,b);
6        int d = b + c;
7        return d;
8      }
9    }

I am playing with arguments 2 and 3: the result is 6, but why?

In line 5 I will get 0 after the second a=a-1; and then d is 3 then return 3 and not 6. Am I stupid or is it also confusing for you?

Upvotes: 1

Views: 1782

Answers (2)

Rohit Jain
Rohit Jain

Reputation: 213193

Let's go step by step [ mult(2, 3) ]: -

 1. (a = 2, b = 3) : - 
     a = 1;
     c = mult(1, 3); ---->    2. (a = 1, b = 3) : - 
                                  a = 0;
                                  c = mult(0, 3); -----> 3. (a = 0, b == 3) : -
                                                             return 0
---------------------------------------------------------------------------------
                                  c = 0;
                                  d = (b + c) = 3;
                                  return 3; 
------------------------------------------------------------------
     c = 3;
     d = b + c == 3 + 3 = 6

     return 6;

NOTE: -

States of recursive calls are stored on stack. So, as the base condition is reached, the stack starts unwinding, passing the result of the current call to the previous call, thus reaching the state where it started with a final result.

Upvotes: 5

Jon Skeet
Jon Skeet

Reputation: 1499770

You're getting confused by the recursion.

mult(2, 3):
  calls mult(1, 3)
    mult(1, 3):
      calls mult(0, 3)
        mult(0, 3):
          returns 0
      d = 3 + 0
      returns 3
  d = 3 + 3
  returns 6

Upvotes: 6

Related Questions