1 递归定义： 自己调用自己
2 递归分类：
·- 直接递归：方法自身调用自己。
·- 间接递归：A方法调用B方法，B方法调用C方法，C方法再调用A方法。
3 注意事项
·递归一定要有条件限定，保证递归能够停止下来，否则会形成死循环并发生栈内存溢出（StackOverflowError）。
·禁止构造方法递归。
·内层函数调用（子调用）完成，外层函数才能算调用完成【内层函数调用的时候，外层函数中引用的变量不会被JVM回收】！！！！
·递归就是“递”到最后，将结果一层一层往回“归”。
·尾递归的语言： scala 和 c++ 语言。
·尾调用： return语句的返回值是返回调用递归方法的返回值 就不需要调用递归之后 再回来“归”的过程
4 单路递归
定义：(递归函数只包含一个自身调用)：
单路递归案例： 阶乘、二分查找、冒泡排序、插入排序
代码实现：
//阶乘案例
privite int jiecheng(int n){
if (n == 1){
return 1;
}
return n * jiecheng(n-1)
}
public static void main[String[] args](){
int value = jiecheng(5);
System.out.println(value);
}
图理解
5 多路递归：
定义：（递归函数包含多个自身调用）
多路递归案例：斐波那契数列【含兔子问题、青蛙跳台阶】、汉诺塔、杨辉三角。
图理解：
原来版本: 时间复杂度O(1.618的n次方)
改进版本：时间复杂度O(n) 代价： 增加了额外的空间
代码实现
//斐波那契数列案例
package SF_DiGui;
import java.util.Arrays;
public class Fibonacci {
public static void main(String[] args) {
System.out.println(f1(5));
System.out.println(Fibonacci(5));
}
//原始版本
public static int f1(int n) {
//从第三项开始 每一项的值为前两项之和 数学定义 F(0) = 0，F(1) = 1, F(n) = F(n - 1) + F(n - 2)（n ≥ 2，n ∈ N*）。
//TODO 初始化前两项
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
return f1(n - 1) + f1(n - 2);
}
//改进版本
private static int Fibonacci(int n) { //斐波那契数列从索引0开始 记忆数组需要n+1个元素
int[] cache = new int[n + 1];
Arrays.fill(cache, -1);
cache[0] = 0;
cache[1] = 1;
return f2(n, cache);
}
//改进版本
//定义方法 斐波那契数列: 0,1、1、2、3、5、8、13、21、34……
public static int f2(int n, int[] cache) {
//从第三项开始 每一项的值为前两项之和 数学定义 F(0) = 0，F(1) = 1, F(n) = F(n - 1) + F(n - 2)（n ≥ 2，n ∈ N*）。
//TODO 已经初始化了前两项
if (cache[n] != -1) {
return cache[n];
}
cache[n] = f2(n - 1, cache) + f2(n - 2, cache);
return cache[n];
}
}
6 递归常见案例：
递归二分查找：
//递归查找值
public staic int binarySearch(int[] arr, int target, int i, int j){
if (i > j){
return -1; 递归调用到i > j的时候说明没有找到元素 返回-1
}
int m = (i + j) >>> 1;
if (target < arr[m]){
binarySearch(arr, targrt, 0, m-1)
}else if (arr[m] < target){
binarySearch(arr, targrt, m+1, j)
}else{
return m;
}
}
递归冒泡排序法：
双for版本: 具体笔记
递归版本：
private static void bubble_digui(int[] arr, int last) {
//递归 每次将最大的值泡在最后面
if (last == 0) {
return; //只剩第一个 不需要排序
}
for (int i = 0; i < last; i++) { //这里的last是最后一位索引 i+1 不会越界
if (arr[i] > arr[i + 1]) {
int t = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = t;
}
}
//循环结束后 最大值跑到最后一位
bubble_digui(arr, last - 1);
}
//缺点 每次都需要从最后一位往前排序 如果前面是有序的就做了无用功了
递归改进版本[产生临界]:
private static void bubble_digui2(int[] arr, int last) {
//递归 每次将最大的值泡在最后面
if (last == 0) {
return; //只剩第一个 不需要排序
}
int linjie = 0; //定义一个临界边
for (int i = 0; i < last; i++) { //这里的last是最后一位索引 i+1 不会越界
if (arr[i] > arr[i + 1]) {
int t = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = t;
linjie = i; //如果没有更新 说明linjie右边都是有序的 并没发生交换
}
}
/**
* TODO
* 改进版： 假设一个案例数组 【1，3，5，7，8，9】
* 对于这个假设的案例，双for 和 递归 都会比较所有！！！！ ===> 不必要的比较 因为本身有序
* 对于改进版 如果没有发生交换值--> 不会更新linjie值【说明linjie右边都是有序的】 下次递归 右边有序的不会参与比较
*/
//循环结束后 最大值跑到最后一位
bubble_digui2(arr, linjie); //缺点 每次都需要从最后一位往前 如果前面是有序的就做了无用功了
}
递归插入排序法：
//递归实现插入排序 low传递1 因为第一个元素默认不需要排序
private static void insertSort_digui(int[] arr, int low){
if (low == arr.length){ //防止最后一步会越界
return;
}
int insertvalue = arr[low];
int last = low - 1; //last 表示插入序列的最后一个元素 必须>=0 因为插入元素最远插入到第一个元素
while (last >= 0 && arr[last] > insertvalue){
//将大数值向后去
arr[last+1] = arr[last]; //此处arr[last] 下次比较时候 比插入元素比较小的时候 插入元素的侯选位置
last--;
}
//将插入元素放置last加1的位置 因为 last小于等于insertValue的时候 才会推出循环 last+1 是候选位置
arr[last+1] = insertvalue;
//上面一行赋值细节情况: 当low索引的值与前面不需要交换时候 说明low前面正常是有序的【就是last + 1 == low的情况】 就不需要赋值操作
// if (last + 1 != low){
// arr[last+1] = insertvalue;
// } //没必要添加
insertSort_digui(arr, low + 1);
}
多路递归杨辉三角：
模型： x表示行 y表示列【y=0列 和 x=y的元素都是1】 初始值
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
package SF_DiGui;
public class duoluDiGui {
public static void main(String[] args) {
print2(5);
}
private static void printSpace(int n, int i){
int num = (n-i-1)*2;
for (int j = 0; j < num;j++){
System.out.print(" ");
}
}
private static void print(int n){
for (int i = 0;i < n; i++){
printSpace(n,i);
for (int j = 0; j <= i;j++){
System.out.printf("%-4d",element(i,j));
}
System.out.println();
}
}
//普通做法
private static int element(int x, int y){ //x表示行 y表示列
if (y==0 || x == y){
return 1;
}
return element(x-1,y-1) + element(x-1,y); //根据坐标系 笔记中有
}
//-----------------------------------------------------------------
private static void print1(int n){
int[][] taringle = new int[n][]; //初始化n行
for (int i = 0;i < n; i++){ i 表示 索引i行 i+1表示索引i行的元素个数【数组长度】
taringle[i] = new int[i+1]; //第i行的元素个数 = 行数i + 1
printSpace(n,i);
for (int j = 0; j <= i;j++){
System.out.printf("%-4d",element1(taringle,i,j));
}
System.out.println();
}
}
//二位数组记忆法
private static int element1(int[][] taringle, int x, int y){
if (taringle[x][y] > 0){ //初始值都是0 如果大于1 说明更新过了
return taringle[x][y];
}
if (x == y || y == 0){
taringle[x][y] = 1;
return 1;
}
//记忆法：记住那些重复调用的函数返回值，下次判断存不存再即可
taringle[x][y] = element1(taringle,x-1,y-1) + element1(taringle,x-1, y);
return taringle[x][y];
}
//-----------------------------------------------------------------
//一维数组记忆法改进2
/**
* parame row 上一行数组
* parame i 行号
*
*/
1 0 0 0 0 i = 0行
1 1 0 0 0 i = 1行
1 2 1 0 0 i = 2行
1 3 3 1 0 i = 3行
1 4 6 4 1 i = 4行
一个特性: 从第二行开始【第二个元素开始】 每个元素 --> |x，y| = |x-1, y-1| + |x-1, y|
根据这个特性 使用一维数组 记忆数据 减少内存占用 提高时间效率
private static void createRow(int[] row: 一维数组, int i){ //方法名：根据上一行生成新的一行
if (i == 0){ //TODO 第1行必须进行初始化的 特性是从第二行开始的！！！！
row[0] = 1; //因为无论是哪一行 第一个元素都是1 下面只要不动row[0] 就一直是1
return;
}
for (int j = i; j > 0;j--){ //特性是从 第二个元素开始的 j 不能取到0; 我们需要更新第二个及以后的元素即可
row[j]: 新复制的 = row[j]: 原来的 + row[j-1];
}
}
private static void print2(int n){
int[] row = new int[n]; //n行有n个元素 初始化一次就行
for (int i = 0;i < n; i++){
createRow(row,i); //第i行的元素个数 = 行数i + 1
printSpace(n,i);
for (int j = 0; j <= i;j++){
System.out.printf("%-4d",row[j]);
}
System.out.println();
}
}
}