斐波那契數(shù)列是一系列數(shù)字，其中每個數(shù)字(前兩個數(shù)字除外)都是前兩個數(shù)字的總和。斐波那契數(shù)列通常從 0、1 開始。我們可以在 Java 中使用迭代或遞歸創(chuàng)建斐波那契數(shù)列。在本文中，我們將介紹在 Java遞歸方法中的斐波那契數(shù)列。

介紹

在斐波那契數(shù)列中，每個數(shù)字(前兩個數(shù)字除外)都是前兩個數(shù)字的總和。斐波那契數(shù)列的數(shù)學(xué)公式是：

F(n) = F(n - 1) + F(n - 2)F ( n )=F ( n-1 )+F ( n-2 )其中，F(xiàn)(n)表示n^{第}n時間_斐波那契數(shù)。

在 Java 中，我們可以使用遞歸和記憶等不同的技術(shù)來創(chuàng)建斐波那契數(shù)列。讓我們看幾個例子來了解我們?nèi)绾蝿?chuàng)建斐波那契數(shù)列。

示例 1

在 Java 中使用遞歸的斐波那契數(shù)列 要在 Java 中使用遞歸計算斐波那契數(shù)列，我們需要創(chuàng)建一個函數(shù)以便執(zhí)行遞歸。這個函數(shù)接受一個整數(shù)輸入。該函數(shù)檢查輸入數(shù)字是0、1還是2，如果輸入是三個數(shù)字中的任何一個，它分別返回0、1或1 。如果輸入大于2，該函數(shù)會遞歸調(diào)用自身以獲取先前的值，直到輸入變量的值變得小于或等于2。因此，如果函數(shù)接收一個整數(shù)n作為輸入，它將返回n^th^斐波那契數(shù)。要打印斐波那契數(shù)列，我們將調(diào)用此函數(shù)來計算每個斐波那契數(shù)。

public class FibonacciCalc {
  public static int fibRecursion(int count) {
    if (count == 0) {
      return 0;
    }
    if (count == 1 || count == 2) {
      return 1;
    }
    return fibRecursion(count - 1) + fibRecursion(count - 2);
  }
  public static void main(String args[]) {
    int fib_len = 9;
    System.out.print("Fibonacci Series of " + fib_len + " numbers is: \n");
    for (int i = 0; i < fib_len; i++) {
      System.out.print(fibRecursion(i) + " ");
    }
  }
}

程序的輸出：

Fibonacci Series of 9 numbers is:
0 1 1 2 3 5 8 13 21

在上面的示例中，我們定義了一個遞歸函數(shù)fibRecursion來獲取第 n 個斐波那契數(shù)并重復(fù)調(diào)用它(對于i=0 到 i=8)，以創(chuàng)建一個長度為 9 的斐波那契數(shù)列。

時空復(fù)雜度

求解斐波那契數(shù)列的遞歸方法的時間復(fù)雜度為O(2^n)O ( 2n)即指數(shù)時間。如果我們考慮遞歸堆棧，遞歸方法的空間復(fù)雜度為O(n) 。

指數(shù)時間復(fù)雜度是極其低效的。使用遞歸方法計算長度很大的斐波那契數(shù)列需要很長時間。為了解決這個問題，我們可以使用記憶技術(shù)來創(chuàng)建斐波那契數(shù)列。這種技術(shù)比遞歸方法快得多。

示例 2

Java 中的斐波那契數(shù)與記憶記憶 記憶是一種用于提高遞歸程序性能的編程技術(shù)。在這種技術(shù)中，先前計算的結(jié)果被存儲(緩存)并重復(fù)使用。在之前的方法中，我們分別計算每個斐波那契數(shù)。但是，在這種方法中，我們將使用之前的結(jié)果來計算當(dāng)前的斐波那契數(shù)。因此，如果我們計算了一個數(shù)字的斐波那契，我們可以重復(fù)使用它而無需再次進行計算。

在之前的方法中，我們分別計算每個斐波那契數(shù)，但在這種方法中，我們將使用之前的結(jié)果來計算當(dāng)前數(shù)字。

記憶化可以使用HashMaps來完成。

import java.util.HashMap;
import java.util.Map;
public class FibonacciCalc {
  static private Map < Integer, Integer > memoizeTable = new HashMap < > ();
  // Fibonacci with Memoization
  static public int fibMemoize(int n) {
    if (n == 0) {
      return 0;
    }
    if (n == 1) {
      return 1;
    }
    if (memoizeTable.containsKey(n)) {
      // getting value from the stored result(s)
      return memoizeTable.get(n);
    }
    int result = fibMemoize(n - 1) + fibMemoize(n - 2);
    // storing the result in cache
    memoizeTable.put(n, result);
    return result;
  }
  public static void main(String[] args) {
    //FibonacciCalc fibo = new FibonacciCalc();
    System.out.println("Fibonacci value for n = 6 --> " +
      fibMemoize(6));
  }
}

程序的輸出：

Fibonacci value for n = 6 --> 8

在上面的例子中，我們創(chuàng)建了一個函數(shù)fibMemoize，它使用 memoization 來計算斐波那契數(shù)。在這個函數(shù)中，我們首先檢查變量n 是 0 還是 1。如果n是0，我們返回 0 ，如果n是 1 ，我們返回1。如果n^{第}n時間_斐波那契數(shù)存儲在 hashmap 中，我們直接使用它的值來獲得所需的斐波那契數(shù)。如果沒有存儲n，我們通過調(diào)用前兩個斐波那契值的函數(shù)來計算斐波那契值，然后將這個值存儲到hashmap中，最后返回它來得到我們的答案。

時空復(fù)雜度

計算斐波那契數(shù)列的記憶方法的時間復(fù)雜度為O(n)。這種方法的空間復(fù)雜度也是O(n)。

以上就是關(guān)于“遞歸實現(xiàn)斐波那契數(shù)列”的介紹，大家如果想了解更多相關(guān)知識，可以關(guān)注一下動力節(jié)點的Java教程，里面有更豐富的知識等著大家去學(xué)習(xí)，相信對大家一定會有所幫助的。