java 递归和乘法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16068643/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Recursion and multiplication
提问by SomeGuyWithFingers
Is this possible guys? This is homework I have, and my teacher obviously believes it is, but it seems to me that it's impossible not to use addition or multiplication outside of the short-multiplication method.
这可能吗伙计们？这是我的作业，我的老师显然相信是，但在我看来，在短乘法之外不使用加法或乘法是不可能的。
Write (and provide a tester for) a recursive algorithm:
int multiply(int x, int y)
to multiply two positive integers together without using the * operator. Do not just add x to itself y times!!!
(Hint: Write a recursive method that will multiply an integer by a value in the range 0 .. 10. Then write a second recursive method to implement the multiplication algorithm you learned to multiply multi-digit numbers in elementary school.)
编写（并提供测试器）递归算法：
int乘法（int x，int y）
在不使用 * 运算符的情况下将两个正整数相乘。不要只是将 x 添加到自身 y 次！！！
（提示：编写一个递归方法，将一个整数乘以 0 .. 10 范围内的一个值。然后编写第二个递归方法来实现你在小学学到的乘法算法。）
My issue is that once you break down any multi digit number and starting adding those together you have to use multiplication of numbers greater than 10, i.e 22 * 6 is 2 * 6 + 20 * 6 ... so am I totally missing something?
我的问题是，一旦你分解任何多位数字并开始将它们相加，你必须使用大于 10 的数字乘法，即 22 * 6 是 2 * 6 + 20 * 6 ......所以我完全错过了什么吗？
EDITI guess I should have added this is the code I have,
编辑我想我应该添加这是我拥有的代码，
public int mult(int x, int y){
return x == 0 ? 0 : (mult(x-1, y) + y);
}
which is perfect, but as far as I understand the instructions, that's breaking do not just add x to itself y times. I personally believe it isn't, but my teacher hasn't been very clear, and I'd like to know if there's some other way that I havn't thought of, sorry for the confusion.
这是完美的，但据我了解说明，这不仅仅是将 x 添加到自身 y 次。我个人认为不是，但我的老师不是很清楚，我想知道是否还有其他我没有想到的方法，抱歉造成混乱。
回答by CPerkins
Yes, it's possible. Yes, I think you're missing something. Try writing down the steps you'd follow to manually multiply two numbers, the way you learned in elementary school.
是的，这是可能的。是的，我认为你错过了一些东西。尝试按照您在小学学到的方法，写下您手动将两个数字相乘的步骤。
Then turn those steps into code.
然后将这些步骤转化为代码。
回答by Jesse Webb
My interpretation of the assignment is that the teacher would like the student to implement a recursive algorithm to perform Grid method multiplication(the kind we learn in elementary school).
我对作业的解释是，老师希望学生实现一个递归算法来执行网格法乘法（我们在小学学到的那种）。
For example, multiplying 34 x 13 would be done like so...
例如，乘以 34 x 13 会像这样完成......
34
* 13
====
12
90
40
+300
====
442
I didn't have easy access to a Java development environment, so I wrote the code in C# but the algorithm should be simple enough to convert into Java.
我无法轻松访问 Java 开发环境，所以我用 C# 编写了代码，但算法应该足够简单，可以转换为 Java。
public int Multiply(int x, int y)
{
if (x < 0) throw new ArgumentException("must be positive integer", "x");
if (y < 0) throw new ArgumentException("must be positive integer", "y");
if (x == 0 || y == 0) return 0; // obvious quick-exit condition
// integer division
int xDivBy10 = x / 10;
int yDivBy10 = y / 10;
bool xIsSingleDigit = xDivBy10 == 0;
bool yIsSingleDigit = yDivBy10 == 0;
// base case
if (xIsSingleDigit && yIsSingleDigit)
{
return MultiplySingleDigits(x, y);
}
// otherwise, use grid multiplication recursively
// http://en.wikipedia.org/wiki/Grid_method_multiplication
if (xIsSingleDigit) // y must not be a single digit
{
return (Multiply(x, yDivBy10) * 10) + Multiply(x, y % 10);
}
if (yIsSingleDigit) // x must not be a single digit
{
return (Multiply(xDivBy10, y) * 10) + Multiply(x % 10, y);
}
// else - x and y are both numbers which are not single digits
return (Multiply(x, yDivBy10) * 10) + Multiply(x, y % 10); // the same code as the "if (xIsSingleDigit)" case
}
// technically, this algorith can multiply any positive integers
// but I have restricted it to only single digits as per the assignment's requirements/hint
private int MultiplySingleDigits(int x, int y)
{
if (x < 0 || x > 9) throw new ArgumentException("must be in range 0 - 9 (inclusive)", "x");
if (y < 0 || y > 9) throw new ArgumentException("must be in range 0 - 9 (inclusive)", "y");
if (x == 0 || y == 0) return 0; // base case
return x + MultiplySingleDigits(x, y - 1);
}
NOTES:
笔记：
- This approach still uses the
*operator but not for actually multiplyingxandy, it is used to increase other sub-products by multiples of 10 - Many parts of this code could be simplified/refactored but I specifically left them expanded to make the steps more obvious
- 这种方法仍然使用
*运算符，但不是用于实际乘以xandy，它用于将其他子产品增加 10 的倍数 - 这段代码的许多部分都可以简化/重构，但我特意将它们进行了扩展以使步骤更加明显
回答by Maroun
Of course you can do it.
你当然可以做到。
First of all, think about the condition. If some number is 0, then the result is? Right.. zero.
首先，考虑条件。如果某个数为 0，那么结果是？对.. 零。
So.. You'll have if x is zero or y is zero return 0
所以..你会有 if x is zero or y is zero return 0
Now.. saying X * Y is like saying "X, Y times", which is like writing: X + .... + X (Y times).
现在.. 说 X * Y 就像说"X, Y times"，这就像写：X + .... + X (Y 次)。
So, you'll have something like:
所以，你会有类似的东西：
x + multiply(x, y - 1);
You'll have to consider the case in which one of the numbers is negative (But if you understand the basic, I believe you can easily do it).
您必须考虑其中一个数字为负的情况（但如果您了解基本知识，我相信您可以轻松做到）。
回答by Aurand
Easily possible.
很容易。
int multiply(int x, int y) {
if(y == 0) {
return 0;
}
return x + multiply(x, y - 1);
}
The above fails to take into account the case where y is negative, but you wouldn't want me to do all your work for you . . .
上面没有考虑到 y 为负的情况，但你不会希望我为你做所有的工作。. .
回答by rekinyz
This solution will work for both when y>=0 and y<0
当 y>=0 和 y<0 时，此解决方案将适用
public int multiply(final int x, final int y) {
if (y != 0 && x != 0) {
if (y > 0) {
return multiply(x, y - 1) + x;
} else {
return multiply(x, y + 1) - x;
}
}
return 0;
}
回答by polinens
static int Multiply(int x, int y)
{
if (y > 0 && x > 0)
return (x + Multiply(x, y - 1));
if (y < 0 && x > 0)
return -Multiply(x, -y);
if (x < 0 && y > 0)
return -Multiply(-x, y);
if (x < 0 && y < 0)
return Multiply(-x, -y);
return 0;
}
