递归的剪枝逻辑_fib递归算法map

1.计算数n的斐波那契数列(应用到剪枝逻辑)

0，1，1，2，3，5，8.........

剪枝逻辑：应用到map集合，将每次求出的fib值都存储在map集合中，在递归需要使用到当前fib值时，先判断若map集合中有的话，直接在map集合中取，不必再计算一次当前fib，若没有则再计算fib同时存入map集合。

public class Num10_斐波那契数列 {
 
    //3.递归——应用到剪枝逻辑！！！(map集合存储每一次的fib值)
    private Map<Integer, Integer> filter = new HashMap<>();//filter：过滤
    public int Fibonacci(int n) {
        if(n==0||n==1){
            return n;
        }
        if(n==2){
            return 1;
        }
 
        int ppre=0;//n-2的斐波那契数
        if(filter.containsKey(n-2)){
            ppre=filter.get(n-2);
        }else {
            //没找到
            ppre=Fibonacci(n-2);
            filter.put(n-2,ppre);
        }
 
        int pre=0;//n-1的斐波那契数
        if(filter.containsKey(n-1)){
            pre=filter.get(n-1);
        }else {
            //没找到
            pre=Fibonacci(n-1);
            filter.put(n-1,pre);
        }
 
        return ppre+pre;
    }
 
//    //2.递归版本
//    public int Fibonacci(int n) {
//        if(n==0){
//            return 0;
//        }
//        if(n<=2){
//            return 1;
//        }
//       return Fibonacci(n-1)+Fibonacci(n-2);
//    }
 
//    //1.迭代版本
//    public int Fibonacci(int n) {
//        if(n==0){
//            return n;
//        }
//        int first=1;
//        int second=1;
//        int third=1;//n=1或2时直接返回1
//        while(n>2){
//            third=first+second;
//            first=second;
//            second=third;
//            n--;
//        }
//        return third;
//    }
}