java - 递归和递归方法

Question

我正在为我的计算机科学期末学习而复习一些我在类里面复习时从未完全掌握的东西。最主要的是递归。我想我已经掌握了简单递归示例的窍门，但我正在尝试完成之前考试中的一个示例，但我无法弄清楚应该如何完成。

问题是:

Texas numbers (Tx(n)) are defined as follows for non-negative numbers (assume true):
Tx(n) = 10                        if n is 0
Tx(n) = 5                         if n is 1
Tx(n) = 2*(Tx(n-1) + Tx(n-2)      if n >= 2

然后我们要写得克萨斯数的递归函数，测试后修正了一些，这是我想出的，我认为是正确的，但不是100%肯定。

public int Tx(int n) {
    if(n == 0)
        return 10;
    else if (n == 1)
        return 5;
    else
        return 2*(Tx(n-1) + Tx(n-2));
}

然后我们被要求计算 Tx(5) 的值。这就是我被困的地方。如果 else 的返回语句只是 n-1，我想我能弄明白，但是 n-1 + n-2 完全让我失望了。

任何人都可以解释这是如何工作的，或者分享一些具有类似示例的链接。我试过在网上和我的教科书中查找这个，但我发现的例子要么太高级以至于我不知道发生了什么，要么他们只处理像 return n-1 这样的事情，我已经知道该怎么做.

Answer 1

让我们从 Tx(2) 开始。 n > 1，所以我们有 2*(Tx(n-1) + Tx(n-2)) 即 2*(Tx(1) + Tx(0)).

但是我们已经知道了 Tx(1) 和 Tx(0)!所以只需将它们代入即可得到 2*(5 + 10) -> 30。太好了，现在我们知道了 T(2)。

T(3) 呢？ 2*(Tx(2) + Tx(1))。很好，我们也已经知道这些了 :) 同样，只需填写它们即可得到 2*(30 + 5) -> 70。

您可以向前移动到达 Tx(5)。

您的代码在逻辑上是正确的，您应该只使用 == 来测试相等性，单个 = 用于赋值。

当您运行您的方法时，它将向后工作并解决越来越小的子问题，直到达到已知答案的程度，这些是您的基本情况。

                    Tx(3)
  2*    Tx(2)         +        Tx(1)
  2*Tx(1) + Tx(0)               (5)
     (5)     (10)

为了使递归起作用，无论您每次将问题分解为更小的问题，都需要在基本情况下取得一些进展。如果没有，您将无限递归，直到您的计算机用尽空间来存储对同一函数的所有重复调用。

public int Tx(int n) {
    if(n == 0)
        return 10;
    else
        return Tx(n+1); // n will never reach 0!
}

Tx(1) 变为 Tx(2) -> Tx(3) -> Tx(4) -> Tx(5) 等