public class FibonacciRecursive {  
    public static int fibonacci(int n) {  
        if (n <= 1) {  
            return n;  
        } else {  
            return fibonacci(n - 1) + fibonacci(n - 2);  
        }  
    }  
    public static void main(String[] args) {  
        int n = 40; // 嘗試較大的數(shù)，比如40，可能會(huì)導(dǎo)致堆棧溢出  
        System.out.println("Fibonacci(" + n + ") = " + fibonacci(n));  
    }  
}

public class FibonacciIterative {  
    public static int fibonacci(int n) {  
        if (n <= 1) {  
            return n;  
        }  
        int a = 0, b = 1;  
        for (int i = 2; i <= n; i++) {  
            int temp = a + b;  
            a = b;  
            b = temp;  
        }  
        return b;  
    }  
    public static void main(String[] args) {  
        int n = 90; // 即使n很大，也不會(huì)導(dǎo)致堆棧溢出  
        System.out.println("Fibonacci(" + n + ") = " + fibonacci(n));  
    }  
}

public class FibonacciTailRecursive {  
    public static int fibonacci(int n, int a, int b) {  
        if (n == 0) return a;  
        if (n == 1) return b;  
        return fibonacci(n - 1, b, a + b); // 尾遞歸調(diào)用  
    }  
    public static void main(String[] args) {  
        int n = 40; // 在標(biāo)準(zhǔn)Java中，這仍然可能導(dǎo)致堆棧溢出  
        System.out.println("Fibonacci(" + n + ") = " + fibonacci(n, 0, 1));  
    }  
}

import java.util.Stack;  
public class FibonacciWithStack {  
    static class Pair {  
        int n;  
        int value; // 用于存儲(chǔ)已計(jì)算的值，以避免重復(fù)計(jì)算  
        Pair(int n, int value) {  
            this.n = n;  
            this.value = value;  
        }  
    }  
    public static int fibonacci(int n) {  
        Stack<Pair> stack = new Stack<>();  
        stack.push(new Pair(n, -1)); // -1 表示值尚未計(jì)算  
        while (!stack.isEmpty()) {  
            Pair pair = stack.pop();  
            int currentN = pair.n;  
            int currentValue = pair.value;  
            if (currentValue != -1) {  
                // 如果值已經(jīng)計(jì)算過(guò)，則直接使用  
                continue;  
            }  
            if (currentN <= 1) {  
                // 基本情況  
                currentValue = currentN;  
            } else {  
                // 遞歸情況，將更小的n值壓入棧中  
                stack.push(new Pair(currentN - 1, -1));  
                stack.push(new Pair(currentN - 2, -1));  
            }  
            // 存儲(chǔ)計(jì)算過(guò)的值，以便后續(xù)使用  
            stack.push(new Pair(currentN, currentValue));  
        }  
        // 棧底元素存儲(chǔ)了最終結(jié)果  
        return stack.peek().value;  
    }  
    public static void main(String[] args) {  
        int n = 40;  
        System.out.println("Fibonacci(" + n + ") = " + fibonacci(n));  
    }  
}