Fibonacci(n) 的实现是如何工作的？ [递归]
我正在读的一本 Java 书中的一个练习让我感到困惑：
斐波那契数列是数字 1、1、2、3、5、8 的序列， 13、21、34 等，其中每个数字（从第三个开始）是总和 前两个。创建一个以整数作为参数的方法 参数并显示从 开始。例如，如果您运行 java Fibonacci 5（其中 Fibonacci 是 类的名称）输出将为：1, 1, 2, 3, 5。
我可以发誓它需要一个数组或某种方式来存储以前的数字，但当我看到答案时，它不是案例：
import java.util.*;
public class Fibonacci {
static int fib(int n) {
if (n <= 2)
return 1;
return fib(n-1) + fib(n-2);
}
public static void main(String[] args) {
// Get the max value from the command line:
int n = Integer.parseInt(args[0]);
if(n < 0) {
System.out.println("Cannot use negative numbers"); return;
}
for(int i = 1; i <= n; i++)
System.out.print(fib(i) + ", ");
}
}
有人能够解释如何在其内部使用函数来产生这个结果吗？
Theres an exercise from a Java book I'm reading that has me confused:
A Fibonacci sequence is the sequence of numbers 1, 1, 2, 3, 5, 8,
13, 21, 34, etc., where each number (from the third on) is the sum
of the previous two. Create a method that takes an integer as an
argument and displays that many Fibonacci numbers starting from the
beginning. If, e.g., you run java Fibonacci 5 (where Fibonacci is
the name of the class) the output will be: 1, 1, 2, 3, 5.
I could have swore that it would need an array or some way of storing the previous numbers but when I saw the answer it wasn't the case:
import java.util.*;
public class Fibonacci {
static int fib(int n) {
if (n <= 2)
return 1;
return fib(n-1) + fib(n-2);
}
public static void main(String[] args) {
// Get the max value from the command line:
int n = Integer.parseInt(args[0]);
if(n < 0) {
System.out.println("Cannot use negative numbers"); return;
}
for(int i = 1; i <= n; i++)
System.out.print(fib(i) + ", ");
}
}
Would someone be able to explain how using a function within itself produces this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您提供的代码是递归的示例解决方案。当函数第一次被调用时，它会一直执行，直到调用自身。它的状态存储在堆栈中，并且代码使用新的输入数据再次开始执行。重复这个过程，直到输入小于2，此时返回1，并将答案返回给前一个调用者。
例如，调用 fib(5) 会导致以下执行：
请注意，您是部分正确的。在此解决方案中，中间结果存储在堆栈中。这就是递归解决方案如此昂贵的原因之一。另一个是其
O(2^n)复杂度。但是，是否可以迭代计算Fibonacci(n)并且不存储所有先前的结果。您真正需要的只是存储最后的结果并从 1 计数到n。The code you gave is an example of a recursive solution. When the function is called for the first time, it executes until it calls itself. Its state is stored on the stack, and the code begins executing again with new input data. This process repeats until the input is less than 2, at which point 1 is returned, and the answer returns to the previous caller.
For example, calling fib(5) results in the following execution:
Note that you are partially correct. Intermediate results are stored on the stack in this solution. That is one of the reasons why the recursive solution is so expensive. The other is its
O(2^n)complexity. However, if is possible to computeFibonacci(n)iteratively and without storing all previous results. All you really need is to store the last to results and count from 1 up ton.这是一个递归解决方案。递归函数调用自身，直到满足给定的停止条件。然后每个调用都会退出，直到只剩下第一个调用。第一个调用输出结果。
在您的解决方案中，停止条件是：
在满足此条件之前，函数将连续调用自身。每次调用都会减少作为参数传递的 int。当达到 2 时，停止条件指示函数返回值 1（fibonacci(n) 中 n=1 和 n=2 的结果）。
因为斐波那契是最后两个数字的总和，所以函数的递归部分
对 n-1 和 n-2 求和（正如我所说，序列的最后两个数字）。当n等于2时，这些对函数fib的调用最终将有一个值，并将被返回。
例如，如果 n = 3，递归部分将调用 fib(2) 和 fib(1)，两者都等于或小于 2，因此两次调用都将返回 1。因此 printf 将打印 1, 1, 2。
2 是 1 + 1 的总和（我知道这很明显，但有时陈述明显的内容会有所帮助）。
This is a recursive solution. A recursive function calls itself until a given stop condition is met. Then each call exits until only the first call remains. That first call outputs the result.
In your solution, the stop condition is :
until this condition is met, the function will make successive calls to itself. Each call reduces the int passed as a parameter. When it reaches 2, the stop condition dictates that the function returns with value 1 (the result of n=1 and n=2 in fibonacci(n) ).
Because the fibonacci is the sum of the last two numbers, the recursive part of the function,
does a sum of n-1 and n-2 (as I said, the two last numbers of the sequence). When the n equals 2, these calls to function fib will finally have a value, and will be returned.
Example, if n = 3, the recursive part will call fib(2) and fib(1), both are equal or less than 2, so both calls will return 1. So the printf will print 1, 1, 2.
2 is the sum of 1 + 1 (I know it's obvious, but sometimes stating the obvious helps).
需要注意的重要一点是，该算法是指数算法，因为它不存储先前计算的数字的结果。例如 F(n-3) 被调用 3 次。
有关更多详细信息，请参阅 dasgupta 的算法第 0.2 章
Important point to note is this algorithm is exponential because it does not store the result of previous calculated numbers. eg F(n-3) is called 3 times.
For more details refer algorithm by dasgupta chapter 0.2
这是递归函数的标准示例。
斐波那契数也被声明为递归数。
fib(1)和fib(2)都声明为 1。所有其他值都是通过添加最后两个斐波那契数来计算的，因此fib(3)= fib(2)+fib(1)。将此与执行此操作的计算方法进行比较：
顺便说一下，这是一种使用两个变量计算斐波那契数的非常慢的方法（最后一个变量不需要所有变量，只需要最后两个变量！）并且循环的时间复杂度为 O(n)，上面的递归函数有 O(2^n) 次操作。
This is the standard example for an recursive function.
The Fibonacci Numbers are declared recursive, too.
Both
fib(1)andfib(2)are declared as 1. All others are calculated by adding the last two fibonacci numbers, sofib(3)=fib(2)+fib(1).Compare this to the calculation method which does exactly this:
By the way, this is a very slow way to calculate the fibonacci numbers, using two variables (you don't need all of them for the last one, only the last two!) and a loop is in O(n), the recursive function above has O(2^n) operations.