0

同样，我仍在使用递归，我有一个关于基本案例的问题。

UPD：a 和 b 表示序列中的第一个数字，n 是要计算的总和的所需位置。

我的代码如下：

public static int fib(int a, int b, int n) {

    if (n <=1) { 
        return a;
    } else if (n == 2) {
        return b;
    } else {
        return (fib(a, b, n - 1) + fib(a, b, n - 2));
    }
}

在第 2 行中，在我开始手动跟踪程序之前，我将其保留为 "n<=0" 。但是，当我跟踪并运行程序时，我得到了一个不同的答案。问题出在某个时刻 n will = to 1。所以我将第一个基本情况更改为 n<=1 并得到了相同的答案。

现在的问题是，假设我按如下方式调用该方法： fib(2,3,6) 答案应该是 = 21 （第 2 行 = "n<=1"）但是当第 2 行是 "n<=0"答案是 27。

我想知道当 n 最终 = 1 给定第 2 行中的 "n<=0" 时程序会发生什么

4

4 回答 4

1

n 为 1 时的调用将生成两个额外的递归调用，其中 n 为 0，n 为 -1。这两个递归调用将使a正确答案加倍。

于 2013-10-16T05:46:51.870 回答
0

要获得第 n 个斐波那契，只需将 n 传递给函数。

假设序列是 0, 1, 1, 2, 3 ...

你的算法将是

if n = 1 return 0
else if n = 2 return 1
else return fib(n - 2) + fib(n - 1)
于 2013-10-16T05:40:34.283 回答
0

您有两种基本情况，两者最终都会命中，而不是返回正确的 n ，而是返回传递和未更改的变量之一a或b.

您的代码是计算斐波那契数列的两种不同方法的混乱组合。你有一个非常低效的递归：

public static int fib(int n) {
    if (n <=1)
        return n;

    return fib(n-1) + fib(n-2);
}

但是，正如您所看到的，它将计算一切严重的时间。如果您看到序列，您可以通过将两个数字 a 和 b 作为参数从头开始迭代：

a 0 1 1 2 3 5 ...
b 1 1 2 3 5 8 ...

要计算下一个 a，请使用 b。要计算新的 a，请添加 a 和 b。因此，更有效的算法是：

public static int fib(int a, int b, int n) {
    if (n <= 0)
        return a;

    return fib(b, a+b, n-1);
}

Java 没有尾调用优化，因此递归不会像其他优化尾调用的语言那样工作，因此非递归版本会更好，例如：

public static int fib(int n) {
    for(int a=0, b=1;; n--) {
        if (n <= 0)
           return a;
        int tmpa = a;
        a = b;
        b += tmpa;
    }
}
于 2013-10-16T08:43:52.470 回答
0

我实际上回答了我自己的问题。

你在某个点看到 n = 3，所以要返回的值最终会导致 n = 1，如下所示：

返回 (Fib(2,3,2)+ Fib(2,3,1))

现在 n = 1 将正确执行第 2 行中的基本情况。

而如果第 2 行中的基本情况是“n<=0”，那么对于 n =3 的情况

返回 (Fib(2,3,2) + Fib(2,3,1))

那么 Fib(2,3,1) 将导致该方法再次被调用，并将导致 n =0，这将导致n = -1 & n =-2导致答案不同。

//更新：n =0 & n=-1 将导致答案不同

于 2013-10-16T05:49:12.623 回答