CODEWITHSUNDEEP
javarecursion
Matt Collicott
Matt Collicott

Reputation: 23

Using recursion to multiplying a sequence of numbers without local variables

This was a question on a past exam that had my fellow students and me stumped:

Use recursion to multiply together every number in a series without using local variables. Assume:

  • the parameters are positive
  • the first parameter is less than the second parameter
  • the result is less than 231

For example, rangeProduct(1, 5) should return 120, because 1x2x3x4x5 is 120

Use this method signature:

public static int rangeProduct(int valueOne, int valueTwo) {
    return ?;
}

If anyone knows how to do this, it's simply to benefit my learning and, if you're looking for some practice or simply feel empathy for a starving, moderately knowledgeable Computer Science major, then take a swing!

Upvotes: 1

Views: 619

Answers (5)

Bohemian
Bohemian

Reputation: 425033

Here's a 1-liner:

public static int rangeProduct(int valueOne, int valueTwo) {
    return valueOne * (valueOne == valueTwo ? 1 : rangeProduct(++valueOne, valueTwo));
}

See live demo.

Upvotes: 0

f1sh
f1sh

Reputation: 11934

Try this:

public static int rangeProduct(int valueOne, int valueTwo) {
  if(valueOne>=valueTwo)
    return valueOne;
  return rangeProduct(valueOne, valueTwo-1) * valueTwo;
}

executes the calculation in the exact order you specified:

1x2=2, 2x3=6, 6x4=24, 24x5=120

Upvotes: 3

Nahuel Fouilleul
Nahuel Fouilleul

Reputation: 19315

public static int rangeProduct(int valueOne, int valueTwo)
{
    // to avoid infinite loop if valueOne must be less or equal valueTwo
    if (valueOne > valueTwo) {
        throw new IllegalArgumentException();
    }
    // terminal case : return one over two values
    if (valueOne == valueTwo) {
        return valueOne;
    }
    // recursive call with range's size decreasing
    return valueOne * rangeProduct(valueOne+1, valueTwo);
}

To reduce the number of recursive calls the size can be decreased one both sides

public static int rangeProduct(int valueOne, int valueTwo)
{
    if (valueOne > valueTwo) {
        throw new IllegalArgumentException();
    }
    if (valueOne == valueTwo) {
        return valueOne;
    } else if (valueOne == valueTwo-1) {
        return valueOne*valueTwo;
    }
    return valueOne*valueTwo * rangeProduct(valueOne+1, valueTwo-1);
}

Upvotes: 0

paratrooper
paratrooper

Reputation: 465

That should not be hard at all.

Let's do this iteratively first to understand how this should work.

    public static int rangeProduct(int valueOne, int valueTwo)
    {
      int prod = 1;

      for(int i = valueOne; i <= valueTwo; i++) {
          prod *= i;
      }

      return prod;

    }

So doing this recursively would be just as simple:

    public static int rangeProduct(int valueOne, int valueTwo)
    {
        if (valueOne ==0 || valueTwo == 0) return 0;

        //Range check
        if (valueOne > valueTwo) return rangeProduct(valueTwo, valueOne);

        if (valueOne < 0 && valueTwo > 0) return 0; //Because 0 is always in this range

        if (valueOne == valueTwo) return valueTwo;  

        return valueTwo*rangeProd(valueOne, valueTwo-1);
    }

Logic used for recursion: Say you have a range (3,5) then :

(3,5) = 5*(3,4) = 5*4*(3,3) = 5*4*3 = 60
(-3, -1) = -1*(-3, -2) = -1*-2*(-3,-3) = -6
(-3, 5) = 0 (because this range includes 0)
(5, 3) is same as (3,5) so this can return 60 as well.
(3 ,3) --> now if both no's are same, answer is basically 3.

Hope this helps!

Upvotes: 0

melli-182
melli-182

Reputation: 1234

I think this could be a solution to your problem:

public static int rangeProduct(int valueOne, int valueTwo)
{
    if(valueOne <= valueTwo -1){
        valueOne++;
        return (valueOne-1) * rangeProduct(valueOne, valueTwo);
    }
    return valueTwo;
}

Upvotes: 0

Related Questions