Code an integer multiplication function using recursion (in C)

Question

Can any body tell how to write a multiplication function (in C) using recursion?

Answer 1

Add it to itself over and over again, N times. That is if you want to multiply a number by N..

Answer 2

Here is the function:

int mulitplication(x,y)
{
    if (y==0)
    {
      return 0;
    }
    else
      return x+multiplication(x,y-1);
    }
}

Answer 3

You'll have to be way more specific if you want good help. But here's a recursive function in C that multiplies two positive integers:

int multiply(int multiplicand, int multiplier)
{
  if(multiplier == 0)
  {
    return 0;
  }
  return multiply(multiplicand, multiplier - 1) + multiplicand;
}

Jonathan Leffler wrote: And if multiplier is negative?

Ok:

int multiply(int multiplicand, int multiplier)
{
  if(multiplier == 0)
  {
    return 0;
  }
  if(multiplier < 0)
  {
    return multiply(multiplicand, multiplier + 1) - multiplicand; //Edit: changed "+ multiplicand" to "- multplicand"
  }
  return multiply(multiplicand, multiplier - 1) + multiplicand;
}

Mark Byers wrote: The negative version is still wrong.

Grumble, grumble. Serves me right for writing from memory and without testing. This one is tested for many integer ranges, negative and positive, odd and even. Should work for any integer value. Merry Wintereenmas.

Answer 4

if i am not wrong , is it like this...

int mul(int a, int b)
{
if(b==1)
return a;
else
return a+mul(a,b-1);
}

Answer 5

OK, let's be original. :)

unsigned int mul(unsigned int a, unsigned int b)
{
    if ( !a || !b ) return 0;
    if ( a == 1 ) return b;
    if ( b == 1 ) return a;

    return mul(a-1, b-1)+a+b-1;
}

Answer 6

Alternative version:

int mulInner(int a, int b, int c)
{
    if (b == 0)
        return a*c;
    return mulInner(a, b-1, c+1);
}
int mul(int a, int b)
{
    return multInner(a, b, 0);
}

Hey, he didn't say not to use the operator*...

Answer 7

If you really want to impress your peers and your teacher, submit this - it's both recursive and fast!

int mul(int a, int b)
{
    if ( a < 0 ) return -mul(-a,b);
    if ( b < 0 ) return -mul(a,-b);
    if ( b == 0 ) return 0;
    return (mul(a,b>>1)<<1)+(b&1?a:0);
}

Added: As an added bonus, this correctly handles both positive, negative and 0 values.

Answer 8

This only works if the first operand is larger than zero, but at least it's short and confusing. ;)

int mul(int a, int b) {
  return b + (--a ? mul(a, b) : 0);
}

However, I'm not sure that the evaluation order is defined, so you might have to move the decrement outside the expression:

int mul(int a, int b) {
  a--;
  return b + (a ? mul(a, b) : 0);
}

Answer 9

int mul(int a,int b) { if(b==1) return a; else return(a+(mul(a,b-1))); }

Answer 10

50 characters:

m(x,y){return!y?0:rand()%2?m(x,y+1)-x:m(x,y-1)+x;}

I do hope I score points for use of the rand() function (especially in that way), and general syntax niceties. Depending on your system library and the phase of the moon, be warned that recursion can lead to segfault for high values of the arguments, such as calculating 2 × 3.