【Java】递归算法

递归的本质：

        方法调用自身。

案例1. 斐波那契数列

1 1 2 3 5 8 13 21 ..

f(n)=f(n-1)+f(n-2)

方法的返回值：

        只要涉及到加减乘除，就是int,其他的就是void。

案例2.  青蛙跳台 

        青蛙一次可以跳一级台阶，也可以跳两级台阶，那么青蛙跳到n级台阶有多少种方法？

思路：

        1. 如果只有一级台阶，青蛙有一种跳法。

        2. 如果有两级台阶，青蛙有两种跳法（一级一级跳或者一次跳两个）。

        3. 如果跳到n级，那么他可能是从n-1级跳上来的，也可能是n-2级跳上来的。

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

案例3. 计算数组前n项和

思路：

        前n项和  就是  前n-1项  和加 上  第n项数。

        f(n)=f(n-1)+arr[n-1]

public static int fun(int n,int[] arr){
    if(n==1){
        return arr[0];
    }
    return fun(n-1)+arr[n-1];
}

案例4. 二分查找

704. 二分查找 - 力扣（LeetCode）

        给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

 思路：

        目标值与中间值作对比，

        比中间值小往左走，

        比中间值大往右走。

        相等返回下标。

class Solution {
    public int search(int[] nums, int target) {
        return find(nums,target,0,nums.length-1);
    }
    public int find(int[] nums,int target,int left,int right){
        if(right<left){
            return -1;
        }
        int mid=(left+right)/2;
        if(nums[mid]==target){
            return mid;
        }
        if(target>nums[mid]){
            return find(nums,target,mid+1,right);
        }else{
            return find(nums,target,left,mid-1);
        }
        
    }
}