斐波那契递归ex

同样，我仍然在使用递归，我有一个关于基本情况之一的问题。斐波那契递归ex

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 = = 1的地方。于是我将第一个基本情况改为n < = 1并得到了相同的答案。

现在的问题是，假设我调用的方法如下：FIB（2,3,6-）答案应该是= 21（与线2 =“N < = 1”）但是当第2行是“N < = 0”的答案是27

我想知道当n =最终1比2号线

来源

2013-10-16 Scarl

那么，接下来会发生什么呢，就是调用带有'n-1'和'n-2'的'fib'，并添加这些结果（您的最后一个块）。你为什么不在程序中调试这个或者写一些老学校的'System.out.println'消息并且看看你的自己？比在这里提问更快。 – Matthias

阅读[call stack]（http://en.wikipedia.org/wiki/Call_stack）和[递归]（http://en.wikipedia.org/wiki/Recursion_%28computer_science%29）上的wikipages –

给出“N < = 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-16 05:40:34 hocho

虽然这是一个答案，这并不回答原来的问题。似乎没有OP对Fibonacci序列的数学有问题，他对算法和递归的边界有更多的问题。 – Matthias

n为1时将产生与正为两个额外的递归调用呼叫0和n为-1。这两个递归调用将两次添加a到正确的答案。

来源

2013-10-16 05:46:51 necromancer

是的，这就是我想通了！谢谢 – Scarl

我其实回答了我自己的问题。

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

回报（FIB（2,3,2）+纤维蛋白原（2,3- ，1））

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

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

返回（FIB（2,3,2）+蛋白原（2,3,1））

然后Fib的（2,3,1）将导致再次调用的方法，并且将导致为n = 0，这将导致具有N = -1 & N = -2导致答案不同。

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

来源

2013-10-16 05:49:12 Scarl

你的意思是“这将导致有n = 0和n = -1导致答案不同”？ – necromancer

是的，我想我错误地输入了n值 – Scarl

你有两个基本情况都将最终打击，而不是返回n的将是正确的，它返回的一个通过和不变的变量a或b。

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

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

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

但是，当你看到它会计算所有severeal倍。如果你看到的顺序，你可以从一开始就具有两个数，a和b迭代，作为参数：

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

计算下一一个，你用的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-16 08:43:52 Sylwester

斐波那契递归ex

回答

相关问题