递归问题 - 这个解决方案是否正确，是否有更简单的解决方案?

Question

我是递归新手，我发现了以下Java问题：
编写一个函数，该函数获取整数n，并打印数字1！，2！，3,...,n！。
这是我所做的，我想知道这是否是最简单的解决方案(我不确定，因为我使用了"for"循环来做到这一点(。

public static void Print(int n) {
if (n == 0) {
System.out.print("1");
} else {
int temp = 1;
for (int i = 1; i <= n, i++) {
temp = temp * i;
}
Print(n-1);
System.out.print(temp);
}
}

顺便说一下，前面的练习是使用递归编写一个函数，该函数获取整数 n 并返回 n！。你认为我需要在这里使用它并打印它而不是计算温度 (n！( 并打印它吗？ 谢谢！

Answer 1

下面是一个简单的递归解决方案：

public static long factorial(long n) {
if(n == 0 || n == 1) {
System.out.print(1 + " ");
return 1;
}
long result = n * factorial(n - 1);
System.out.print(result + " ");
return result;
}

Answer 2

你写的东西是有效的，但是你正在重新计算一堆东西，并且你仍然使用for循环，而你可以递归地做这件事，用更少的代码。

假设你被困在函数Print(int n)，你可以写更少的代码，并且只计算一次每个阶乘，方法是从1向上递归并随之计算：

public static void Print(int n) {
PrintHelper(1, n, 1);
}
private static void PrintHelper(int i, int n, long factorial) {
if (i > n)
return;
factorial *= i;
System.out.println(factorial);
PrintHelper(i + 1, n, factorial);
}

这更易于阅读，更容易推理，并避免一遍又一遍地进行相同的计算。

在我上面发布的例子中，我正在做n乘法。在您的示例中，您正在执行大约n^2 / 2次乘法，因为您一次又一次地迭代每个数字(例如：1*2*3*...*50，然后是 1*2*3*...*49，然后是 1*2*3*...*48，...等(。

为了简洁起见，我编写的代码省略了错误检查，因为您可以简单地向其添加输入健全性检查。

Answer 3

没有递归

int temp = 1;
for (int i = 1; i <= 10; ++i) {
temp *= i;
}
System.out.println(temp);

递归是你的循环

public static void main(String[] args) {
System.out.println(print(10));
}
public static long print(long n) {
if (n == 0) {
return 1;
}
return n * print(n - 1);
}

输出

3628800

Answer 4

单行代码如下所示：

public static int factorial(int n) {
return (n <= 2) ? n : n * factorial((n-1));
}

三元运算符折叠 if 语句。然后使用递归，每个函数调用都成为阶乘函数中的一个因子，直到达到基本情况(n <= 2(：

4 * 阶乘(3(

4 * 3 * 阶乘(2(

4 * 3 * 2

Answer 5

使用递归来获取数字的阶乘(前面的练习(，此方法将如下所示

long factorial(long n) {
if (n > 0) {
return n*factorial(n - 1);
}
return 1;
}

鉴于此，最好不要使用递归，而只使用循环来获取数字的阶乘，如下所示：

long factorial(long n) {
long factorial = 1;
for (long i = 1; i <= n; i++) {
factorial *= i;
}
return factorial;
}

如果您想要系列中的所有数字

long[] factorials(long n) {
long[] factorials = new long[n+1];
long factorial = 1;
for (long i = 1; i <= n; i++) {
factorial *= i;
factorials[n] = factorial;
}
factorials[0] = 1;
return factorials;
}

如果只需要打印它们，则该方法变为

void factorials(long n) {
long factorial = 1;
System.out.println(factorial); // 0!
for (long i = 1; i <= n; i++) {
factorial *= i;
System.out.println(factorial);
}
}

Answer 6

这增加了打印，不会使递归表达式更难阅读。

public class Fact {
public static void main(String... args) {
fact(5L);
System.out.println();
}
static long fact(long n) {
return print(
n == 0 || n == 1 ? 1 : n * fact(n - 1));
}
static long print(long i) {
System.out.print(Long.toString(i));
return i;
}
}