blocks|key|456537|text|在fibonacci序列中，前两个项目是0和1，每个其他项目都是前两个项目的总和。即：|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|456538|0+1+1+2+3+5+8...|456539|所以第五项是第四项和第三项的总和。|456540|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Fibonacci_number^0|1|9|0|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@$A|Q|B|R|1|S]]|C|$]]|$1|D|3|E|5|6|7|T|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@]|C|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|C|$]]]|I|$J|$5|K|L|M|C|$N|O]]]]

in the <a href="http://en.wikipedia.org/wiki/Fibonacci_number" rel="nofollow">fibonacci</a> sequence, the first two items are 0 and 1, each other item is the sum of the two previous items. i.e: 
0 1 1 2 3 5 8...

so the 5th item is the sum of the 4th and the 3rd items.

blocks|key|456622|text|在斐波那契数列中，每一项都是前两项的总和。所以，你写了一个递归算法。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|456623|所以,|456624|fibonacci(5)+=+fibonacci(4)+%2B+fibonacci(3)

fibonacci(3)+=+fibonacci(2)+%2B+fibonacci(1)

fibonacci(4)+=+fibonacci(3)+%2B+fibonacci(2)

fibonacci(2)+=+fibonacci(1)+%2B+fibonacci(0)|code-block|syntax|javascript|456625|现在您已经了解了fibonacci(1)==1+and+fibonacci(0)+==+0。因此，您可以随后计算其他值。|offset|length|style|CODE|456626|现在,|456627|fibonacci(2)+=+1%2B0+=+1
fibonacci(3)+=+1%2B1+=+2
fibonacci(4)+=+2%2B1+=+3
fibonacci(5)+=+3%2B2+=+5|456628|从斐波那契数列，我们可以看到，对于5th+element，斐波那契数列返回5。|456629|有关Recursion+Tutorial的信息，请参阅此处。|456630|entityMap|0|LINK|mutability|MUTABLE|url|http://www.danzig.us/java_class/recursion.html^0|0|0|0|8|11|0|0|0|H|B|11|1|0|2|I|0|0^^$0|@$1|2|3|4|5|6|7|14|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|15|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|16|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|17|8|@$K|18|L|19|M|N]]|9|@]|A|$]]|$1|O|3|P|5|6|7|1A|8|@]|9|@]|A|$]]|$1|Q|3|R|5|F|7|1B|8|@]|9|@]|A|$G|H]]|$1|S|3|T|5|6|7|1C|8|@$K|1D|L|1E|M|N]|$K|1F|L|1G|M|N]]|9|@]|A|$]]|$1|U|3|V|5|6|7|1H|8|@]|9|@$K|1I|L|1J|1|1K]]|A|$]]|$1|W|3|-4|5|6|7|1L|8|@]|9|@]|A|$]]]|X|$Y|$5|Z|10|11|A|$12|13]]]]

In fibonacci sequence each item is the sum of the previous two. So, you wrote a recursive algorithm.

So, 

<pre><code>fibonacci(5) = fibonacci(4) + fibonacci(3)

fibonacci(3) = fibonacci(2) + fibonacci(1)

fibonacci(4) = fibonacci(3) + fibonacci(2)

fibonacci(2) = fibonacci(1) + fibonacci(0)
</code></pre>

Now you already know <code>fibonacci(1)==1 and fibonacci(0) == 0</code>. So, you can subsequently calculate the other values.

Now,

<pre><code>fibonacci(2) = 1+0 = 1
fibonacci(3) = 1+1 = 2
fibonacci(4) = 2+1 = 3
fibonacci(5) = 3+2 = 5
</code></pre>

And from fibonacci sequence <code>0,1,1,2,3,5,8,13,21....</code> we can see that for <code>5th element</code> the fibonacci sequence returns <code>5</code>.

See here for <a href="http://www.danzig.us/java_class/recursion.html" rel="noreferrer">Recursion Tutorial</a>.

blocks|key|670956|text|递归有时很难掌握。只需在一张纸上对一个小数字进行评估：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|670957|fib(4)
->+fib(3)+%2B+fib(2)
->+fib(2)+%2B+fib(1)+%2B+fib(1)+%2B+fib(0)
->+fib(1)+%2B+fib(0)+%2B+fib(1)+%2B+fib(1)+%2B+fib(0)
->+1+%2B+0+%2B+1+%2B+1+%2B+0
->+3|code-block|syntax|javascript|670958|我不确定Java实际上是如何评估这一点的，但结果将是相同的。|670959|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

Recursion can be hard to grasp sometimes. Just evaluate it on a piece of paper for a small number:

<pre><code>fib(4)
-&gt; fib(3) + fib(2)
-&gt; fib(2) + fib(1) + fib(1) + fib(0)
-&gt; fib(1) + fib(0) + fib(1) + fib(1) + fib(0)
-&gt; 1 + 0 + 1 + 1 + 0
-&gt; 3
</code></pre>

I am not sure how Java actually evaluates this, but the result will be the same.

blocks|key|456703|text|public+long+getFibonacci(+int+number)+{
++++if+(+number+<=2)+{
++++++++return+1;
++++}
++++long+lRet+=+0;
++++lRet+=+getFibonacci(+number+-1)+%2B+getFibonacci(+number+-2);
++++return+lRet;
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|456704|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>public long getFibonacci( int number) {
 if ( number &lt;=2) {
 return 1;
 }
 long lRet = 0;
 lRet = getFibonacci( number -1) + getFibonacci( number -2);
 return lRet;
}
</code></pre>

blocks|key|671018|text|它是一个基本序列，显示或得到输出为1+1+2+3+5+8。它是一个序列，下一个将显示上一个数字与当前数字之和。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|671019|尝试观看下面的链接Java递归Fibonacci序列教程|671020|public+static+long+getFibonacci(int+number){
if(number<=1)+return+number;
else+return+getFibonacci(number-1)+%2B+getFibonacci(number-2);
}|code-block|syntax|javascript|671021|单击此处Watch+Java+Recursive+Fibonacci+sequence+Tutorial查看汤匙进料|offset|length|671022|entityMap|0|LINK|mutability|MUTABLE|url|http://youtu.be/ajJ3K6-_OgM^0|0|0|0|4|1C|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|V|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|W|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|X|8|@]|9|@$K|Y|L|Z|1|10]]|A|$]]|$1|M|3|-4|5|6|7|11|8|@]|9|@]|A|$]]]|N|$O|$5|P|Q|R|A|$S|T]]]]

It is a basic sequence that display or get a output of
1 1 2 3 5 8
it is a sequence that the sum of previous number the current number will be display next. 

Try to watch link below Java Recursive Fibonacci sequence Tutorial

<pre><code>public static long getFibonacci(int number){
if(number&lt;=1) return number;
else return getFibonacci(number-1) + getFibonacci(number-2);
}
</code></pre>

Click Here <a href="http://youtu.be/ajJ3K6-_OgM" rel="nofollow">Watch Java Recursive Fibonacci sequence Tutorial</a> for spoon feeding

blocks|key|456827|text|这是我找到的最好的视频，它完整地解释了Java中的递归和斐波那契序列。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|456828|http://www.youtube.com/watch?v=dsmBRUCzS7k|offset|length|456829|这是他的序列代码，他的解释比我输入出来的更好。|456830|public+static+void+main(String[]+args)
{
++++int+index+=+0;
++++while+(true)
++++{
++++++++System.out.println(fibonacci(index));
++++++++index%2B%2B;
++++}
}
++++public+static+long+fibonacci+(int+i)
++++{
++++++++if+(i+==+0)+return+0;
++++++++if+(i<=+2)+return+1;

++++++++long+fibTerm+=+fibonacci(i+-+1)+%2B+fibonacci(i+-+2);
++++++++return+fibTerm;
++++}|code-block|syntax|javascript|456831|entityMap|0|LINK|mutability|MUTABLE|url^0|0|0|16|0|0|0|0^^$0|@$1|2|3|4|5|6|7|T|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|U|8|@]|9|@$D|V|E|W|1|X]]|A|$]]|$1|F|3|G|5|6|7|Y|8|@]|9|@]|A|$]]|$1|H|3|I|5|J|7|Z|8|@]|9|@]|A|$K|L]]|$1|M|3|-4|5|6|7|10|8|@]|9|@]|A|$]]]|N|$O|$5|P|Q|R|A|$S|C]]]]

This is the best video I have found that fully explains recursion and the Fibonacci sequence in Java.

<a href="http://www.youtube.com/watch?v=dsmBRUCzS7k" rel="noreferrer">http://www.youtube.com/watch?v=dsmBRUCzS7k</a>

This is his code for the sequence and his explanation is better than I could ever do trying to type it out.

<pre><code>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&lt;= 2) return 1;

 long fibTerm = fibonacci(i - 1) + fibonacci(i - 2);
 return fibTerm;
 }
</code></pre>

blocks|key|456874|text|作为补充，如果你想计算更大的数字，你应该使用BigInteger。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|456875|一个迭代的例子。|456876|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%2B%2B){
++++++++++++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("");
++++++++}
++++}
}|code-block|syntax|javascript|456877|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

Just to complement, if you want to be able to calculate larger numbers, you should use BigInteger.

An iterative example.

<pre><code>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&lt;n ; i++){
 vec[i]=vec[i-1].add(vec[i-2]);
 }
 // printing
 for(int i = vec.length-1 ; i&gt;=0 ; i--){
 System.out.println(vec[i]);
 System.out.println("");
 }
 }
}
</code></pre>

blocks|key|456879|text|public+class+Fibonaci{++++++

++++static+void+fibonacci()+{
++++++++int+ptr1+=+1,+ptr2+=+1,+ptr3+=+0;
++++++++int+temp+=+0;
++++++++BufferedReader+Data=new+BufferedReader+(new+InputStreamReader(System.in));
++++++++try+{
++++++++++++System.out.println("The+Number+Value's+fib+you+required+?+");
++++++++++++ptr3+=+Integer.parseInt(Data.readLine());

++++++++++++System.out.print(ptr1+%2B+"+"+%2B+ptr2+%2B+"+");
++++++++++++for+(int+i+=+0;+i+<+ptr3;+i%2B%2B)+{
++++++++++++++++System.out.print(ptr1+%2B+ptr2+%2B+"+");
++++++++++++++++temp+=+ptr1;
++++++++++++++++ptr1+=+ptr2;
++++++++++++++++ptr2+=+temp+%2B+ptr2;
++++++++++++}
++++++++}+catch(IOException+err)+{
++++++++++++System.out.println("Error!"+%2B+err);
++++++++}+catch(NumberFormatException+err)+{
++++++++++++System.out.println("Invald+Input!");
++++++++}
++++}

++++public+static+void+main(String[]args)throws+Exception{++++
++++++++++++Fibonaci.fibonacci();
++++}+++
+}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|456880|你可以这样做。|unstyled|456881|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|J|8|@]|9|@]|A|$]]|$1|G|3|-4|5|F|7|K|8|@]|9|@]|A|$]]]|H|$]]

<pre><code>public class Fibonaci{ 

 static void fibonacci() {
 int ptr1 = 1, ptr2 = 1, ptr3 = 0;
 int temp = 0;
 BufferedReader Data=new BufferedReader (new InputStreamReader(System.in));
 try {
 System.out.println("The Number Value's fib you required ? ");
 ptr3 = Integer.parseInt(Data.readLine());

 System.out.print(ptr1 + " " + ptr2 + " ");
 for (int i = 0; i &lt; ptr3; i++) {
 System.out.print(ptr1 + ptr2 + " ");
 temp = ptr1;
 ptr1 = ptr2;
 ptr2 = temp + ptr2;
 }
 } catch(IOException err) {
 System.out.println("Error!" + err);
 } catch(NumberFormatException err) {
 System.out.println("Invald Input!");
 }
 }

 public static void main(String[]args)throws Exception{ 
 Fibonaci.fibonacci();
 } 
 }
</code></pre>

You can do like this.

blocks|key|671179|text|更多细节中的http://en.wikipedia.org/wiki/Fibonacci_number|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|671180|public+class+Fibonacci+{

++++public+static+long+fib(int+n)+{
++++++++if+(n+<=+1)+return+n;
++++++++else+return+fib(n-1)+%2B+fib(n-2);
++++}

++++public+static+void+main(String[]+args)+{
++++++++int+N+=+Integer.parseInt(args[0]);
++++++++for+(int+i+=+1;+i+<=+N;+i%2B%2B)
++++++++++++System.out.println(i+%2B+":+"+%2B+fib(i));
++++}

}|code-block|syntax|javascript|671181|使它尽可能简单，不需要使用while循环和其他循环|671182|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Fibonacci_number^0|6|19|0|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@$A|T|B|U|1|V]]|C|$]]|$1|D|3|E|5|F|7|W|8|@]|9|@]|C|$G|H]]|$1|I|3|J|5|6|7|X|8|@]|9|@]|C|$]]|$1|K|3|-4|5|6|7|Y|8|@]|9|@]|C|$]]]|L|$M|$5|N|O|P|C|$Q|R]]]]

<a href="http://en.wikipedia.org/wiki/Fibonacci_number" rel="nofollow">http://en.wikipedia.org/wiki/Fibonacci_number</a> in more details

<pre><code>public class Fibonacci {

 public static long fib(int n) {
 if (n &lt;= 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 &lt;= N; i++)
 System.out.println(i + ": " + fib(i));
 }

}
</code></pre>

Make it that as simple as needed no need to use while loop and other loop

blocks|key|671208|text|Fibonacci系列是一个简单的代码，它展示了动态编程的力量。我们从学生时代学到的就是通过迭代或最大递归代码来运行它。递归代码直到20左右才能正常工作，如果你给出的数字大于20，你会看到它需要大量的时间来计算。在动态编程中，您可以按如下方式编写代码，并且需要秒来计算答案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|671209|static+double+fib(int+n)+{
++++if+(n+<+2)
++++++++return+n;
++++if+(fib[n]+!=+0)
++++++++return+fib[n];
++++fib[n]+=+fib(n+-+1)+%2B+fib(n+-+2);
++++return+fib[n];
}|code-block|syntax|javascript|671210|您将值存储在数组中，并仅当数组无法提供答案时才进行新的计算。|671211|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

Fibonacci series is one simple code that shows the power of dynamic programming. All we learned from school days is to run it via iterative or max recursive code. Recursive code works fine till 20 or so, if you give numbers bigger than that you will see it takes a lot of time to compute. In dynamic programming you can code as follows and it takes secs to compute the answer.

<pre><code>static double fib(int n) {
 if (n &lt; 2)
 return n;
 if (fib[n] != 0)
 return fib[n];
 fib[n] = fib(n - 1) + fib(n - 2);
 return fib[n];
}
</code></pre>

You store values in an array and proceed to fresh computation only when the array cannot provide you the answer.

blocks|key|671249|text|++++++++++++++++++++++++++++++++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)|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|671250|需要注意的重要一点是，该算法是指数型的，因为它不存储以前计算的数字的结果。例如F(n-3)被调用3次。|unstyled|671251|有关更多详细信息，请参阅dasgupta第0.2章的算法|671252|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|L|8|@]|9|@]|A|$]]|$1|G|3|H|5|F|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|F|7|N|8|@]|9|@]|A|$]]]|J|$]]

<pre><code> 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)
</code></pre>

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

blocks|key|457069|text|我认为这是一种简单的方法：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|457070|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%2B%2B){
++++++++++++long+c+=+a+%2Bb;
++++++++++++a=b;
++++++++++++b=c;
++++++++++++System.out.println(c);
++++++++}
++++}
}|code-block|syntax|javascript|457071|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

I think this is a simple way:

<pre><code>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&lt;number;i++){
 long c = a +b;
 a=b;
 b=c;
 System.out.println(c);
 }
 }
}
</code></pre>

blocks|key|671290|text|++++import+java.util.*;
/*
@+Author+12CSE54
@+Date+28.10.14
*/
++++public+class+cfibonacci
++++{
++++public+void+print(int+p)
++++{
++++int+a=0,b=1,c;
++++int+q[]=new+int[30];
++++q[0]=a;
++++q[1]=b;
++++for(int+i=2;i<p;i%2B%2B)
++++{
++++c=a%2Bb;
++++q[i]=c;
++++a=b;
++++b=c;
++++}
++++System.out.println("elements+are....\n");
++++for(int+i=0;i<q.length;i%2B%2B)
++++System.out.println(q[i]);
++++}
++++public+static+void+main(String+ar[])throws+Exception
++++{
++++Scanner+s=new+Scanner(System.in);
++++int+n;
++++System.out.println("Enter+the+number+of+elements\n");
++++n=sc.nextInt();
++++cfibonacci+c=new+cfibonacci();
++++c.printf(n);

++++}
++++}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|671291|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code> import java.util.*;
/*
@ Author 12CSE54
@ Date 28.10.14
*/
 public class cfibonacci
 {
 public void print(int p)
 {
 int a=0,b=1,c;
 int q[]=new int[30];
 q[0]=a;
 q[1]=b;
 for(int i=2;i&lt;p;i++)
 {
 c=a+b;
 q[i]=c;
 a=b;
 b=c;
 }
 System.out.println("elements are....\n");
 for(int i=0;i&lt;q.length;i++)
 System.out.println(q[i]);
 }
 public static void main(String ar[])throws Exception
 {
 Scanner s=new Scanner(System.in);
 int n;
 System.out.println("Enter the number of elements\n");
 n=sc.nextInt();
 cfibonacci c=new cfibonacci();
 c.printf(n);

 }
 }
</code></pre>

blocks|key|457155|text|Michael+Goodrich等人在Java的数据结构和算法中提供了一种非常聪明的算法，通过返回fib(n)，fib(n-1)的数组，在线性时间内递归地求解fibonacci。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|457156|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]+%2B+tmp[1],+tmp[0]};
++++++++return+answer;
++++}
}|code-block|syntax|javascript|457157|结果是fib(n)+=+fibGood(n)。|457158|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

Michael Goodrich et al provide a really clever algorithm in Data Structures and Algorithms in Java, for solving fibonacci recursively in linear time by returning an array of [fib(n), fib(n-1)].

<pre><code>public static long[] fibGood(int n) {
 if (n &lt; = 1) {
 long[] answer = {n,0};
 return answer;
 } else {
 long[] tmp = fibGood(n-1);
 long[] answer = {tmp[0] + tmp[1], tmp[0]};
 return answer;
 }
}
</code></pre>

This yields fib(n) = fibGood(n)[0].

blocks|key|457236|text|@chro说得很对，但他/她没有展示递归的正确方法。以下是解决方案：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|457237|class+Fib+{
++++static+int+count;

++++public+static+void+main(String[]+args)+{
++++++++log(fibWrong(20));++//+6765
++++++++log("Count:+"+%2B+count);+//+21891
++++++++count+=+0;
++++++++log(fibRight(20));+//+6765
++++++++log("Count:+"+%2B+count);+//+19
++++}

++++static+long+fibRight(long+n)+{
++++++++return+calcFib(n-2,+1,+1);
++++}

++++static+long+fibWrong(long+n)+{
++++++++count%2B%2B;
++++++++if+(n+==+0+%7C%7C+n+==+1)+{
++++++++++++return+n;
++++++++}+else+if+(n+<+0)+{
++++++++++++log("Overflow!");
++++++++++++System.exit(1);
++++++++++++return+n;
++++++++}+else+{
++++++++++++return+fibWrong(n-1)+%2B+fibWrong(n-2);
++++++++}

++++}

++++static+long+calcFib(long+nth,+long+prev,+long+next)+{
++++++++count%2B%2B;
++++++++if+(nth--+==+0)
++++++++++++return+next;
++++++++if+(prev%2Bnext+<+0)+{
++++++++++++log("Overflow+with+"+%2B+(nth%2B1)+
++++++++++++++++%2B+"+combinations+remaining");
++++++++++++System.exit(1);
++++++++}
++++++++return+calcFib(nth,+next,+prev%2Bnext);
++++}

++++static+void+log(Object+o)+{
++++++++System.out.println(o);
++++}
}|code-block|syntax|javascript|457238|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

@chro is spot on, but s/he doesn't show the correct way to do this recursively. Here's the solution:

<pre><code>class Fib {
 static int count;

 public static void main(String[] args) {
 log(fibWrong(20)); // 6765
 log("Count: " + count); // 21891
 count = 0;
 log(fibRight(20)); // 6765
 log("Count: " + count); // 19
 }

 static long fibRight(long n) {
 return calcFib(n-2, 1, 1);
 }

 static long fibWrong(long n) {
 count++;
 if (n == 0 || n == 1) {
 return n;
 } else if (n &lt; 0) {
 log("Overflow!");
 System.exit(1);
 return n;
 } else {
 return fibWrong(n-1) + fibWrong(n-2);
 }

 }

 static long calcFib(long nth, long prev, long next) {
 count++;
 if (nth-- == 0)
 return next;
 if (prev+next &lt; 0) {
 log("Overflow with " + (nth+1) 
 + " combinations remaining");
 System.exit(1);
 }
 return calcFib(nth, next, prev+next);
 }

 static void log(Object o) {
 System.out.println(o);
 }
}
</code></pre>

blocks|key|457252|text|+public+static+long+fib(int+n)+{
++++long+population+=+0;

++++if+((n+==+0)+%7C%7C+(n+==+1))+//+base+cases
++++{
++++++++return+n;
++++}+else+//+recursion+step
++++{

++++++++population%2B=fib(n+-+1)+%2B+fib(n+-+2);
++++}

++++return+population;
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|457253|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code> 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;
}
</code></pre>

blocks|key|671484|text|您还可以简化您的函数，如下所示：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|671485|public+int+fibonacci(int+n)++{
++++if+(n+<+2)+return+n;

++++return+fibonacci(n+-+1)+%2B+fibonacci(n+-+2);
}|code-block|syntax|javascript|671486|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

You can also simplify your function, as follows:

<pre><code>public int fibonacci(int n) {
 if (n &lt; 2) return n;

 return fibonacci(n - 1) + fibonacci(n - 2);
}
</code></pre>

blocks|key|457332|text|我发现了一种有效的方法来显示/打印著名的Fibonacci序列，而不是使用数组并做一些花哨的事情，只需两个加两个值就是浪费时间。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|457333|public+static+void+main(String+args[]){

++++++++System.out.println("This+program+lists+the+Fibonacci+sequence.");

++++++++int+answer+=+0;
++++++++int+startValue+=+1;
++++++++int+sum+=+0;

++++++++while+(answer+<+10000){

++++++++++++System.out.println(answer);

++++++++++++sum+=+add(answer,startValue);

++++++++++++startValue+=+answer;
++++++++++++answer+=+sum;+++++++++++++++
++++++++}+++
++++}
++++//This+method+return+the+sum+of+addition+
++++private+static+int+add(int+A,int+B){
++++++++++++return+A%2BB;
++++}|code-block|syntax|javascript|457334|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Instead of using an array and doing some fancy things just two add two values is waste of time, I have found an efficient way to display/print,the famous Fibonacci sequence.

<pre><code>public static void main(String args[]){

 System.out.println("This program lists the Fibonacci sequence.");

 int answer = 0;
 int startValue = 1;
 int sum = 0;

 while (answer &lt; 10000){

 System.out.println(answer);

 sum = add(answer,startValue);

 startValue = answer;
 answer = sum; 
 } 
 }
 //This method return the sum of addition 
 private static int add(int A,int B){
 return A+B;
 }
</code></pre>

blocks|key|457374|text|RanRag(accepted)答案可以很好地工作，但这并不是优化的解决方案，除非按照Anil+answer中解释的那样记住它。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|457375|对于递归考虑下面的方法，TestFibonacci的方法调用最少|offset|length|style|CODE|457376|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+%2B+last;
++++++++++++System.out.println(sum);
++++++++++++calFibRec(n,+last,+sum,+%2B%2BcurrentNo);
++++++++}
++++}

}|code-block|syntax|javascript|457377|entityMap^0|0|C|D|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|P|8|@$D|Q|E|R|F|G]]|9|@]|A|$]]|$1|H|3|I|5|J|7|S|8|@]|9|@]|A|$K|L]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

RanRag(accepted) answer will work fine but that's not optimized solution until and unless it is memorized as explained in Anil answer.

For recursive consider below approach, method calls of <code>TestFibonacci</code> are minimum

<pre><code>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 &lt;= n) {

 int sum = secondLast + last;
 System.out.println(sum);
 calFibRec(n, last, sum, ++currentNo);
 }
 }

}
</code></pre>

blocks|key|457430|text|这里提供的大多数解决方案的复杂度为O(2%5En)。在递归树中重新计算相同的节点效率很低，并且浪费CPU周期。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|457431|我们可以使用记忆法使fibonacci函数在O(n)时间内运行|457432|public+static+int+fibonacci(int+n)+{
++++return+fibonacci(n,+new+int[n+%2B+1]);
}

public+static+int+fibonacci(int+i,+int[]+memo)+{

++++if+(i+==+0+%7C%7C+i+==+1)+{
++++++++return+i;
++++}

++++if+(memo[i]+==+0)+{
++++++++memo[i]+=+fibonacci(i+-+1,+memo)+%2B+fibonacci(i+-+2,+memo);
++++}
++++return+memo[i];
}|code-block|syntax|javascript|457433|如果我们遵循自下而上的动态编程路线，下面的代码足够简单，可以计算斐波纳契数：|457434|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%2B%2B)+{
++++++++memo[i]+=+memo[i+-+1]+%2B+memo[i+-+2];
++++}
++++return+memo[n+-+1]+%2B+memo[n+-+2];
}|457435|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|P|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|Q|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|R|8|@]|9|@]|A|$]]|$1|K|3|L|5|F|7|S|8|@]|9|@]|A|$G|H]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

Most of solutions offered here run in O(2^n) complexity. Recalculating identical nodes in recursive tree is inefficient and wastes CPU cycles.

We can use memoization to make fibonacci function run in O(n) time

<pre><code>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];
}
</code></pre>

If we follow Bottom-Up Dynamic Programming route, below code is simple enough to compute fibonacci:

<pre><code>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 &lt; n; i++) {
 memo[i] = memo[i - 1] + memo[i - 2];
 }
 return memo[n - 1] + memo[n - 2];
}
</code></pre>

blocks|key|457457|text|简单斐波纳契数|type|unstyled|depth|inlineStyleRanges|entityRanges|data|457458|public+static+void+main(String[]args){

++++int+i+=+0;
++++int+u+=+1;

++++while(i<100){
++++++++System.out.println(i);
++++++++i+=+u%2Bi;
++++++++System.out.println(u);
++++++++u+=+u%2Bi;
++++}
++}
}|code-block|syntax|javascript|457459|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Simple Fibonacci

<pre><code>public static void main(String[]args){

 int i = 0;
 int u = 1;

 while(i&lt;100){
 System.out.println(i);
 i = u+i;
 System.out.println(u);
 u = u+i;
 }
 }
}
</code></pre>

blocks|key|457494|text|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%2B%2B)
+++{
++++++x[i]=x[i-1]%2Bx[i-2];
+++}
+++for(int+i=0;i<x.length;i%2B%2B)
+++{
++++++System.out.println(x[i]);
+++}
+}
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|457495|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>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&lt;x.length;i++)
 {
 x[i]=x[i-1]+x[i-2];
 }
 for(int i=0;i&lt;x.length;i++)
 {
 System.out.println(x[i]);
 }
 }
}
</code></pre>

blocks|key|457525|text|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%2B%2B)+{
++++++++++++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)+%2B+fibonacciSeries(n+-+2);
++++++++}
++++++++return+0;
++++}
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|457526|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>public class FibonacciSeries {

 public static void main(String[] args) {
 Scanner scanner = new Scanner(System.in);
 int N = scanner.nextInt();
 for (int i = 0; i &lt;= N; i++) {
 int result = fibonacciSeries(i);
 System.out.println(result);
 }
 scanner.close();
 }

 private static int fibonacciSeries(int n) {
 if (n &lt; 0) {
 return 1;
 } else if (n &gt; 0) {
 return fibonacciSeries(n - 1) + fibonacciSeries(n - 2);
 }
 return 0;
 }
}
</code></pre>

blocks|key|457646|text|Fibbonacci序列是将一个数字的结果与从1开始的前一个结果相加而得到的序列。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|457647|++++++so..+1+%2B+1+=+2
+++++++++++2+%2B+3+=+5
+++++++++++3+%2B+5+=+8
+++++++++++5+%2B+8+=+13
+++++++++++8+%2B+13+=+21|code-block|syntax|javascript|457648|一旦我们理解了Fibbonacci是什么，我们就可以开始分解代码了。|457649|public+int+fibonacci(int+n)++{
++++if(n+==+0)
++++++++return+0;
++++else+if(n+==+1)
++++++return+1;
+++else
++++++return+fibonacci(n+-+1)+%2B+fibonacci(n+-+2);
}|457650|第一个if语句检查基本情况，在那里循环可能会中断。下面的else+if语句也在做同样的事情，但它可以像这样重写。|457651|++++public+int+fibonacci(int+n)++{
++++++++if(n+<+2)
+++++++++++++return+n;

++++++++return+fibonacci(n+-+1)+%2B+fibonacci(n+-+2);
++++}|457652|现在已经建立了一个基本情况，我们必须理解对"fibonacci“的第一个调用将是最后一个在堆栈(调用序列)上解析的调用，因为它们是以调用它们的相反顺序进行解析的。最后调用的方法首先解析，然后在该方法之前调用最后一个方法，依此类推…|457653|所以，在用这些结果“计算”任何东西之前，所有的调用都是先进行的。在输入为8的情况下，我们预计输出为21+(见上表)。|457654|fibonacci(n+-+1)一直被调用，直到它到达基本情况，然后fibonacci(n+-+2)被调用，直到它到达基本情况。当堆栈开始以相反的顺序对结果求和时，结果将如下所示…|457655|1+%2B+1+=+1++++++++----+last+call+of+the+stack+(hits+a+base+case).
2+%2B+1+=+3++++++++----+Next+level+of+the+stack+(resolving+backwards).
2+%2B+3+=+5++++++++----+Next+level+of+the+stack+(continuing+to+resolve).|457656|它们一直向上冒泡(向后解析)，直到将正确的和返回给堆栈中的第一个调用，这就是您获得答案的方式。|457657|话虽如此，这个算法的效率非常低，因为它为代码拆分到的每个分支计算相同的结果。一种更好的方法是“自下而上”的方法，其中不需要记忆(缓存)或递归(深层调用堆栈)。|457658|像这样..。|457659|++++++++static+int+BottomUpFib(int+current)
++++++++{
++++++++++++if+(current+<+2)+return+current;

++++++++++++int+fib+=+1;
++++++++++++int+last+=+1;

++++++++++++for+(int+i+=+2;+i+<+current;+i%2B%2B)
++++++++++++{
++++++++++++++++int+temp+=+fib;
++++++++++++++++fib+%2B=+last;
++++++++++++++++last+=+temp;
++++++++++++}

++++++++++++return+fib;
++++++++}|457660|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|16|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|17|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|18|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|19|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|1A|8|@]|9|@]|A|$]]|$1|M|3|N|5|D|7|1B|8|@]|9|@]|A|$E|F]]|$1|O|3|P|5|6|7|1C|8|@]|9|@]|A|$]]|$1|Q|3|R|5|6|7|1D|8|@]|9|@]|A|$]]|$1|S|3|T|5|6|7|1E|8|@]|9|@]|A|$]]|$1|U|3|V|5|D|7|1F|8|@]|9|@]|A|$E|F]]|$1|W|3|X|5|6|7|1G|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|6|7|1H|8|@]|9|@]|A|$]]|$1|10|3|11|5|6|7|1I|8|@]|9|@]|A|$]]|$1|12|3|13|5|D|7|1J|8|@]|9|@]|A|$E|F]]|$1|14|3|-4|5|6|7|1K|8|@]|9|@]|A|$]]]|15|$]]

A Fibbonacci sequence is one that sums the result of a number when added to the previous result starting with 1.

<pre><code> so.. 1 + 1 = 2
 2 + 3 = 5
 3 + 5 = 8
 5 + 8 = 13
 8 + 13 = 21
</code></pre>

Once we understand what Fibbonacci is, we can begin to break down the code.

<pre><code>public int fibonacci(int n) {
 if(n == 0)
 return 0;
 else if(n == 1)
 return 1;
 else
 return fibonacci(n - 1) + fibonacci(n - 2);
}
</code></pre>

The first if statment checks for a base case, where the loop can break out. The else if statement below that is doing the same, but it could be re-written like so...

<pre><code> public int fibonacci(int n) {
 if(n &lt; 2)
 return n;

 return fibonacci(n - 1) + fibonacci(n - 2);
 }
</code></pre>

Now that a base case is establish we have to understand the call stack.Your first call to "fibonacci" will be the last to resolve on the stack (sequence of calls) as they resolve in the reverse order from which they were called. The last method called resolves first, then the last to be called before that one and so on...

So, all the calls are made first before anything is "calculated" with those results. With an input of 8 we expect an output of 21 (see table above).

fibonacci(n - 1) keeps being called until it reaches the base case, then fibonacci(n - 2) is called until it reaches the base case. When the stack starts summing the result in reverse order, the result will be like so...

<pre><code>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).
</code></pre>

They keep bubbling (resolving backwards) up until the correct sum is returned to the first call in the stack and that's how you get your answer.

Having said that, this algorithm is very inefficient because it calculates the same result for each branch the code splits into. A much better approach is a "bottom up" one where no Memoization (caching) or recursion (deep call stack) is required.

Like so...

<pre><code> static int BottomUpFib(int current)
 {
 if (current &lt; 2) return current;

 int fib = 1;
 int last = 1;

 for (int i = 2; i &lt; current; i++)
 {
 int temp = fib;
 fib += last;
 last = temp;
 }

 return fib;
 }
</code></pre>

blocks|key|457729|text|下面是一个一行的febonacci递归：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|457730|public+long+fib(+long+n+)+{
++++++++return+n+<=+0+?+0+:+n+==+1+?+1+:+fib(+n+-+1+)+%2B+fib(+n+-+2+);
}|code-block|syntax|javascript|457731|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Here is a one line febonacci recursive:

<pre><code>public long fib( long n ) {
 return n &lt;= 0 ? 0 : n == 1 ? 1 : fib( n - 1 ) + fib( n - 2 );
}
</code></pre>

blocks|key|457779|text|是的，记住每次递归方法调用的计算返回值是很重要的，这样你就可以在调用方法中显示序列。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|457780|在提供的实现中有一些改进。请找到下面的实现，它为我们提供了更多正确和通用的输出：|457781|import+java.util.HashMap;
import+java.util.stream.Collectors;

public+class+Fibonacci+{
private+static+HashMap<Long,+Long>+map;

public+static+void+main(String[]+args)+{
++++long+n+=+50;
++++map+=+new+HashMap<>();
++++findFibonacciValue(n);
++++System.out.println(map.values().stream().collect(Collectors.toList()));
}

public+static+long+findFibonacciValue(long+number)+{
++++if+(number+<=+1)+{
++++++++if+(number+==+0)+{
++++++++++++map.put(number,+0L);
++++++++++++return+0L;
++++++++}
++++++++map.put(number,+1L);
++++++++return+1L;
++++}+else+if+(map.containsKey(number))+{
++++++++return+map.get(number);
++++}+else+{
++++++++long+fibonacciValue+=+findFibonacciValue(number+-+1L)+%2B+findFibonacciValue(number+-+2L);
++++++++map.put(number,+fibonacciValue);
++++++++return+fibonacciValue;
++++}
}
}|code-block|syntax|javascript|457782|编号50的输出为：|457783|[0,+1,+1,+2,+3,+5,+8,+13,+21,+34,+55,+89,+144,+233,+377,+610,+987,+1597,+2584,+4181,+6765,+10946,+17711,+28657,+46368,+75025,+121393,+196418,+317811,+514229,+832040,+1346269,+2178309,+3524578,+5702887,+9227465,+14930352,+24157817,+39088169,+63245986,+102334155,+165580141,+267914296,+433494437,+701408733,+1134903170,+1836311903,+2971215073,+4807526976,+7778742049,+12586269025]|457784|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|P|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|Q|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|R|8|@]|9|@]|A|$]]|$1|K|3|L|5|F|7|S|8|@]|9|@]|A|$G|H]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

Yes, it's important to memorize your calculated return value from each recursion method call, so that you can display the series in calling method.

There are some refinement in the implementation provided. Please find below implementation which gives us more correct and versatile output:

<pre><code>import java.util.HashMap;
import java.util.stream.Collectors;

public class Fibonacci {
private static HashMap&lt;Long, Long&gt; map;

public static void main(String[] args) {
 long n = 50;
 map = new HashMap&lt;&gt;();
 findFibonacciValue(n);
 System.out.println(map.values().stream().collect(Collectors.toList()));
}

public static long findFibonacciValue(long number) {
 if (number &lt;= 1) {
 if (number == 0) {
 map.put(number, 0L);
 return 0L;
 }
 map.put(number, 1L);
 return 1L;
 } else if (map.containsKey(number)) {
 return map.get(number);
 } else {
 long fibonacciValue = findFibonacciValue(number - 1L) + findFibonacciValue(number - 2L);
 map.put(number, fibonacciValue);
 return fibonacciValue;
 }
}
}
</code></pre>

Output for number 50 is:

<pre><code>[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025]
</code></pre>

blocks|key|457809|text|使用while|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|457810|public+int+fib(int+index)+{
++++int+tmp+=+0,+step1+=+0,+step2+=+1,+fibNumber+=+0;
++++while+(tmp+<+index+-+1)+{
++++++++fibNumber+=+step1+%2B+step2;
++++++++step1+=+step2;
++++++++step2+=+fibNumber;
++++++++tmp+%2B=+1;
++++};
++++return+fibNumber;
}|code-block|syntax|javascript|457811|这种解决方案的优点是很容易阅读和理解代码，希望它能有所帮助|457812|entityMap^0|2|5|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@$9|P|A|Q|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|R|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|S|8|@]|D|@]|E|$]]|$1|M|3|-4|5|6|7|T|8|@]|D|@]|E|$]]]|N|$]]

Use <code>while</code>:

<pre><code>public int fib(int index) {
 int tmp = 0, step1 = 0, step2 = 1, fibNumber = 0;
 while (tmp &lt; index - 1) {
 fibNumber = step1 + step2;
 step1 = step2;
 step2 = fibNumber;
 tmp += 1;
 };
 return fibNumber;
}
</code></pre>

The advantage of this solution is that it's easy to read the code and understand it, hoping it helps

blocks|key|457872|text|Fibbonacci序列是将一个数字的结果相加，然后我们将其与前一个结果相加，我们应该从1开始。我试图根据算法找到解决方案，所以我构建了递归代码，注意到我保留了前一个数字，并改变了位置。我在搜索从1到15的Fibbonacci序列。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|457873|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+%2B+"+");

++++a+=+temp+%2B+a;

++++return+numbers(temp,a,target);
}|code-block|syntax|javascript|457874|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

A Fibbonacci sequence is one that sums the result of a number
then we have added to the previous result, we should started from 1.
I was trying to find a solution based on algorithm, so i build the recursive code, noticed that i keep the previous number and i changed the position. I'm searching the Fibbonacci sequence from 1 to 15. 

<pre><code>public static void main(String args[]) {

 numbers(1,1,15);
}


public static int numbers(int a, int temp, int target)
{
 if(target &lt;= a)
 {
 return a;
 }

 System.out.print(a + " ");

 a = temp + a;

 return numbers(temp,a,target);
}
</code></pre>

blocks|key|672133|text|尝尝这个|type|unstyled|depth|inlineStyleRanges|entityRanges|data|672134|private+static+int+fibonacci(int+n){
++++if(n+<=+1)
++++++++return+n;
++++return+fibonacci(n+-+1)+%2B+fibonacci(n+-+2);
}|code-block|syntax|javascript|672135|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Try this

<pre><code>private static int fibonacci(int n){
 if(n &lt;= 1)
 return n;
 return fibonacci(n - 1) + fibonacci(n - 2);
}
</code></pre>

blocks|key|672196|text|这是O(1)解：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|672197|+private+static+long+fibonacci(int+n)+{
++++double+pha+=+pow(1+%2B+sqrt(5),+n);
++++double+phb+=+pow(1+-+sqrt(5),+n);
++++double+div+=+pow(2,+n)+*+sqrt(5);

++++return+(long)+((pha+-+phb)+/+div);
}|code-block|syntax|javascript|672198|用于上述实现的+Binet's+Fibonacci+number+formula。对于大输入，可以用BigDecimal替换long。|offset|length|style|CODE|672199|entityMap|0|LINK|mutability|MUTABLE|url|http://mathworld.wolfram.com/FibonacciNumber.html^0|0|0|1E|A|1Q|4|7|X|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|W|8|@$I|X|J|Y|K|L]|$I|Z|J|10|K|L]]|9|@$I|11|J|12|1|13]]|A|$]]|$1|M|3|-4|5|6|7|14|8|@]|9|@]|A|$]]]|N|$O|$5|P|Q|R|A|$S|T]]]]

Here is O(1) solution :

<pre><code> 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);
}
</code></pre>

<a href="http://mathworld.wolfram.com/FibonacciNumber.html" rel="nofollow noreferrer"> Binet's Fibonacci number formula</a> used for above implementation.
 For large inputs <code>long</code> can be replaced with <code>BigDecimal</code>.

blocks|key|672276|text|我找不到一个简单的带有三元运算符的一行代码。所以这里有一个：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|672277|public+int+fibonacci(int+n)+{
++++return+(n+<+2)+?+n+:+fibonacci(n+-+2)+%2B+fibonacci(n+-+1);
}|code-block|syntax|javascript|672278|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

I could not find a simple one liner with a ternary operator. So here is one:
<pre><code>public int fibonacci(int n) {
 return (n &lt; 2) ? n : fibonacci(n - 2) + fibonacci(n - 1);
}
</code></pre>

Please explain this simple code:

<pre><code>public int fibonacci(int n) {
 if(n == 0)
 return 0;
 else if(n == 1)
 return 1;
 else
 return fibonacci(n - 1) + fibonacci(n - 2);
}
</code></pre>

I'm confused with the last line especially because if n = 5 for example, then fibonacci(4) + fibonacci(3) would be called and so on but I don't understand how this algorithm calculates the value at index 5 by this method. Please explain with a lot of detail!

Java recursive Fibonacci sequence

请解释一下这个简单的代码：public int fibonacci(int n)  {    if(n == 0)        return 0;    else if(n == 1)      return 1;   else      return fibonacci(n - 1) + fibonacci(n -...

问Java递归Fibonacci序列
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Java递归Fibonacci序列EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Java递归Fibonacci序列
EN