Java递归斐波那契数列

Question

请解释这个简单的代码：

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 处的值。请详细解释一下！

Answer 1

Michael Goodrich 等人在《Java 数据结构和算法》中提供了一种非常聪明的算法，通过返回 [fib(n), fib(n-1)] 数组，在线性时间内递归求解斐波那契。

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]。

Answer 2

这是 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);
}

用于上述实现的比奈斐波那契数公式。
对于较大的输入，long 可以替换为 BigDecimal。

Answer 3

为什么这个答案不同

每个其他答案要么：

• 打印而不是返回
• 每次迭代进行 2 次递归
• 调用 通过使用循环忽略问题

（除此之外：这些实际上都不是有效的；使用 比奈公式直接计算第 n^th 项）

尾递归 Fib

这是一种递归方法，通过传递前一个答案和之前的答案来避免双重递归调用。

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);
}

Answer 4

斐波那契数列是一种将一个数字的结果与从 1 开始的前一个结果相加的数列。

      so.. 1 + 1 = 2
           2 + 3 = 5
           3 + 5 = 8
           5 + 8 = 13
           8 + 13 = 21

一旦我们了解了斐波那契是什么，我们就可以开始分解代码。

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（见上表）。

fibonacci(n - 1) 不断被调用，直到达到基本情况，然后调用 fibonacci(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).

它们不断冒泡（向后解析），直到正确的总和返回到堆栈中的第一个调用，这就是您得到答案的方式。

话虽如此，该算法的效率非常低，因为它为代码分成的每个分支计算相同的结果。一种更好的方法是“自下而上”的方法，其中不需要记忆（缓存）或递归（深度调用堆栈）。

就像这样...

        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;
        }

Answer 5

这里提供的大多数解决方案都以 O(2^n) 复杂度运行。重新计算递归树中的相同节点效率低下并且浪费 CPU 周期。

我们可以使用记忆化使斐波那契函数在 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];
}

Answer 6

它是显示或获取输出的基本序列
1 1 2 3 5 8
下一个显示的是前一个数字和当前数字的顺序。

尝试观看下面的链接 Java 递归斐波那契数列教程

public static long getFibonacci(int number){
if(number<=1) return number;
else return getFibonacci(number-1) + getFibonacci(number-2);
}

点击这里 观看 Java 递归斐波那契数列教程 进行勺子喂养

Answer 7

我认为这是一个简单的方法：

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);
        }
    }
}

Answer 8

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);
        }
    }

}

Answer 9

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]);
   }
 }
}

Answer 10

通过使用理论上可能允许的内部 ConcurrentHashMap
这种递归实现可以在多线程中正确运行
环境中，我实现了一个使用 BigInteger 的 fib 函数
和递归。计算前 100 个 fib 数字大约需要 53 毫秒。

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

Answer 11

这是一个单行 febonacci 递归：

public long fib( long n ) {
        return n <= 0 ? 0 : n == 1 ? 1 : fib( n - 1 ) + fib( n - 2 );
}

Answer 12

我找不到带有三元运算符的简单单衬。所以这是一个：

public int fibonacci(int n) {
    return (n < 2) ? n : fibonacci(n - 2) + fibonacci(n - 1);
}

Answer 13

作为补充，如果您希望能够计算更大的数字，您应该使用 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("");
        }
    }
}

Answer 14

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 循环和其他循环

Answer 15

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;
    }
}

Answer 16

使用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;
}

这种方案的优点是很容易阅读代码并理解，希望有帮助

Answer 17

斐波那契数列是对一个数字的结果求和的数列
那么我们已经添加到之前的结果中，我们应该从 1 开始。
我试图找到基于算法的解决方案，所以我构建了递归代码，注意到我保留了以前的数字并且更改了位置。我正在搜索从 1 到 15 的斐波那契数列。

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);
}

Answer 18

试试这个

private static int fibonacci(int n){
    if(n <= 1)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Answer 19

 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;
}

Answer 20

简单斐波那契

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;
    }
  }
}

Answer 21

在斐波那契数列中，每一项都是前两项之和。所以，你写了一个递归算法。

所以，

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 和 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....我们可以看到对于第5个元素斐波那契序列返回5。

请参阅此处的递归教程。

Answer 22

您的代码有 2 个问题：

1. 结果存储在 int 中，它只能处理前 48 个斐波那契数，此后整数填充减位，结果是错误的。但你永远无法运行斐波那契(50)。
2. 代码 fibonacci(n - 1) + fibonacci(n - 2) 效率非常低。问题是它调用斐波那契的次数不是 50 次，而是更多。
   • 首先调用 fibonacci(49)+fibonacci(48)，
   • 下一个斐波那契(48)+斐波那契(47)和斐波那契(47)+斐波那契(46)...
   • 每次斐波那契（n）变得更糟，因此复杂性呈指数级增长：
     

非递归代码的方法：

 double fibonacci(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;
}

Answer 23

在伪代码中，当 n = 5 时，会发生以下情况：

斐波那契(4) + 斐波那契(3)

这可以分解为：

(斐波那契(3) + 斐波那契(2)) + (斐波那契(2) + 斐波那契(1))

这可以分解为：

(((斐波那契(2) + 斐波那契(1)) + ((斐波那契(1) + 斐波那契(0))) + (((斐波那契(1) + 斐波那契(0)) + 1))

这可以分解为：

((((斐波那契(1)) + 斐波那契(0)) + 1) + ((1 + 0)) + ((1 + 0) + 1))

这可以分解为：

((((1 + 0) + 1) + ((1 + 0)) + ((1 + 0) + 1))

这导致：​​ 5

给定斐波那契数列为 1 1 2 3 5 8 ...，第5个元素是5。您可以使用相同的方法来计算其他迭代。

Answer 24

您还可以简化您的功能，如下所示：

public int fibonacci(int n)  {
    if (n < 2) return n;

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

Answer 25

递归有时可能很难掌握。只需在一张纸上评估它的一小部分：

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实际上如何评估它，但结果将是相同的。

Answer 26

                                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 章

Answer 27

大多数答案都很好，并解释了斐波那契递归的工作原理。

以下是对包括递归在内的三种技术的分析：

1. For 循环
2. 递归
3. 记忆化

这是我测试这三种技术的代码：

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

因此我们可以看到记忆化是最好的时间明智并且 for 循环非常匹配。

但递归花费的时间最长，可能是您在现实生活中应该避免的。另外，如果您使用递归，请确保优化解决方案。

Answer 28

这是我发现的最好的视频，它充分解释了 Java 中的递归和斐波那契数列。

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;
    }

Answer 29

在 fibonacci 序列中，前两项是 0 和 1，其他项是前两项。即：
0 1 1 2 3 5 8...

所以第 5 项是第 4 项和第 3 项之和。

Answer 30

对于斐波那契递归解决方案，重要的是保存较小斐波那契数的输出，同时检索较大数的值。这称为“记忆”。

下面的代码使用记忆较小的斐波那契值，同时检索较大的斐波那契数。该代码非常高效，并且不会对同一功能发出多个请求。

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;
    }
  }
}