递归和递归方法
我正在为我的计算机科学期末考试学习，在课堂上复习一些我从未完全掌握过的东西。主要是递归。我想我已经掌握了简单递归示例的诀窍，但我正在尝试完成一个在上一次考试中遇到的问题，并且很难弄清楚应该如何做。
以下是一个问题：
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)的值。这就是我被困的地方。如果其他的返回语句仅仅是n-1，我想我可以搞清楚，但n-1 + n-2完全把我甩了。
是否有人能解释这将如何工作，或分享一些链接，有类似的例子。我试着在网上和我的教科书里查到，但是我发现的例子要么是太先进了，我不知道发生了什么，要么是它们只处理返回n-1之类的事情，我已经知道该怎么做了。
回答 4
Stack Overflow用户
发布于 2014-08-08 04:59:41
让我们从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)等。
Stack Overflow用户
发布于 2014-08-08 04:54:22
您的实现很好，只有一个小错误--在应该用=替换==的条件下--这不是一个任务--这是一个比较。
顺便问一下，您希望您的方法返回到Tx(-1)吗？
Stack Overflow用户
发布于 2014-08-08 05:38:49
您已经正确地实现了它，只需用==更改=即可。
如果您想进一步降低时间复杂度，您可以将结果存储在一个全局数组中，这样您的函数就不会一次又一次地计算结果，这只会为大型计算节省一些时间。
你可以用这样的东西。
public int tx(int n , int []arr) {
if (arr[n] == 0) {
if (n == 1) {
arr[n] = 10;
}
else if (n == 2) {
arr[n] = 5;
}
else {
arr[n] = 2 * (tx((n - 1), arr) + tx((n - 2), arr));
}
}
return arr[n];
}https://stackoverflow.com/questions/25196203
复制相似问题
腾讯云开发者
