我如何创建一个递归方法，该方法执行 n 的 exp，但在 Java 中返回字符串 n 次

Question

所以我正在做一个练习，但我在递归方法上遇到了不好的时间。

我希望该方法starPower将 2 的幂返回到星号 ("*"( 中的 n，但我得到堆栈溢出。

有人可以告诉我我做错了什么吗？

这是我到目前为止所拥有的：

public static String starPower(int n){
String str = "*";
if (n<0)
throw new IllegalArgumentException("n has an invalid value");
if (n==0)
{return str;
}     
return str + starPower( Math.pow(2,n-1));
}

Answer 1

不要使用Math.pow().您的方法应该是递归的并使用简单的操作。

我不会给你代码，但解释它应该如何工作。首先，以下是预期结果：

starPower(0) = "*"                                 // 2^0 = 1 stars
starPower(1) = "**"                                // 2^1 = 2 stars
starPower(2) = "****"                              // 2^2 = 4 stars
starPower(3) = "********"                          // 2^3 = 8 stars
starPower(4) = "****************"                  // 2^4 = 16 stars
starPower(5) = "********************************"  // 2^5 = 32 stars
starPower(6) = "****************************************************************"
. . .

如您所见，如果结果是双¹starPower(n)则结果为starPower(n - 1)的结果。那是你的简单递归。

^{1(双倍，我的意思是长度的两倍，即字符串与自身连接。}

Answer 2

您需要了解问题中输出的模式才能解决问题。

如果你能在每种情况下找到输入和输出之间的关系n你就可以解决它，这种思维方式被称为逆向工程。

正如 Andreas 在测试用例的回答中所说，您可以得出结论，starPower(n)是starPower(n - 1)结果的两倍：

starPower(0) = "*"                                
starPower(1) = "**"                                
starPower(2) = "****" 

因此，您只需要在每次递归调用中将"*"的结果加倍：

public static String starPower(int n){
if (n < 0){
throw new IllegalArgumentException("n has an invalid value");
}
if (n==0){
return "*";
}     
return starPower(n-1) + starPower(n-1);
}
public static void main(String[] args) {
System.out.println(starPower(3));
}

输出：

********

Answer 3

你必须递归地思考，这是非常困难的。 如果你连接了两个函数调用的结果n-1，你会有两半，形成一个整体。 但请注意，由于使用相同的输入调用该函数两次将产生两次相同的输出。 因此，您可以通过仅调用一次并使用结果两次来帮助减轻堆栈的负担。

尝试像这样可视化它，以举例调用starPower(3)。 它调用starPower(2)并将其结果与自身连接起来。 调用starPower(2)调用starPower(1)，并将结果与自身连接起来。starPower(1)调用starPower(0)，并将结果与自身连接起来。

starPower(0)总是返回"*";这是基本情况。 您现在可以从这里开始构建。starPower(1)拿了其中两个，把它们粘贴在一起做成"**"。starPower(2)连接其中两个以"****"。 希望现在有一种模式正在为你出现。 最后，starPower(3)取其中两个并将它们连接起来，得出"********"的最终结果，即 8 或 2³，星号。

3:        ********
2:    ****        ****
1:  **    **    **    **
0: *  *  *  *  *  *  *  *

下面是实现该解决方案的修改代码。

public static String starPower(int n) {
if (n < 0) {
throw new IllegalArgumentException("n has an invalid value");
}
if (n == 0) {
return "*";
}
String halfResult = starPower(n - 1);
return halfResult + halfResult;
}