一、定义
递归是一种解决计算问题的方法，解决方案取决于同一类问题的更小子集。
特点：
- 自己调用自己，如果说每个函数对应着一种解决方案，自己调用自己意味着解决方案是一样的（有规律的）
- 每次调用，函数处理的数据会较上次缩减(子集)，而且最后会缩减至无需继续递
- 内层函数调用(子集处理) 完成，外层函数才能算调用完成
单链表递归遍历：
private static void loop(SingleNode node) {
if (node == null) {
return;
}
System.out.println("before:" + node.value);
loop(node.next);
System.out.println("after:" + node.value);
}
public static void main(String[] args) {
SingleLinkedList.addLast(1);
SingleLinkedList.addLast(2);
SingleLinkedList.addLast(3);
loop(findNode(0));
}
before:1
before:2
before:3
after:3
after:2
after:1
以上递归代码写成伪代码如下：
private static void loop(node == 1) {
System.out.println("before:" + node.value); // 1
private static void loop(node == 2) {
System.out.println("before:" + node.value); // 2
private static void loop(node == 3) {
System.out.println("before:" + node.value); // 3
private static void loop(SingleNode node) {
if (node == null) {
return;
}
}
System.out.println("after:" + node.value); // 3
}
System.out.println("after:" + node.value); // 2
}
System.out.println("after:" + node.value); // 1
}
二、解题思路
- 确定能否使用递归求解
- 推导出递推关系，即父问题与子问题的关系，以及递归的结束条件
如遍历链表的递推关系：
- 深入到最里层叫递
- 从最里层出来叫归
- 在递的过程中，外层函数内的局部变量（以及方法参数）并未消失，归的时候还可以用到。
三、求阶乘
用递归方法求阶乘，
- 阶乘的定义：n!=1·2·3···（n-2）·（n-1）·n，其中n为自然数，0!=1。
- 递推关系：
public class Factorial {
public static int f(int n) {
if (n == 1) {
return 1;
}
return n * f(n - 1);
}
public static void main(String[] args) {
int factorial = f(3);
System.out.println(factorial);
}
}
伪代码如下：
f(int n=3){
return 3*f(int n=2){
return 2*f(int n=1){
if(n == 1){
return 1;
}
}
}
四、反向打印字符串
用递归反向打印字符串，n为字符在整个字符串 str 中的索引位置
- 递:n从0开始，每次n+1，一直递到n==str.length()-1
- 归:从n== str.length()开始归，从归打印，自然是逆序的
递推关系
public static void reversePrint(String str,int index) {
if (index == str.length()) {
return;
}
reversePrint(str, index + 1);
System.out.println(str.charAt(index));
}
public static void main(String[] args) {
reversePrint("abcd",0);
}
伪代码：
reversePrint(String str,0) {
reversePrint(str, 1) {
reversePrint(str, 2) {
reversePrint(str, 3) {
reversePrint(str, 4) {
if (3 == str.length()) {
return;
}
}
System.out.println(str.charAt(3));
}
System.out.println(str.charAt(2));
}
System.out.println(str.charAt(1));
}
System.out.println(str.charAt(0));
}
五、使用递归实现冒泡排序
1.冒泡排序基本思想：
通过对待排序序列从前向后（从下标较小的元素开始）,依次对相邻两个元素的值进行两两比较，若发现逆序则交换，使值较大的元素逐渐从前移向后移，就如果水底下的气泡一样逐渐向上冒。
2.步骤
待排序数组：[8,5,1,2,0]
第一轮排序（索引0~4中）：[8,5,1,2,0]：
- 索引0和索引1比较，前者大，交换：[5,8,1,2,0]
- 索引1和索引2比较，前者大，交换：[5,1,8,2,0]
- 索引2和索引3比较，前者大，交换：[5,1,2,8,0]
- 索引3和索引4比较，前者大，交换：[5,1,2,0,8]
这一轮结束 ，最大的元素已经排在了最后
第二轮排序（索引0~3中）：[5,1,2,0,8]
- 索引0和索引1比较，前者大，交换：[1,5,2,0,8]
- 索引1和索引2比较，前者大，交换：[1,2,5,0,8]
- 索引2和索引3比较，前者大，交换：[1,2,0,5,8]
这一轮结束 ，倒数第二大的的元素已经排在倒数第二个位置
第三轮排序（索引0~2中）：[1,2,0,5,8]
- 索引0和索引1比较，后者大，不交换：[1,2,0,5,8]
- 索引1和索引2比较，前者大，交换：[1,0,2,5,8]
这一轮结束 ，倒数第三大的的元素已经排在倒数第三个位置
第四轮排序（索引0~1中）：[1,0,2,5,8]
- 索引0和索引1比较，前者大，交换：[0,1,2,5,8]
这一轮结束 ，倒数第四大的的元素已经排在倒数第四个位置
一共5个元素，排序结束。
第一层for循环控制总轮次，第二层for循环控制交换的次数，因为每一轮都有一个大的排好了序在后面，所以内存循环的次数是随着每一轮排好的元素逐渐递减的。
迭代实现：
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - 1-i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
public static void swap(int[] arr,int a ,int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
递归实现：
/**
* 递归冒泡
* @param arr
* @param right
*/
public static void bubbleRecursion(int[] arr,int right) {
if (right == 0) {
return;
}
for (int i = 0; i < right; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}
bubbleRecursion(arr, right - 1);
}
递归优化：在冒泡的过程中，如果两个相邻元素发生了交换，意味着有无序的情况，如果没发生交换，意味着有序；所以最后一次发生交换的时候，意味着后续的都是有序的了。所以最后一次交换，i索引的位置就是有序和无序的分界点，i的右侧一定都是有序的了，i的左侧可能还是无序的。使用一个标志位记录下这个位置，下一趟递归，直接从这个标志位开始，就可以减少无效的递归次数了（上面的写法是每次都减少1），现在缩减成直接从未排序的标志点开始递归（缩减的可能比1要多，所以可以减少递归的次数）。
/**
* 递归冒泡优化
* @param arr
* @param right
*/
public static void bubbleRecursion1(int[] arr,int right) {
if (right == 0) {
return;
}
int flag = 0;
for (int i = 0; i < right; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
flag = i;
}
}
bubbleRecursion1(arr, flag);
}
六、使用递归实现插入排序
1.插入排序基本思想
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
2.步骤
将第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面）
待排序数组：[8,5,1,2,0]
- 取出无序部分[1~4]的首个元素5，在有序部分从后向前比较，插入到合适的位置：[5,8,1,2,0]
- 取出无序部分[2~4]的首个元素1，在有序部分从后向前比较，插入到合适的位置：[1,5,8,2,0]
- 取出无序部分[3~4]的首个元素2，在有序部分从后向前比较，插入到合适的位置：[1,2,5,8,0]
- 取出无序部分[3~4]的首个元素8，在有序部分从后向前比较，插入到合适的位置：[1,2,5,8,0]
- 取出无序部分[4]的首个元素0，在有序部分从后向前比较，插入到合适的位置：[0,1,2,5,8]
迭代实现：
public static void insert(int[] arr) {
for (int i = 1; i < arr.length; i++) {
//要插入的元素
int current = arr[i];
//要比较的索引，有序部分从后向前比较
int j = i - 1;
//寻找比当前元素小的元素的位置
while (j >= 0 && arr[j] > current) {
//依次空出一个位置
arr[j + 1] = arr[j];
j--;
}
//要插入的位置
arr[j + 1] = current;
}
}
递归实现：
/**
* 递归插入排序
* @param arr
* @param insertEleIndex 要开始准备插入的元素的索引，未排序区域的左边界
*/
public static void insertRecursion(int[] arr,int insertEleIndex) {
if (insertEleIndex == arr.length) {
return;
}
//要插入的元素
int current = arr[insertEleIndex];
//要比较的索引
int j = insertEleIndex - 1;
//寻找比当前元素小的元素的位置
while (j >= 0 && arr[j] > current) {
//依次空出一个位置
arr[j + 1] = arr[j];
j--;
}
//要插入的位置
arr[j + 1] = current;
insertRecursion(arr, insertEleIndex + 1);
}
七、Leetcode509.斐波那契数
- 每个递归函数只包含一个自身调用，称为单路递归 single recursion
- 每个递归包含多个自身调用，称为多路递归 multi recursion
递推关系：
数列的前几项：
| F0 | F1 | F2 | F3 | F4 | F5 | F6 | F7 | F8 | F9 | F10 | F11 | F12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 |
迭代方式：
public static int fib(int n) {
if (n <= 1) {
return n;
}
int[] arr = new int[n + 1];
arr[0] = 0;
arr[1] = 1;
for (int i = 2; i <= n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n];
}
递归方式：
public static int f(int n) {
if (n <= 1) {
return n;
}
return f(n - 1) + f(n - 2);
}
递归过程：
递归过程.gif
- 绿色代表正在执行（对应递），灰色代表执行结束（对应归）
- 递不到头，不能归，对应深度优先搜索
八、兔子问题
古典问题：3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，求第n个月的兔子数
设第 n 个月兔子数为
-
= 上个月兔子数 + 新生的小兔子数
- 而【新生的小兔子数】实际就是【上个月成熟的兔子数】
- 因为需要一个月兔子就成熟，所以【上个月成熟的兔子数】也就是【上上个月的兔子数】
- 上个月兔子数，即
- 上上个月的兔子数，即
因此本质还是斐波那契数列
代码实现：
public static int sumRabbit(int month) {
if (month <= 2) {
return 1;
}
return sumRabbit(month - 1) + sumRabbit(month - 1);
}
九、Leetcode70.爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
分析
| n | 跳法 | 规律 |
|---|---|---|
| 1 | (1) | 暂时看不出 |
| 2 | (1,1) (2) | 暂时看不出 |
| 3 | (1,1,1) (1,2) (2,1) | 暂时看不出 |
| 4 | (1,1,1,1) (1,2,1) (2,1,1) (1,1,2) (2,2) |
最后一跳，跳一个台阶的，基于f(3) 最后一跳，跳两个台阶的，基于f(2) |
| 5 | ... | ... |
因此本质上还是斐波那契数列，只是从其第二项开始
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
return climbStairs(n - 2) + climbStairs(n - 1);
}
此解法在力扣上超出时间限制
使用迭代：
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
int[] arr = new int[n + 1];
arr[0] = 0;
arr[1] = 1;
arr[2] = 2;
for (int i = 3; i <= n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n];
}
十、使用记忆法（备忘录）优化递归
在之前的递归过程中，存在很多重复的计算，为了减少这些重复的计算，可以把已经计算好的结果暂存起来，用到的时候直接取。
public static int fibonacciImprove(int n) {
int[] cache = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
cache[i] = -1;
}
cache[0] = 0;
cache[1] = 1;
return fibonacciRecursion(n, cache);
}
public static int fibonacciRecursion(int n, int[] cache) {
//用数组缓存已经计算好的结果
if (cache[n] != -1) {
return cache[n];
}
int lastOne = fibonacciRecursion(n - 1, cache);
int lastTwo = fibonacciRecursion(n - 2, cache);
cache[n] = lastOne + lastTwo;
return cache[n];
}
十一、爆栈问题
1.问题现象
public static void main(String[] args) {
long sum = sum(15000);
System.out.println(sum);
}
public static long sum(long n) {
if (n == 1) {
return n;
}
return sum(n - 1) + n;
}
Exception in thread "main" java.lang.StackOverflowError
at com.hcx.algorithm.recursion.RecursionSum.sum(RecursionSum.java:24)
at com.hcx.algorithm.recursion.RecursionSum.sum(RecursionSum.java:24)
at com.hcx.algorithm.recursion.RecursionSum.sum(RecursionSum.java:24)
at com.hcx.algorithm.recursion.RecursionSum.sum(RecursionSum.java:24)
at com.hcx.algorithm.recursion.RecursionSum.sum(RecursionSum.java:24)
at com.hcx.algorithm.recursion.RecursionSum.sum(RecursionSum.java:24)
at com.hcx.algorithm.recursion.RecursionSum.sum(RecursionSum.java:24)
at com.hcx.algorithm.recursion.RecursionSum.sum(RecursionSum.java:24)
递是压栈，归是弹栈：
在递的过程中，必须递到最里层，即n=1的时候，才开始归，即开始弹栈；每个方法的调用都要存储方法相关的信息，如参数，返回地址等，当调用的过程很深的时候，占用的内存逐渐增加，并且都没有释放，因为还没有开始归，只有拿到了返回值，对应的方法内存才释放，所以会导致栈内存占用太高，栈内存耗尽，抛出栈溢出错误。
2.尾递归与尾调用
定义：
如果函数的最后一步是调用一个函数，那么称为尾调用
function(){
return a()
}
反例：以下不是尾调用
function(){
int result = a();
return result; // 不是调用函数
}
function(){
return a()+1; // 虽然调用了，但是又用到了外层函数的数值1，最后一步实际是加法操作，不是函数调用
}
function(){
return a()+b; // 虽然调用了，但是又用到了外层函数的变量b，最后一步是加法操作
}
编译器的优化：
一些语言的编译器能对尾调用做优化：
a(){
return b();
}
b(){
return c();
}
c(){
return 100;
}
a();
没优化：最内层的c没有返回之前，a和b都不能结束。
a(){
b(){
c(){
return 100;
}
}
}
优化后：平级调用，a调用完，不需要等待b返回，直接释放内存。
a()；
b();
c();
因为尾调用的操作，自己要做的事情已经全部执行完了，只需要等待调用方的结果就可以了，所以可以把自己的内存释放掉了。上面的例子中，return a()+1;这种情况，当拿到了a的返回值，函数本身还要拿着结果去执行+1的操作，所以不能提前结束。
尾递归：最后调用的函数是自己。
支持尾递归和尾调用优化的语言有scala和C++
3.使用尾递归避免爆栈问题
import scala.annotation.tailrec
object Main {
def main(args: Array[String]): Unit = {
println(sum(10000000, 0))
}
@tailrec
def sum(n: Long, accumulator: Long): Long = {
if (n == 1) {
return 1 + accumulator
}
return sum(n - 1, n + accumulator)
}
调用过程：
sum(n=3, accumulator=0): Long = {
return sum(2, 3)
}
sum(n=2, accumulator=3): Long = {
return sum(1, 5)
}
sum(n=1, accumulator=5): Long = {
if (n == 1) {
return 1 + 5
}
}
4.使用迭代避免爆栈问题
public static long sum(long n){
long sum = 0;
for (long i = 0; i <= n; i++) {
sum = sum + i;
}
return sum;
}
理论上所有的递归都能使用迭代写出来
