C语言训练-斐波纳契数列-题解(递归解法)（Java代码）

解题思路: 因为f(n)=f(n-1)+f(n-2)，所以这个是很明显的双分支递归......

注意事项: 注意保存数据要long

参考代码:

 //递归
 public static int recuision(int num) {
        if (num == 1 || num == 2) {
            return 1;
        }
        return recuision(num-1)+recuision(num-2);//开始递归
    }
    
    public static int recuisionNumber(int origin,int end) {//参数origin表示起点，end表示终点(慢慢理解)
        if (origin==end+1) {//递归结束
            return 1;
        }
        int record = recuision(origin);
        //打印
        if (origin<end) {
            System.out.print(record+" ");
        }else {
            System.out.print(record);
        }
        return recuisionNumber(++origin,end);//开始递归
    }
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        int record = sc.nextInt();
        if (record<41) {
            recuisionNumber(1,record);
        }
        
    }

    //这是上面方法的优化，时间减少了很多，主要就是剪掉重复的分支。啊！不想讲解，慢慢看。不懂可以评论提问！！！！！！！！！
    
    
    
    public static int recuision(int arr[],int num) {
        if (num == 1 || num == 2) {
            return 1;
        }
        if (arr[num]!=0) {
            return arr[num];
        }
        return recuision(arr,num-1)+recuision(arr,num-2);//开始递归
    }
    
    public static int recuisionNumber(int arr[],int origin,int end) {//参数origin表示起点，end表示终点(慢慢理解)
        if (origin==end+1) {//递归结束
            return 1;
        }
        int record = recuision(arr,origin);
        arr[origin] = record;
        //打印
        if (origin<end) {
            System.out.print(record+" ");
        }else {
            System.out.print(record);
        }
        return recuisionNumber(arr,++origin,end);//开始递归
    }
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        int record = sc.nextInt();
        int arr[] = new int[record+1];//记录
        if (record<41) {
            recuisionNumber(arr,1,record);
        }
        
    }