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

介紹

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

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

在 Java 中，我們可以使用遞歸和記憶等不同的技術來創建斐波那契數列。讓我們看幾個例子來了解我們如何創建斐波那契數列。

示例 1

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

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

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

時空復雜度

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

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

示例 2

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

在之前的方法中，我們分別計算每個斐波那契數，但在這種方法中，我們將使用之前的結果來計算當前數字。

記憶化可以使用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

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

時空復雜度

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

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