0

Addition information:

Chip doesn't support multiplication, only addition. I should work around this problem by creating a recursive method, mult(), that performs multiplication of x and y by adding x to itself y times. Its arguments are x and y and its return value is the product of x and y. I should then write the method and a main() to call it.

It's pure logical thinking, but I get lost every time I try to think what to do.

I am stuck at the math part.. What I have, that doesn't work and I know the math is wrong, but I am not good at this:

public static void mult(int x, int y) {
    x = 0;
    y = 0;
    if (y > 0) {
        for (int i = 0; i < y; i++) {
            x = x * (x * y);
            return mult(x, y);
        }
    }
}
Improve this question
4
  • 2
    "Can someone help me write the code?" No. But we can help when you face a concrete problem and guide you further. You could start by making it recursive, and then ask this again.. Commented Sep 28, 2013 at 12:36
  • 1
    Homework problems don't go down well here. Commented Sep 28, 2013 at 12:38
  • @Zavior It's recursive now, I guess. Can you point out where it goes wrong? Commented Sep 28, 2013 at 12:39
  • The recursion will never terminate. You need to figure out a condition to stop the recursing. Commented Sep 28, 2013 at 12:40

6 Answers 6

Reset to default
10

When I hear "recursion", I expect to see two things:

  1. A function calling itself with modified arguments each time.
  2. A stopping condition right at the top that tells the function when to stop, avoiding an infinite stack.

So where are yours? Start with writing those down in words before you write code.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

This sounds really good. I will write it down before proceeding to writing the code from now on..
3

One possibility is to use an accumulator which will store the current value of the multiplication. I replace missing statements by ??? :

public static void main(String []args){
        System.out.println(mult(2,5));
 }
    public static int mult(int x, int y) {
      if(???) return ???;
      else return multAcc(???,???,???);
    }

    private static int multAcc(int x, int y, int acc){
        if(???) return ???;
        else return multAcc(???, ???, ???);
    }
Improve this answer

Comments

2

... by adding x to itself y times.

You could actually do that, instead of multiplying. Oh, and maybe if you don't set both x and y to zero, you would have something to add ;-)

One last thing: If you want a recursive solution, you don't need the for-loop.

Improve this answer

Comments

2

Java has no TCO by design, so using recursion for linear (not tree-like) processes is very bad idea. Especially for such task, which will most likely become a bottleneck in your program. Use loop instead.

Oh, it must be recursive anyway? Looks like a homework task. Do it yourself then.

Improve this answer

6 Comments

Haha, yes it is some kind of 'homework', but I was actually stuck at the math part..
Tail call optimization isn't a requirement for an academic problem like this that's for the sake of exposure to recursion. No one in their right mind would ever use such a thing.
@Sarge Borsch, really funny :P
@duffymo Java is not good for introduction to programming in general either. If you know Java, you know, why. It can be better than C++, for example, but it doesn't mean that it is the right choice.
More importantly, it will blow up memory
|
2

All you need to remember is that a multiplication is a repeated addition (assuming that both operands are >= 0), so we have:

  • The base case is when y is zero
  • If y is not zero, then add x one more time, and subtract 1 from y

Notice that as long as y is positive, it'll eventually have a value of zero. So basically we keep adding x a total number of y times; this is what I mean:

public static int mult(int x, int y) {
    if (y == 0)
        return 0;
    return x + mult(x, y-1);
}

The same code can be written in a tail-recursive style, too - meaning: there's nothing to do after the recursive call returns, and this is important for certain languages that support a so-called tail-call optimization:

public static int mult(int x, int y, int accumulator) {
    if (y == 0)
        return accumulator;
    return mult(x, y-1, x + accumulator);
}

The above will get called as follows, noticing that the last parameter is always initialized in zero:

mult(10, 5, 0)
=> 50
Improve this answer

7 Comments

Should not do other peoples homework, at least not with direct answers :|
Thank for the solution and explanation. The problem was in the math side of this code. I have made more recursive programs in this section of the book. But this one was a little bit confusing because of the math..
@duffymo and Zavior : I wasn't finished writing yet. Mind reconsidering the down vote?
@ÓscarLópez Did you try your second solution with (mult(-2,-5, 0)); ?
I voted you down because you're doing too much of the work for the student.
|
1 
public static int mult(int x, int y) {
        if (y == 0) {
            return 0;
        }
        if (y > 0) {
            return x + mult(x, y - 1);
        } else {
            return -x + mult(x, y + 1);
        }
    }

this was the solution by the way

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.