遞歸生成Fibonocci

Question

我正在嘗試創建一個方法，該方法將根據用戶輸入生成斐波那契數列，並通過遞歸計算第10個數字。 （現在學習遞歸，這是一個練習）。

這裏是我試圖代碼，我目前正在努力使工作：

//being run with fibonacci(10, 10); 
//Start being the number the sequence starts with 
public static int fibonacci(int start, int times) 
{ 
    if(times > 0) 
    { 
     int result = fibonacci(start - 1, times - 1) + fibonacci(start - 2, times - 1); 
     sequence += result; 
     return result; 
    } 
    System.out.println(sequence); 
    return start; 
} 

然而，這會返回大量的（我想約40000號需要大約10秒完成運行）。而且所有的數字看起來都是負面的，絕對不是我的目標。

現在，我們來認識問題：我認爲問題在於，每調用一次該方法時，該方法都會自動調用兩次，從而導致大量增加。然而，我想不出一個解決這個問題的辦法，因爲我每次都試圖通過遞歸來實現，而我別無選擇，只能再次調用它。

至於爲什麼它是負面的，我沒有線索。我以爲我正確地使用了斐波納契方程，但顯然我做了不正確的事情。

任何人都可以幫助我解決這個問題嗎？

（的確如此，我可以很容易地在這裏搜索一些代碼，因爲我確定它已經存在了，但我想實際瞭解它是如何完成的以及我爲未來的參考做了什麼錯誤。比從複製的代碼中獲得分數還要高）

Answer 1

我想你在這裏與斐波那契數列有些混淆。公式爲F（n）= F（n-1）+ F（n-2）。遞歸總是應該以Fibonacci爲F（0）= 0且F（1）= 1的基本情況結束。您的方法只需要一個變量n。

想想這樣說：

public static int fibonacci(int n) { 
    //Insert your base cases here to terminate early 
    //Then process the recursive formula 
    return fibonacci(n - 1) + fibonacci(n - 2); 
} 

Answer 2

我想我明白你正在嘗試做的。你需要10個斐波那契數字。也許這樣的事情會起作用：

public static int[] fibonacci(int start, int times) 
{ 
    return fibonacci(start, times, 0, 1, new int[times]); 
} 

private static int[] fibonacci(int start, int times, int a, int b, int[] answer) 
{  
    if(start > 0) 
     return fibonacci(start-1, times, b, a+b, answer); 

    if(times > 0) 
    { 
     answer[answer.length - times] = a; 
     return fibonacci(start, times-1, b, a+b, answer); 
    } 

    return answer; 
} 

public static void main(String[] args) { 
    int[] a = fibonacci(5, 10); 

    for(int i=0; i<a.length; i++) 
    { 
     System.out.println(a[i]); 
    } 
}