使用递归计算要打印的东西的数量

Question

我在学习递归，有一个例子，我解决了写 * 字符一定次数的问题。

例如：如果您要传递数字 3，它应该打印 2^3 颗星，这样它就会打印出 8 颗星。

我应该打印 2 ^ k 次，其中 k 是传递的整数。问题的答案是：

public String printStars(int k) {
    if (k == 0) 
        return "*";
    else 
        return printStars(k - 1) + printStars(k - 1); 
}

我似乎无法理解调用堆栈以及它如何解决问题，我的看法是，当我为 int k 传递 3 时，它会执行 n - 1 3 次，直到它达到基本情况，并且会 return 2 stars to the call before that, and since it takes 3 levels to get that deep, it would print 3 x 2 stars so it would print 6 stars.这很奇怪，因为大多数其他递归对我来说很容易，但这很令人困惑。

Answer 1

只需按照代码完成：

应该清楚，在非基础情况下：

printStars(k).length() == 2 * printStars(k - 1).length()

因为这种情况下的值由

给出

return printStars(k - 1) + printStars(k - 1);

利用这个观察，我们可以通过归纳法证明：

printStars(k).length() == 2^k

（其中^表示幂，而不是按位异或）

在基本情况下 printStars(0).length() == 2^0
假设 printStars(k - 1).length() == 2^(k-1)、printStars(k).length() == 2 * printStars(k - 1).length() == 2^k

QED.

Answer 2

我认为查看它的简单方法是展开每个函数调用：

当 k = 3 时，return 语句的计算结果为 printStars(2) + printStars(2)。

所以它会首先调用左边的 printStars(2)，它的计算结果是：

printStars(1) + printStars(1) + printStars(2)

同样，我们先展开左边的：

printStars(0) + printStars(0) + printStars(1) + printStars(2)

printStars(0) 最终将计算为 "*" 所以我们有

"*" + "*" + printStars(1) + printStars(2) == "**" + printStars(1) + printStars(2).

我们已经看到 printStars(1) == "**" 所以我们有：

"****" + printStars(2)。我们已经知道 printStars(2) 将解决什么问题。

Answer 3

我猜它一定总是 k 或 n？

递归如何工作：它跨越一棵树：

每次调用 printStars 都会导致一个 * (2^0) 或两个 * (2^1)。

如果你调用 printStars(4):

递归级别 4 ist != 0 所以它 return 是两个单独调用自身的收缩，每个调用都带有参数 (3)。

递归级别 3 ist != 0 所以它 return 是两个单独调用自身的收缩，每个调用都带有参数 (2)。

递归级别 2 ist != 0 所以它 return 是两个单独调用自身的收缩，每个调用都带有参数 (1)。

递归级别 1 ist != 0 所以它 return 是两个单独调用自身的收缩，每个调用都带有参数 (0)。

递归级别 0 ist == 0 所以每个调用 return 有一个 *.

回到递归级别 1，我们收到两个 * 和 contract 和 return 它们。

回到递归级别 2，我们收到两个 ** 和 contract 和 return 它们。

回到递归级别 3，我们收到两个 **** 和 contract 和 return 它们。

回到递归级别 4，我们收到两个 ******** 和 contract 和 return 它们。

所以调用方收到'***************' 2^4=16 *'s

caller                 |
k=4              /         \            (just call yourself 2 times an return contraction of both calls)
k=3          /     \     /     \        (just call yourself 2 times an return contraction of both calls)
k=2         / \   / \   / \   / \       (just call yourself 2 times an return contraction of both calls)
k=1        /\ /\ /\ /\ /\ /\ /\ /\      (just call yourself 2 times an return contraction of both calls)
k=0        ** ** ** ** ** ** ** **      (just return 2^0 = 1 '*')

使用递归计算要打印的东西的数量

Using Recursion to compute the number of something to print

java

recursion

exponent