面试题目：如何实现费波纳契数列使java用递归方法？？？

Question

高手来实现一下，拓宽点儿思维。

Answer 1

Fibonacci数列Fib(n),当n=0的时候Fib(n)=0,当n=1的时候Fib(n)=1,其他情形Fib(n)=Fib(n-1)+Fib(n-2)
public class Fibonacci {
public static int fun(int n)
{
if(n==0)
{
return 0;
}
else if(n==1)
{
return 1;
}
else
{
return fun(n-1)+fun(n-2);
}
}
public static void main(String[] args)
{
System.out.println(fun(1));//参数可以自己设置
}
}

Answer 2

public class Fibonacci {
public static int fun(int n)
{
if(n==0)
{
return 0;
}
else if(n==1)
{
return 1;
}
else
{
return fun(n-1)+fun(n-2);
}
}
public static void main(String[] args)
{
int n=12;
for(int i=1;i<n;i++)
{
System.out.print(fun(i)+" ");
}
}
}

Answer 3

面试出这题一定是考基础。
f(n)=f(n-1）+ f(n-2)
fun(int n)
{
    if(n==0 || n==1)
     return n;
    else
     return f(n-1) + f(n-2);
}

Answer 4

基础很重要，分:->给For_suzhen

Answer 5

这个感觉不是那么简单，要考虑到int的取值范围及对超过取值范围后的处理

Answer 6

class Feb 
{
public static void main(String[] args) 
{
if (args.length<=0)
{
            System.out.println("请输入参数！");
}
int n = Integer.parseInt(args[0]);
        for(int i=1;i<=n;i++)
        {
            System.out.print(Feb(i)+" ");
        }
} public static long Feb(int n)
{
if (n==0)
{
return 0;
}else if (n==1)
{
return 1;
}else
{
return Feb(n-1)+Feb(n-2);
}
    }
}
---------------------------------------
效率比较低，数字稍微一大的话出来的值是很慢的。

Answer 7

<<Programming abstractions in c>>
上有详细说明

Answer 8

package xcjtest;
public class XcjTest {
public static long Fibonacci(int n,int k,int last1,int last2){
        if(n==0){
return 0;
}
else if(n==1){
return 1;
}
else if(n==k){
return last1+last2;
}
else{
int last3=last1+last2;
return(Fibonacci(n,k+1,last2,last3));
}
}
public static void main(String[] args) {
long i=Fibonacci(8,2,0,1);
System.out.printf("%d\n", i);
}
}
麻烦一点,但效率高,用空间换时间!

Answer 9

1、循环实现
int fun(int n) {
int sum = 0, tmp1=1, tmp2 = 1; 
if (n < 2)
return 1; 
for(int i = 2; i <= n; i++) {
sum = tmp1 + tmp2; 
tmp2 = tmp1; 
tmp1 = sum; 
}
return sum; 
}
2、递归实现
int fun1(int n) {
int sum = 0; 
if (n < 2)
return 1; 
for(int i = 2; i <= n; i++) {
sum = fun1(i-2) + fun1(i-1);  
}
return sum; 
}

Answer 10

当年学java时试验的代码，找找还在，呵呵
  如下：import java.awt.event.*;
import java.awt.*;import javax.swing.*;
public class Fibonacci extends JApplet implements ActionListener {
    
JLabel numberLabel,resultLabel;
JTextField numberField,resultField;

public void init(){

Container container=getContentPane();
container.setLayout(new FlowLayout());

numberLabel = new JLabel("Enter a integer and press ENTER");
container.add(numberLabel);

numberField = new JTextField(10);
container.add(numberField);

numberField.addActionListener(this);

resultLabel = new JLabel("Fibonacci number is : ");
container.add(resultLabel);

resultField = new JTextField(15);
resultField.setEditable(false);
container.add(resultField);
}

public void actionPerformed(ActionEvent arg0) {

long number,fibonacciValue;

number = Long.parseLong(numberField.getText());
showStatus("calculating...");

fibonacciValue=fibonacci(number);

showStatus("done.");
resultField.setText( Long.toString(fibonacciValue)); }

public long fibonacci(long number){
//递归方法，计算fibonacci数列；

if (number==0 || number==1)
return number;
else 
return fibonacci(number-1)+fibonacci(number-2);
}}/* Fibonacci数列:
 *       0,1,1,2,3,5,8,......
 *       第一个和第二个数为0和1,后面每一个数都是前两个之和;
 *       相邻两个数之比趋向于黄金比例:1.618...;
 * 
 * 
 * 在要求高性能的场合，尽量不要用递归，用迭代；
 * 递归的优势在于可读性强，便于调试与理解；
 * 
 */

Answer 11

import java.util.*;
public class TestStack
{
  public static void main(String args[])
  {
      TestStack test = new TestStack();
      int lens = test.getLens(20);
   System.out.println("费波纳契数列20：" + lens);
   }   public int getLens(int len)
   {
    Stack<Integer> mystack = new Stack<Integer>();
     int lens = 0;
     mystack.push(new Integer(1));
     mystack.push(new Integer(1));
     int k = 1;
     while(k <= len)
     {
        for(int i=1;i<=2;i++)
        {
          Integer F1 = (Integer)mystack.pop();
          int f1 = F1.intValue();
          Integer F2 = (Integer)mystack.pop();
          int f2 = F2.intValue();
          Integer temp = new Integer(f1+f2);
          lens = temp.intValue();
          mystack.push(temp);
          mystack.push(F2);
          k++;
         }
      }
      return lens;
   }
}

Answer 12

得了吧，递归成这个样子，我写个Ruby的。希望能开导你们一下。def fab(n)
  return 1, 1 if n==2
  a, b = fab(n - 1)
  return a + b , a
end

Answer 13

Ruby 语言也不过尔尔，个人不太喜欢def，end的方式。

Answer 14

递归实现，如果n=0;返回0.n=1,返回1.佛则第三个数等于它的前一个数加上前两个数的和的思想。
if   (n==0) 
{ 
return   0; 
}else   if   (n==1) 
{ 
return   1; 
}else 
{ 
return   Feb(n-1)+Feb(n-2); 
} 
        } 
} 

Answer 15

public class fibonacci {                      //用递归的方法求fibonacci数列
static long fib (int index) {
if (index == 0 || index ==1)
return index;

else return fib (index - 1) +fib (index - 2); 
}

public static void main (String args[]) {
System.out.println(fib(5));
} 
}

Answer 16

讲递归的一般第一个都是拿这个做例子的,没有必要这个也copy吧?