请解释这个简单的代码：
public int fibonacci(int n) {
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
我对最后一行感到困惑，特别是因为如果n = 5，那么将调用fibonacci（4）+ fibonacci（3）等等但是我不明白这个算法如何计算索引5处的值方法。请详细说明！
在斐波那契序列中，每个项目是前两个项目的总和。所以，你写了一个递归算法。
所以，
fibonacci(5) = fibonacci(4) + fibonacci(3)
fibonacci(3) = fibonacci(2) + fibonacci(1)
fibonacci(4) = fibonacci(3) + fibonacci(2)
fibonacci(2) = fibonacci(1) + fibonacci(0)
现在你已经知道了fibonacci(1)==1 and fibonacci(0) == 0。因此，您可以随后计算其他值。
现在，
fibonacci(2) = 1+0 = 1
fibonacci(3) = 1+1 = 2
fibonacci(4) = 2+1 = 3
fibonacci(5) = 3+2 = 5
从斐波那契序列0,1,1,2,3,5,8,13,21....我们可以看到，对于5th element，斐波那契序列返回5。
在这里查看Recursion Tutorial。
Michael Goodrich等人在Java中的数据结构和算法中提供了一种非常聪明的算法，通过返回[fib（n），fib（n-1）]的数组，在线性时间内递归地求解fibonacci。
public static long[] fibGood(int n) {
if (n < = 1) {
long[] answer = {n,0};
return answer;
} else {
long[] tmp = fibGood(n-1);
long[] answer = {tmp[0] + tmp[1], tmp[0]};
return answer;
}
}
这产生fib（n）= fibGood（n）[0]。
在fibonacci序列中，前两个项目是0和1，每个其他项目是前两个项目的总和。即： 0 1 1 2 3 5 8 ...
所以第5项是第4项和第3项的总和。
Fibonacci序列是将数字的结果与从1开始的前一个结果相加的值。
so.. 1 + 1 = 2
2 + 3 = 5
3 + 5 = 8
5 + 8 = 13
8 + 13 = 21
一旦我们理解了Fibonacci是什么，我们就可以开始分解代码了。
public int fibonacci(int n) {
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
第一个if语句检查基本情况，循环可以突破。下面的else if语句也是如此，但它可以像这样重写...
public int fibonacci(int n) {
if(n < 2)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
现在已经建立了基本情况，我们必须理解调用堆栈。您对第一个调用“fibonacci”将是最后一个解决堆栈（调用序列），因为它们按照调用它们的相反顺序解析。最后一个方法首先解析，然后在该方法之前调用，依此类推......
因此，在使用这些结果“计算”任何内容之前，首先进行所有调用。如果输入为8，我们预计输出为21（见上表）。
斐波纳契（n - 1）一直被调用直到它到达基本情况，然后调用斐波那契（n - 2）直到它到达基本情况。当堆栈开始以相反的顺序对结果求和时，结果将如此...
1 + 1 = 1 ---- last call of the stack (hits a base case).
2 + 1 = 3 ---- Next level of the stack (resolving backwards).
2 + 3 = 5 ---- Next level of the stack (continuing to resolve).
他们继续冒泡（向后解决）直到将正确的金额返回到堆栈中的第一个调用，这就是你得到答案的方式。
话虽如此，该算法的效率非常低，因为它为代码分裂的每个分支计算相同的结果。更好的方法是“自下而上”的方法，其中不需要Memoization（缓存）或递归（深度调用堆栈）。
像这样......
static int BottomUpFib(int current)
{
if (current < 2) return current;
int fib = 1;
int last = 1;
for (int i = 2; i < current; i++)
{
int temp = fib;
fib += last;
last = temp;
}
return fib;
}
这里提供的大多数解决方案都以O（2 ^ n）复杂度运行。在递归树中重新计算相同的节点是低效的并且浪费CPU周期。
我们可以使用memoization使fibonacci函数在O（n）时间内运行
public static int fibonacci(int n) {
return fibonacci(n, new int[n + 1]);
}
public static int fibonacci(int i, int[] memo) {
if (i == 0 || i == 1) {
return i;
}
if (memo[i] == 0) {
memo[i] = fibonacci(i - 1, memo) + fibonacci(i - 2, memo);
}
return memo[i];
}
如果我们遵循自下而上的动态编程路线，下面的代码很简单，可以计算斐波纳契：
public static int fibonacci1(int n) {
if (n == 0) {
return n;
} else if (n == 1) {
return n;
}
final int[] memo = new int[n];
memo[0] = 0;
memo[1] = 1;
for (int i = 2; i < n; i++) {
memo[i] = memo[i - 1] + memo[i - 2];
}
return memo[n - 1] + memo[n - 2];
}
其他每一个答案：
（除此之外：这些都不是有效的;使用Binet's formula直接计算第n项）
这是一种递归方法，通过传递前一个答案和之前的答案来避免双递归调用。
private static final int FIB_0 = 0;
private static final int FIB_1 = 1;
private int calcFibonacci(final int target) {
if (target == 0) { return FIB_0; }
if (target == 1) { return FIB_1; }
return calcFibonacci(target, 1, FIB_1, FIB_0);
}
private int calcFibonacci(final int target, final int previous, final int fibPrevious, final int fibPreviousMinusOne) {
final int current = previous + 1;
final int fibCurrent = fibPrevious + fibPreviousMinusOne;
// If you want, print here / memoize for future calls
if (target == current) { return fibCurrent; }
return calcFibonacci(target, current, fibCurrent, fibPrevious);
}
它是显示或获得1 1 2 3 5 8输出的基本序列，它是下一个将显示当前数字的前一个数字之和的序列。
尝试观看Java Recursive Fibonacci sequence Tutorial下面的链接
public static long getFibonacci(int number){
if(number<=1) return number;
else return getFibonacci(number-1) + getFibonacci(number-2);
}
我认为这是一个简单的方法：
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int number = input.nextInt();
long a = 0;
long b = 1;
for(int i = 1; i<number;i++){
long c = a +b;
a=b;
b=c;
System.out.println(c);
}
}
}
RanRag（已接受）答案可以正常工作，但这不是优化的解决方案，除非按照Anil的回答进行记忆。
对于递归考虑下面的方法，TestFibonacci的方法调用是最小的
public class TestFibonacci {
public static void main(String[] args) {
int n = 10;
if (n == 1) {
System.out.println(1);
} else if (n == 2) {
System.out.println(1);
System.out.println(1);
} else {
System.out.println(1);
System.out.println(1);
int currentNo = 3;
calFibRec(n, 1, 1, currentNo);
}
}
public static void calFibRec(int n, int secondLast, int last,
int currentNo) {
if (currentNo <= n) {
int sum = secondLast + last;
System.out.println(sum);
calFibRec(n, last, sum, ++currentNo);
}
}
}
通过使用内部ConcurrentHashMap，理论上可能允许此递归实现在多线程环境中正常运行，我已经实现了一个同时使用BigInteger和Recursion的fib函数。需要大约53ms来计算前100个fib数。
private final Map<BigInteger,BigInteger> cacheBig
= new ConcurrentHashMap<>();
public BigInteger fibRecursiveBigCache(BigInteger n) {
BigInteger a = cacheBig.computeIfAbsent(n, this::fibBigCache);
return a;
}
public BigInteger fibBigCache(BigInteger n) {
if ( n.compareTo(BigInteger.ONE ) <= 0 ){
return n;
} else if (cacheBig.containsKey(n)){
return cacheBig.get(n);
} else {
return
fibBigCache(n.subtract(BigInteger.ONE))
.add(fibBigCache(n.subtract(TWO)));
}
}
测试代码是：
@Test
public void testFibRecursiveBigIntegerCache() {
long start = System.currentTimeMillis();
FibonacciSeries fib = new FibonacciSeries();
IntStream.rangeClosed(0,100).forEach(p -&R {
BigInteger n = BigInteger.valueOf(p);
n = fib.fibRecursiveBigCache(n);
System.out.println(String.format("fib of %d is %d", p,n));
});
long end = System.currentTimeMillis();
System.out.println("elapsed:" +
(end - start) + "," +
((end - start)/1000));
}
and output from the test is:
.
.
.
.
.
fib of 93 is 12200160415121876738
fib of 94 is 19740274219868223167
fib of 95 is 31940434634990099905
fib of 96 is 51680708854858323072
fib of 97 is 83621143489848422977
fib of 98 is 135301852344706746049
fib of 99 is 218922995834555169026
fib of 100 is 354224848179261915075
elapsed:58,0
这是一行斐波纳契递归：
public long fib( long n ) {
return n <= 0 ? 0 : n == 1 ? 1 : fib( n - 1 ) + fib( n - 2 );
}
您的代码有两个问题：
fibonacci(n - 1) + fibonacci(n - 2)
是非常错误的。
问题在于它称斐波那契不是50倍而是更多。
起初它叫斐波那契（49）+斐波那契（48），
下一个斐波那契（48）+斐波那契（47）和斐波那契（47）+斐波那契（46）
每次它变得斐波那契（n）更糟，所以复杂性是指数级的。非递归代码的方法：
double fibbonaci(int n){
double prev=0d, next=1d, result=0d;
for (int i = 0; i < n; i++) {
result=prev+next;
prev=next;
next=result;
}
return result;
}
只是为了补充，如果你想能够计算更大的数字，你应该使用BigInteger。
一个反复的例子。
import java.math.BigInteger;
class Fibonacci{
public static void main(String args[]){
int n=10000;
BigInteger[] vec = new BigInteger[n];
vec[0]=BigInteger.ZERO;
vec[1]=BigInteger.ONE;
// calculating
for(int i = 2 ; i<n ; i++){
vec[i]=vec[i-1].add(vec[i-2]);
}
// printing
for(int i = vec.length-1 ; i>=0 ; i--){
System.out.println(vec[i]);
System.out.println("");
}
}
}
http://en.wikipedia.org/wiki/Fibonacci_number更详细
public class Fibonacci {
public static long fib(int n) {
if (n <= 1) return n;
else return fib(n-1) + fib(n-2);
}
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
for (int i = 1; i <= N; i++)
System.out.println(i + ": " + fib(i));
}
}
使它尽可能简单，不需要使用while循环和其他循环
public class febo
{
public static void main(String...a)
{
int x[]=new int[15];
x[0]=0;
x[1]=1;
for(int i=2;i<x.length;i++)
{
x[i]=x[i-1]+x[i-2];
}
for(int i=0;i<x.length;i++)
{
System.out.println(x[i]);
}
}
}
public class FibonacciSeries {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
for (int i = 0; i <= N; i++) {
int result = fibonacciSeries(i);
System.out.println(result);
}
scanner.close();
}
private static int fibonacciSeries(int n) {
if (n < 0) {
return 1;
} else if (n > 0) {
return fibonacciSeries(n - 1) + fibonacciSeries(n - 2);
}
return 0;
}
}
使用while：
public int fib(int index) {
int tmp = 0, step1 = 0, step2 = 1, fibNumber = 0;
while (tmp < index - 1) {
fibNumber = step1 + step2;
step1 = step2;
step2 = fibNumber;
tmp += 1;
};
return fibNumber;
}
这个解决方案的优点是易于阅读和理解代码，希望它有所帮助
一个Fibbonacci序列是一个数字的结果，然后我们添加到前一个结果，我们应该从1开始。我试图找到一个基于算法的解决方案，所以我建立递归代码，注意到我保持以前的号码和我改变了位置。我正在搜索从1到15的Fibbonacci序列。
public static void main(String args[]) {
numbers(1,1,15);
}
public static int numbers(int a, int temp, int target)
{
if(target <= a)
{
return a;
}
System.out.print(a + " ");
a = temp + a;
return numbers(temp,a,target);
}
试试这个
private static int fibonacci(int n){
if(n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
欲了解更多信息，请查看thisOutput Fibonacci Series in Java - Mediocre Code
这是O（1）解决方案：
private static long fibonacci(int n) {
double pha = pow(1 + sqrt(5), n);
double phb = pow(1 - sqrt(5), n);
double div = pow(2, n) * sqrt(5);
return (long) ((pha - phb) / div);
}
Binet's Fibonacci number formula用于上述实施。对于大输入，long可以用BigDecimal替换。
public static long fib(int n) {
long population = 0;
if ((n == 0) || (n == 1)) // base cases
{
return n;
} else // recursion step
{
population+=fib(n - 1) + fib(n - 2);
}
return population;
}
Fibonacci系列是一个简单的代码，展示了动态编程的强大功能。我们从上学时间学到的只是通过迭代或最大递归代码来运行它。递归代码可以正常工作到20左右，如果你给出的数字大于你将会看到需要花费大量时间来计算的数字。在动态编程中，您可以按如下方式编码，计算答案需要几秒钟。
static double fib(int n) {
if (n < 2)
return n;
if (fib[n] != 0)
return fib[n];
fib[n] = fib(n - 1) + fib(n - 2);
return fib[n];
}
您将值存储在数组中，并仅在阵列无法为您提供答案时才进行新计算。
在伪代码中，其中n = 5，发生以下情况：
斐波那契（4）+斐波那契（3）
这分解为：
（斐波那契（3）+斐波那契（2））+（斐波那契（2）+斐波那契（1））
这分解为：
（（（fibonacci（2）+ fibonnacci（1））+（（fibonacci（1）+ fibonnacci（0）））+（（（fibonacci（1）+ fibonnacci（0））+ 1））
这分解为：
（（（（fibonacci（1）+ fibonacci（0））+ 1）+（（1 + 0））+（（1 + 0）+ 1））
这分解为：
((((1 + 0) + 1) + ((1 + 0)) + ((1 + 0) + 1))
这导致：5
鉴于斐波纳契数列是1 1 2 3 5 8 ...，第5个元素是5.您可以使用相同的方法来计算其他迭代。
简单的斐波那契
public static void main(String[]args){
int i = 0;
int u = 1;
while(i<100){
System.out.println(i);
i = u+i;
System.out.println(u);
u = u+i;
}
}
}
有时递归很难掌握。只需在一张纸上评估一小部分：
fib(4)
-> fib(3) + fib(2)
-> fib(2) + fib(1) + fib(1) + fib(0)
-> fib(1) + fib(0) + fib(1) + fib(1) + fib(0)
-> 1 + 0 + 1 + 1 + 0
-> 3
我不确定Java实际上是如何评估它的，但结果将是相同的。
您还可以简化您的功能，如下所示：
public int fibonacci(int n) {
if (n < 2) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
F(n)
/ \
F(n-1) F(n-2)
/ \ / \
F(n-2) F(n-3) F(n-3) F(n-4)
/ \
F(n-3) F(n-4)
需要注意的重要一点是该算法是指数的，因为它不存储先前计算的数字的结果。例如F（n-3）被称为3次。
有关更多详细信息，请参阅dasgupta第0.2章的算法
大多数答案都很好，并解释了斐波纳契的递归是如何工作的。
以下是对包括递归在内的三种技术的分析：
这是我测试所有三个的代码：
public class Fibonnaci {
// Output = 0 1 1 2 3 5 8 13
static int fibMemo[];
public static void main(String args[]) {
int num = 20;
System.out.println("By For Loop");
Long startTimeForLoop = System.nanoTime();
// returns the fib series
int fibSeries[] = fib(num);
for (int i = 0; i < fibSeries.length; i++) {
System.out.print(" " + fibSeries[i] + " ");
}
Long stopTimeForLoop = System.nanoTime();
System.out.println("");
System.out.println("For Loop Time:" + (stopTimeForLoop - startTimeForLoop));
System.out.println("By Using Recursion");
Long startTimeRecursion = System.nanoTime();
// uses recursion
int fibSeriesRec[] = fibByRec(num);
for (int i = 0; i < fibSeriesRec.length; i++) {
System.out.print(" " + fibSeriesRec[i] + " ");
}
Long stopTimeRecursion = System.nanoTime();
System.out.println("");
System.out.println("Recursion Time:" + (stopTimeRecursion -startTimeRecursion));
System.out.println("By Using Memoization Technique");
Long startTimeMemo = System.nanoTime();
// uses memoization
fibMemo = new int[num];
fibByRecMemo(num-1);
for (int i = 0; i < fibMemo.length; i++) {
System.out.print(" " + fibMemo[i] + " ");
}
Long stopTimeMemo = System.nanoTime();
System.out.println("");
System.out.println("Memoization Time:" + (stopTimeMemo - startTimeMemo));
}
//fib by memoization
public static int fibByRecMemo(int num){
if(num == 0){
fibMemo[0] = 0;
return 0;
}
if(num ==1 || num ==2){
fibMemo[num] = 1;
return 1;
}
if(fibMemo[num] == 0){
fibMemo[num] = fibByRecMemo(num-1) + fibByRecMemo(num -2);
return fibMemo[num];
}else{
return fibMemo[num];
}
}
public static int[] fibByRec(int num) {
int fib[] = new int[num];
for (int i = 0; i < num; i++) {
fib[i] = fibRec(i);
}
return fib;
}
public static int fibRec(int num) {
if (num == 0) {
return 0;
} else if (num == 1 || num == 2) {
return 1;
} else {
return fibRec(num - 1) + fibRec(num - 2);
}
}
public static int[] fib(int num) {
int fibSum[] = new int[num];
for (int i = 0; i < num; i++) {
if (i == 0) {
fibSum[i] = i;
continue;
}
if (i == 1 || i == 2) {
fibSum[i] = 1;
continue;
}
fibSum[i] = fibSum[i - 1] + fibSum[i - 2];
}
return fibSum;
}
}
结果如下：
By For Loop
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
For Loop Time:347688
By Using Recursion
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Recursion Time:767004
By Using Memoization Technique
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Memoization Time:327031
因此，我们可以看到memoization是最好的时间，并且循环匹配紧密。
但递归时间最长，在现实生活中可能应该避免。此外，如果您使用递归，请确保优化解决方案。
这是我发现的最好的视频，它完整地解释了Java中的递归和Fibonacci序列。
http://www.youtube.com/watch?v=dsmBRUCzS7k
这是他的序列代码，他的解释比我试图输入它更好。
public static void main(String[] args)
{
int index = 0;
while (true)
{
System.out.println(fibonacci(index));
index++;
}
}
public static long fibonacci (int i)
{
if (i == 0) return 0;
if (i<= 2) return 1;
long fibTerm = fibonacci(i - 1) + fibonacci(i - 2);
return fibTerm;
}
对于fibonacci递归解决方案，重要的是保存较小的斐波纳契数的输出，同时检索较大数的值。这称为“记忆”。
这是一个使用memoizing较小的fibonacci值的代码，同时检索更大的fibonacci数。此代码是高效的，不会产生多个相同功能的请求。
import java.util.HashMap;
public class Fibonacci {
private HashMap<Integer, Integer> map;
public Fibonacci() {
map = new HashMap<>();
}
public int findFibonacciValue(int number) {
if (number == 0 || number == 1) {
return number;
}
else if (map.containsKey(number)) {
return map.get(number);
}
else {
int fibonacciValue = findFibonacciValue(number - 2) + findFibonacciValue(number - 1);
map.put(number, fibonacciValue);
return fibonacciValue;
}
}
}