算法：栈模拟递归斐波那契数列

快来打我* 2023-02-16 00:42 138阅读 0赞

# 题目来源 #

[LEETCODE][]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 解答 #

## java ##

### 栈 ###

public class Solution {
        
        public static int Fibonacci(int num){
        
            if (num <  2){
        
                return num;
            }
            return Fibonacci(num - 1) + Fibonacci(num - 2);
        }
    
        public static int FibonacciStack(int num){
        
            Stack<Integer> stack = new Stack<Integer>();
            stack.push(num);
            int res = 0;
            while (!stack.empty()){
        
                int data =  stack.pop();
                if (data < 2){
        
                    res = res + data;
                }else{
        
                    stack.push(data - 1);
                    stack.push(data - 2);
                }
            }
            return res;
        }
    
    
    
        public static void main(String[] args){
        
            System.out.println(FibonacciStack(15));
            System.out.println(Fibonacci(15));
        }
    }

### 循环 ###

public static int fib(int N) {
        
            if (N == 0 || N == 1){
        
                return N;
            }
    
    
            int res = 0;
            int min = 0;
            int max = 1;
            for (int i = 2; i <= N; i++){
        
                res = min + max;
                min = max;
                max = res;
            }
            return res;
        }

![在这里插入图片描述][20200422091935390.png]  
时间复杂度：O(N)O(N)。  
空间复杂度：O(1)O(1)，仅仅使用了 current，prev1，prev2。

### 递归 ###

public static int fib(int N) {
        
            if (N == 0 || N == 1){
        
                return N;
            }
    
            return fib(N-1) + fib(N - 2);
        }

![在这里插入图片描述][20200422092243281.png]

![在这里插入图片描述][20200529113944632.gif]

[递归树][Link 1]

时间复杂度：O(2^N）  
这是计算斐波那契数最慢的方法。因为它需要指数的时间。  
空间复杂度：O(N)O(N)，在堆栈中我们需要与 N 成正比的空间大小。该堆栈跟踪 fib(N) 的函数调用，随着堆栈的不断增长如果没有足够的内存则会导致 StackOverflowError。

## C++ ##

#include <stack>
    #include <cstdio>
    using namespace std;
    
    int fab(int num){
        
        if (num == 0 || num == 1){
        
            return num;
        }
    
        return fab(num - 1)  + fab(num - 2);
    }
    
    
    int fab_for(int num){
        
        if (num == 0 || num == 1){
        
            return num;
        }
    
        int ans = 0;
        int min = 0;
        int max = 1;
        for(int i = 2; i <= num; i++){
        
            ans = (min + max);
            min = max;
            max = ans;
        }
    
        return ans;
    }
    
    
    int fab_stack(int num){
        
        if (num == 0 || num == 1){
        
            return num;
        }
    
        std::stack<int> stack;
        stack.push(num);
        int ans = 0, data = 0;
        while (!stack.empty()){
        
            data = stack.top();
            stack.pop();
            if (data < 2){
        
                ans += data;
            }else{
        
                stack.push(data - 1);
                stack.push(data - 2);
            }
        }
    
        return ans;
    }
    
    
    int main(int argc,char **argv){
        
    
        printf("%d\n", fab_for(10));
        printf("%d\n", fab(10));
        printf("%d", fab_stack(10));
    
    
        return 0;
    }

[LEETCODE]: https://leetcode-cn.com/problems/fibonacci-number/solution/fei-bo-na-qi-shu-by-leetcode/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200422092308298.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200422091935390.png]: https://img-blog.csdnimg.cn/20200422091935390.png
[20200422092243281.png]: https://img-blog.csdnimg.cn/20200422092243281.png
[20200529113944632.gif]: https://img-blog.csdnimg.cn/20200529113944632.gif
[Link 1]: https://visualgo.net/zh/recursion