斐波那契數列的數組法和遞歸法

數組法：

public static int Fibonacci(int n) {
    int[] f = new int[n+1];
    f[1] = f[2] = 1;
    for (int i = 3; i <= n; i++) {
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}
           

遞歸法：

public static int Fibonacci(int n) {
    if(n == 1 || n == 2){
        return 1;
    }
    return Fibonacci(n-1) + Fibonacci(n-2);
}
           

循環遞歸

//循環遞歸求x的n次方
public static double myPow(double x, int n) {
        long N = n;
        if (n < 0) {
            x = 1 / x;
            N = -n;
        }
        double ans = 1.0;
        for (int i = 0; i < N; i++) {
            ans *= x;
        }
        return ans;
    }
           

尾遞歸

如果一個函數中所有遞歸形式的調用都出現在函數的末尾，我們稱這個遞歸函數是尾遞歸的。當遞歸調用是整個函數體中最後執行的語句且它的傳回值不屬于表達式的一部分時，這個遞歸調用就是尾遞歸。尾遞歸函數的特點是在回歸過程中不用做任何操作，這個特性很重要，因為大多數現代的編譯器會利用這種特點自動生成優化的代碼。------百度百科

//反例：return是一個表達式
public static double myPow(double x, int n) {
	if(n == 0){
    	return 1;
    }
    if(n < 0){
        return (1/x) * myPow(x,n + 1);
    }else{
        return x * myPow(x,n - 1);
    }
}
           

而上面這個代碼如果這樣調用

myPow(0.00001, 2147483647)

會出現這種錯誤

Exception in thread "main" java.lang.StackOverflowError at Test.myPow(Test.java:332) at Test.myPow(Test.java:332) at Test.myPow(Test.java:332)

因為這樣會在每次return時生成一個新的棧，導緻了棧溢出。是以要避免這種形式的遞歸，可以使用上邊循環來代替遞歸。