递归的本质：
方法调用自身。
案例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);}}
}
