writing a recursive function to multiply 2 integers, with a twist

Question

This is a homework assignment of mine. It would also seem as though people on this forum ask for help with similar functions, but I couldn't find anything relevant enough for me to use.

Here it is;

The Nat multiply(Nat a, Nat b) function takes to 2 Nat type values. They contain a int theValue value, and a bool isValid value. The second is mostly irrelevant (as far as I am concerned.)

I'm trying to multiply these two Nat values. This is what I have currently, although it's changing frequently as I become more and more frustrated with it; [EDIT] -> here's a slightly revised edition;

    if(b.theValue == 1){
    return a;
}
else if(a.theValue == 0 || b.theValue == 0){
    a.theValue = 0;
    return a;
}
else{
    a = add(a, a);
    b = decrement(b);
    return multiply(a, b);
}

[EDIT] it's working for values of 1 and zero. I'm going to implement your helpful hints.

The limitations are that I cannot use the '+' operator directly, or the '*' operator directly, and it has to be recursive. I can however use a increment and decrement function that take one Nat argument, and increase it by one. I may also use an add and subtract function which I wrote myself and have tested extensively.

Mostly, I think I'm having a problem understand how I can modify these values without affecting how many times the other is changed. ie; how can reach the base case while adding the SAME value for b to a? I sort of grasp the concept of recursion, but this problem is troubling me.

As you can probably see, I'm not sure what I'm doing. The answers that this function is giving me are WAY off.

Any help is appreciated, and thanks in advance.

[EDIT] These are helping and I'm getting closer haha thanks.

[EDIT] I got a teacher to help and he pointed out the seemingly obvious solution. Here it is without changing the header in case others come searching;

    if(b.theValue == 1){
    return a;
}
else if(a.theValue == 0 || b.theValue == 0){
    a.theValue = 0;
    return a;
}
else{

    //a = add(a, a);
    b = decrement(b);

    return add(a , multiply(a, b));
}

I was skipping some fundamental thought process associated with recursion. This makes perfect sense to me now though. Thanks again guys.

Answer 1

I think I am in the same class as you and if so I have something really important to mention that will crucially change your entire answer. In the function it mentions this:

// you may not access the fields in the Nats directly

Which means you cannot use a.theValue or b.theValue at all in this question. If you do you will get 0 marks on that function. To confirm that you have my assignment do you by any chance have a function called bool zero (Nat n)? If so you have to use those functions like the other functions such as increment, decrement, and NotANat.

These are the functions that you should use on add, multiply, and subtract:

// given an integer, create a Nat
// This is the only way you should create Nats!
bool NotANat(Nat n)
{
    return !(n.isValid);
}

// given a Nat, check if it is zero or not
bool zero(Nat n)
{
    if (n.isValid) {
        return n.theValue == 0;
    }
    else
    {
        return false;
    }
}

// given a Nat, returns a Nat one less
// Note: we cannot allow this function to produce a negative value
// so to avoid that, we'll set the invalid flag

Nat decrement(Nat n)
{
    if (n.isValid && n.theValue > 0)
    {
        n.theValue = n.theValue - 1;
    }
    else
    {
        n.isValid = false;
    }
    return n;
}

// given a Nat, returns a Nat one greater
Nat increment(Nat n)
{
    if (n.isValid) {
        n.theValue = n.theValue + 1;
    }
    return n;
}

Since I am in your class and cannot discuss the answer due to academic honesty, however I can tell you what you can do. For the most part you have the question right, however your base case statement should use the zero function.

EDIT: Since the assignment is done I can give the answer now. Here's what I had for my assignment and I tested it multiple times and it works:

// ToDo: add()
//       given 2 Nats a,b, return a Nat that represents the sum a+b
//       you may not use + directly
//       you may not access the fields in the Nats directly
//       you must use recursion!
//       you may use any functions already defined for Nat

Nat add(Nat a, Nat b)
{
    if (zero(b)){
        return a;
    } else {
            return add(increment(a), decrement(b));
    }
}


// ToDo: multiply()
//       given 2 Nats a,b, return a Nat that represents the product a*b
//       you may not use * or + directly
//       you may not access the fields in the Nats directly
//       you must use recursion!
//       you may use any functions already defined for Nat
//       Hint: you should use add()

Nat multiply(Nat a, Nat b)
{
    if(zero (b)){
        return b;
    } else {
        return add(a, multiply(a, decrement(b)));
    }
}


// ToDo: subtract()
//       given 2 Nats a,b, return a Nat that represents the difference a-b
//       you may not use - directly
//       you may not access the fields in the Nats directly
//       you must use recursion!
//       you may use any functions already defined for Nat

Nat subtract(Nat a, Nat b)
{
    if (zero(b)){
       if(NotANat(a){
          return a;
       }else{
          return a;
       }
    } else {
        return subtract(decrement(a), decrement(b));
    }
}

So basically what is going on is I am using "bool zero(nat n)" as my base case statement for all three functions because that is the only primitive function that a user can use without directly accessing the fields in your function. We return b in the multiply function because when b is zero it will return 0 therefore the function is satisfied. Your example mentions if b is one then it will return a as the base case. In most cases that is the common way to answer it but as I mentioned you cannot use fields which would mean that function would be marked as zero. Therefore this is one way of doing the answer. The whole point of this assignment isn't being able to multiply using a function but rather to use your knowledge to make primitive functions work and to use recursion properly. I maybe explaining this wrong since this is my first year into this, but if anyone would like to expand to this it would be greatly appreciated.

Answer 2

You should step through this by hand with a simple multiplication, such as 2*1… you'll probably see that the problem is in a = add(a, b);. a*b is a+a+a+a+… until you have b total terms of a. Your routine is adding b in when it should only be decrementing b (which is effectively an addition counter).

To set this up as a recursive routine, you're actually going to need a 3rd parameter… something to store the value to be added, so you can a = add(a, original_a); -- the original_a should not be modified throughout the operation.

Nat multiply(Nat a, Nat b)
{
    if (a.theValue == 0) return a;
    if (b.theValue == 0) return b;
    return recursive_multiply(a, b, a);
}

Nat recursive_multiply(Nat a, Nat b, Nat adder)
{
    if (b.theValue == 0) return a;
    a = add(a, adder);
    b = decrement(b);
    return recursive_multiply(a, b, adder);
}