🔥博客主页： 小扳_-CSDN博客
❤感谢大家点赞👍收藏⭐评论✍
文章目录
1.0 递归的说明
2.0 用递归来实现相关问题
2.1 递归 - 阶乘
2.2 递归 - 反向打印字符串
2.3 递归 - 二分查找
2.4 递归 - 冒泡排序
2.5 递归 - 冒泡排序2.0
2.6 递归 - 插入排序
2.7 递归 - 斐波那契
2.8 递归 - 兔子问题
2.9 递归 - 青蛙爬楼梯
1.0 递归的说明
递归就是在一个函数中调用自身。这样做可以让我们解决一些问题，比如计算斐波那契数列、阶乘等。
递归函数一般包括两部分：基本情况和递归情况。基本情况是指当问题变得很小，可以直接得到答案时，递归就可以停止了。递归情况是指在解决问题的过程中，需要不断地调用自身来解决更小规模的问题。
对于递归这个算法，简单的来说，方法自身调用自身的时候，需要有终止的条件，在运行过程中不断的趋向终止条件。还有递归总的来说有两个动作：第一个动作是递出，方法不断的在栈区中创建出来，直到达到了条件就会停止。第二个动作，达到条件停止了，就会回归，指方法在栈区中依次执行完后就销毁。
2.0 用递归来实现相关问题
以下的问题都较为简单，采取直接用代码来演示。
2.1 递归 - 阶乘
代码如下：
//阶乘 public static void main(String[] args) { System.out.println(fun(5)); } public static int fun(int n) { if (n == 1) { return 1; } return n * fun(n-1); } }运行结果为：
2.2 递归 - 反向打印字符串
代码如下：
//反向打印字符串 public static void main(String[] args) { String str = "lisi"; fun2(str,0); } public static void fun2 (String s, int n) { if (n == s.length()) { return; } fun2(s,n + 1); System.out.println(s.charAt(n)); }运行结果：
2.3 递归 - 二分查找
代码如下：
//二分查找 public static void main(String[] args) { int[] arr = {1,3,5,7,9,10,13}; System.out.println(fun3(arr, 0, arr.length - 1, 4)); } public static int fun3 (int[] arr, int left, int right, int target) { int mid = (left + right) >>> 1; if (left > right) { return -1; } if(arr[mid] < target) { return fun3(arr, mid + 1,right,target); } else if (target < arr[mid]) { return fun3(arr,left,right - 1,target); }else { return mid; } }运行结果如下：
没有找到就返回 - 1
2.4 递归 - 冒泡排序
代码如下：
//冒泡排序 public static void main(String[] args) { int[] arr = {1,5,2,4,9,1,3}; fun4(arr, arr.length - 1); System.out.println(Arrays.toString(arr)); } public static void fun4 (int[] arr, int n) { if (n == 0) { return; } for (int i = 0; i < n; i++) { if (arr[i] > arr[i + 1]) { int temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; } } fun4(arr,n-1); }运行结果如下：
2.5 递归 - 冒泡排序2.0
对冒泡排序进行升级，假如 int[] arr = {2,1,1,3,4,5,9}，这种只需要遍历一遍即可，但是对与已经用递归实现的冒泡不止遍历一次。因此，需要得到升级版冒泡排序。
思路为：对于后续的元素已经是排好序了，就不用再遍历了。每一次交换完元素之后记下来 i 索引，i 之后的元素已经是排好序的，i 之前的元素还需要继续遍历，看是否还需要交换。
代码如下：
//冒泡排序升级版 public static void main(String[] args) { int[] arr = {1,3,2,4,9,10,13}; fun4(arr, arr.length - 1); System.out.println(Arrays.toString(arr)); } public static void fun4 (int[] arr, int n) { if (n == 0) { return; } int j = 0; for (int i = 0; i < n; i++) { if (arr[i] > arr[i + 1]) { int temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; j = i; } } fun4(arr,j); }如果还不是很清晰的话，可以一步步来调试一下，来对比两种冒泡的执行过程。
2.6 递归 - 插入排序
思路：假设第一个元素已经排序好了的，在已经排好的元素的后一个元素记录为 low，这个 low 索引对应的元素需要用临时变量来接受，只要找到比这个索引对应的元素小的值，就可以插入到比它小的值的后一个索引位置了，当然，每一次对比之后，都需要往后移一个位置，以便直接插入。当 low 一直每一个加 1 ，当 low 等于数组的长度时，就该停止了继续递归下去了。
代码如下：
public class Recursion { // 插入排序 public static void main(String[] args) { int[] arr = {1,3,2,4,9,10,13}; fun5(arr,1); System.out.println(Arrays.toString(arr)); } public static void fun5 (int[] arr,int low) { if (low == arr.length) { return; } int temp = arr[low]; int i = low - 1; while (arr[i] > temp) { arr[i + 1] = arr[i]; i--; } arr[i + 1] = temp; fun5(arr,low + 1); }运行结果如下：
2.7 递归 - 斐波那契
代码如下：
//斐波那契 public static void main(String[] args) { System.out.print(fun6(1) +" "); System.out.print(fun6(2) +" "); System.out.print(fun6(3) +" "); System.out.print(fun6(4) +" "); System.out.print(fun6(5) +" "); System.out.print(fun6(6) +" "); } public static int fun6 (int n) { if (n == 0) { return 0; } if (n == 1 || n == 2) { return 1; } return fun6(n-1) + fun6(n - 2); }运行结果如下：
2.8 递归 - 兔子问题
一个斐波那契的变体问题。
思路：观察第六个月的兔子个数，是否等于第四个月的兔子的总数加上第五个月的兔子总数；类推，第五个月的兔子个数，是否等于第四个月的兔子的总数加上第三个月的兔子总数；以此类推，是符合斐波那契逻辑的。
代码如下：
//兔子问题 public static void main(String[] args) { System.out.print(fun7(1) + " "); System.out.print(fun7(2) + " "); System.out.print(fun7(3) + " "); System.out.print(fun7(4) + " "); System.out.print(fun7(5) + " "); } public static int fun7 (int n) { if (n == 1) { return 1; } if (n == 0) { return 0; } return fun7(n -1) + fun7(n - 2); }运行结果如下：
2.9 递归 - 青蛙爬楼梯
一个斐波那契的变体问题。
题目如下：
列举一下：
实现思路： 一个阶梯一种跳法，两个阶梯两种跳法。重点，如果有四个阶梯，从后往前分析，分两种情况；第一种，从第二个台阶直接一下子跳两阶上来。第二种，从第三个台阶跳一阶上来。那么从考虑第一种情况，前面两阶是不是就是只有两种方法。考虑第二种情况，前面的三个台阶是不是就是前面已经算出来的方式跳法个数了。因此，这就是一个斐波那契的变体问题。
代码如下：
//青蛙问题 public static void main(String[] args) { System.out.print(fun8(1) + " "); System.out.print(fun8(2) + " "); System.out.print(fun8(3) + " "); System.out.print(fun8(4) + " "); System.out.print(fun8(5) + " "); System.out.print(fun8(6) + " "); } public static int fun8 (int n) { if (n == 1) { return 1; } if (n == 2) { return 2; } return fun8(n-1) +fun8(n-2); }运行结果如下：
