远程wordpress数据库备份,揭阳百度推广优化,seo方法,科普网站建设经验一、递归
1. 概述
定义#xff1a;在计算机科学中#xff0c;递归是一种解决计算问题的方法#xff0c;其中解决方案取决于同一类问题的更小子集。
比如单链表递归遍历的例子#xff1a; void f(Node node) {if(node null) {return;}println(before: node…一、递归
1. 概述
定义在计算机科学中递归是一种解决计算问题的方法其中解决方案取决于同一类问题的更小子集。
比如单链表递归遍历的例子 void f(Node node) {if(node null) {return;}println(before: node.value)f(node.next);println(after: node.value)
} 说明
自己调用自己如果说每个函数对应着一种解决方案自己调用自己意味着解决方案是一样的有规律的每次调用函数处理的数据会较上次缩减子集而且最后会缩减至无需继续递归内层函数调用子集处理完成外层函数才能算调用完成 原理
假设链表中有3个节点value分别为123以上代码的执行流程类似于下面的伪码 // 1 - 2 - 3 - null f(1)void f(Node node 1) {println(before: node.value) // 1void f(Node node 2) {println(before: node.value) // 2void f(Node node 3) {println(before: node.value) // 3void f(Node node null) {if(node null) {return;}}println(after: node.value) // 3}println(after: node.value) // 2}println(after: node.value) // 1
} 思路 1. 确定能否使用递归求解
2. 推导出递推关系即父问题与子问题的关系以及递归的结束条件
例如之前遍历链表的递推关系为 深入到最里层叫递从最里层处理叫归在递的过程中外层函数内的局部变量以及方法参数并未消失归的时候还可以用到 2. 单路递归Single Recursion
2.1 阶乘
用递归方法求阶乘
阶乘的定义n! 1 * 2 * 3 ... (n - 2) * (n - 1) * n其中n为自然数当然 0! 1递推关系 代码 private static int f(int n) {if (n 1) {return 1;}return n * f(n - 1);
} 拆解伪码如下假设n初始值为3 f(int n 3) { // 解决不了,递return 3 * f(int n 2) { // 解决不了,继续递return 2 * f(int n 1) {if (n 1) { // 可以解决, 开始归return 1;}}}
} 2.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));
} 2.2 二分查找单路递归 public static int binarySearch(int[] a, int target) {return recursion(a, target, 0, a.length - 1);
}public static int recursion(int[] a, int target, int i, int j) {if (i j) {return -1;}int m (i j) 1;if (target a[m]) {return recursion(a, target, i, m - 1);} else if (a[m] target) {return recursion(a, target, m 1, j);} else {return m;}
} 2.3 冒泡排序单路递归
将数组划分为两部分[0 ... j] [j 1 ... a.length - 1]左边[0 ... j]是未排序部分右边[j 1 ... a.length - 1]是已排序部分未排序区间内相邻的两个元素比较如果前一个大于后一个则交换位置 public static void main(String[] args) {int[] a {3, 2, 6, 1, 5, 4, 7};bubble(a, 0, a.length - 1);System.out.println(Arrays.toString(a));
}private static void bubble(int[] a, int low, int high) {if(low high) {return;}int j low;for (int i low; i high; i) {if (a[i] a[i 1]) {swap(a, i, i 1);j i;}}bubble(a, low, j);
}private static void swap(int[] a, int i, int j) {int t a[i];a[i] a[j];a[j] t;
} low与high为未排序范围j表示的是未排序的边界下一次递归时的high发生交换意味着有无序情况最后一次交换以后没有无序时左侧i仍是无序右侧i1已然有序 private static void bubble(int[] a, int j) {if (j 0) {return;}int x 0; // x右侧的元素都是有序的for(int i 0; i j; i) {{if(a[i] a[i 1]) {{int t a[i];a[i] a[i 1];a[i 1] t;x i;}}bubble(a, x);
} C版冒泡排序exchange右侧都是有序的 #includeiostream
#includevector
using namespace std;void BubbleSort(vectorint data, int length){int j, exchange, bound, temp;exchange length - 1; // 第一趟冒泡排序的区间是[0 ~ length - 1]while(exchange ! 0){bound exchange;exchange 0;for(j 0; j bound; j) // 一趟冒泡排序的区间是[0 ~ bound]{if(data[j] data[j 1]){temp data[j];data[j] data[j 1];data[j 1] temp;exchange j; // 记载每一次记录交换的位置 }} }
} 2.4 插入排序单路递归 public static void main(String[] args) {int[] a {3, 2, 6, 1, 5, 7, 4};insertion(a, 1, a.length - 1);System.out.println(Arrays.toString(a));
}private static void insertion(int[] a, int low, int high) {if (low high) {return;}// low指针指的是未排序区的边界int i low - 1; // 已排序区的指针int t a[low];while (i 0 a[i] t) { // 没有找到插入位置a[i 1] a[i]; // 空出插入位置i--;}if(i 1 ! low) {a[i 1] t;} insertion(a, low 1, high);
} public void insertionSort(int[] nums, int length) {int i, j, temp;for(i 1; i length; i) {temp nums[i];for(j i - 1; j 0 temp nums[j]; j--) { // 寻找插入位置nums[j 1] nums[j]; // 后移}nums[j 1] temp;}
} 2.5 约瑟夫问题单路递归
n个人排成圆圈从头开始报数每次数到第m个人杀之继续从下一个人重复以上过程求最后活下来的人是谁
解法一
设josephus(n, m)表示在n个人中每m个人被杀时最后存活的人。递归关系为 josephus(n, m) (josephus(n - 1, m) m) % n, n 1 josephus(1, m) 0 这个关系的意思是若我们知道n-1个人时的存活者我们可以通过调整索引来得出n个人时的存活者。 class Solution { public int findTheWinner(int n, int m) { return josephus(n, m) 1; // 转换为1-based索引 } private int josephus(int n, int m) { if (n 1) return 0; // 只有一个人时返回其索引0 return (josephus(n - 1, m) m) % n; // 递归公式 } public static void main(String[] args) { Solution solution new Solution(); int n 7; // 总人数 int m 3; // 每次报数到m的人被杀 int winner solution.findTheWinner(n, m); System.out.println(最后存活下来的人的位置是: winner); // 输出最后存活者的1-based索引 }
} 3 多路递归 Multi Recursion
如果每个递归函数例包含多个自身调用称之为multi recursion 3.1 裴波那契数列
假设你正在爬楼梯。需要 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 阶提示
1 n 45
Java实现
解法一递归会超时 class Solution {public int climbStairs(int n) {if(n 1) {return 1;}if(n 2) {return 2;}return climbStairs(n - 1) climbStairs(n - 2);}
} 递归的次数也符合斐波那契数列规律2 * f(n 1) - 1
时间复杂度推导过程
解法二 class Solution {public int climbStairs(int n) {if(n 1) {return 1;}if(n 2) {return 2;}int prev 1;int curr 2;for(int i 3; i n; i) {int temp curr;curr prev curr;prev temp;}return curr;}
} 3.2 兔子问题
第一个月有一对未成熟的兔子。第二个月它们成熟。第三个月它们能产下一对新的小兔子。所有兔子遵循相同规律求第n个月的兔子数量。
分析设第n个月兔子数为f(n)
f(n) 上个月兔子数 新生的小兔子数新生的小兔子数 上个月成熟的兔子数因为需要一个月兔子就成熟所以【上个月成熟的兔子数】也就是【上上个月的兔子数】上个月兔子数即f(n - 1)上上个月的兔子数即f(n-2)
递推公式f(n) f(n -1) f(n - 2) class Solution {public int f(int n) {if(n 1 || n 2) {return 1;}int a 1; // f(n-2)int b 1; // f(n-1)int count 0;for(int i 3; i n; i) {count a b;a b; // 更新f(n-2)b count; // 更新f(n-1)}return count;}
} 3.3 汉诺塔问题多路递归
Tower of Hanoi是一个源于印度古老传说大梵天创建世界时做了三根金刚石柱在一根柱子从下往上按大小顺序摞着 64 片黄金圆盘大梵天命令婆罗门把圆盘重新摆放在另一根柱子上并且规定 一次只能移动一个圆盘 小圆盘上不能放大圆盘
下面的动图演示了4片圆盘的移动方法 解法一递归。时间复杂度O(2^n)
递归分解
若有n个盘子以A、B和C分别表示起始柱、辅助柱和目标柱首先将前n-1个盘子从柱A移动到柱B使用柱C作为辅助接下来将第n个盘子最大的盘子从柱A移动到柱C最后将n-1个盘子从柱B移动到柱C使用柱A作为辅助
class Solution { public void hanota(ListInteger A, ListInteger B, ListInteger C) { int n A.size(); moveDisks(n, A, C, B); // A - C B为辅助 } private void moveDisks(int n, ListInteger from, ListInteger to, ListInteger aux) { // 基本情况如果没有盘子要移动直接返回 if (n 0) { return; } // 1. 将 n-1 个盘子从 from 移动到 aux使用 to 作为辅助 moveDisks(n - 1, from, aux, to); // 2. 将第 n 个盘子从 from 移动到 to to.add(from.remove(from.size() - 1)); // 从 from 中移除最后一个盘子并添加到 to // 3. 将 n-1 个盘子从 aux 移动到 to使用 from 作为辅助 moveDisks(n - 1, aux, to, from); }
}
package com.itheima.algorithm.recursion_multi;import org.springframework.util.StopWatch;import java.util.LinkedList;/*** 递归汉诺塔*/
public class E02HanoiTower {static LinkedListInteger a new LinkedList();static LinkedListInteger b new LinkedList();static LinkedListInteger c new LinkedList();static void init(int n) {for (int i n; i 1; i--) {a.addLast(i);}}/*** h3移动圆盘/h3** param n 圆盘个数* param a 由* param b 借* param c 至*/static void move(int n, LinkedListInteger a,LinkedListInteger b,LinkedListInteger c) {if (n 0) {return;}move(n - 1, a, c, b); // 把 n-1 个盘子由a,借c,移至bc.addLast(a.removeLast()); // 把最后的盘子由 a 移至 c
// print();move(n - 1, b, a, c); // 把 n-1 个盘子由b,借a,移至c}// T(n) 2T(n-1) c, O(2^64)public static void main(String[] args) {StopWatch sw new StopWatch();int n 1;init(n);print();sw.start(n1);move(n, a, b, c);sw.stop();print();System.out.println(sw.prettyPrint());}private static void print() {System.out.println(----------------);System.out.println(a);System.out.println(b);System.out.println(c);}
}3.3 杨辉三角
给定一个非负整数 numRows生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中每个数是它左上方和右上方的数的和。 示例 1:
输入: numRows 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]示例 2:
输入: numRows 1
输出: [[1]]提示:
1 numRows 30
递推公式triangle[i][j] triangle[i - 1][j - 1] triangle[i - 1][j]
解法一迭代
class Solution { public ListListInteger generate(int numRows) { ListListInteger triangle new ArrayList(); for (int i 0; i numRows; i) { ListInteger row new ArrayList(i 1); for (int j 0; j i; j) { if (j 0 || j i) { row.add(1); // 第一列和最后一列都为1 } else { // 当前元素等于上一行的两个元素之和 row.add(triangle.get(i - 1).get(j - 1) triangle.get(i - 1).get(j)); } } triangle.add(row); // 将当前行添加到三角形中 } return triangle; }
}
解法二递归。这个递归方法对于较大的 numRows接近 30可能会非常低效因为会有大量重复计算。对于较大的输入推荐使用迭代的方法。
class Solution { public ListListInteger generate(int numRows) { ListListInteger triangle new ArrayList(); for(int i 0; i numRows; i) {triangle.add(generateRow(i));}return triangle; } private ListInteger generateRow(int rowIndex) {ListInteger row new ArrayList();for(int j 0; j rowIndex; j) {row.add(getValue(rowIndex, j));}return row;}private int getValue(int row, int col) {if(col 0 || col row) {return 1;}return getValue(row - 1, col - 1) getValue(row - 1, col);}
}
解法二递归优化。备忘录模式
二维数组记忆法
class Solution { public ListListInteger generate(int numRows) { ListListInteger triangle new ArrayList(); // 创建一个二维数组用于存储已计算的值 Integer[][] memo new Integer[numRows][numRows]; for (int i 0; i numRows; i) { triangle.add(new ArrayList()); for (int j 0; j i; j) { triangle.get(i).add(getValue(i, j, memo)); } } return triangle; } private int getValue(int row, int col, Integer[][] memo) { // 如果位置超出边界返回 0 if (col 0 || col row) { return 0; } // 如果是边界元素(最左或最右)返回 1 if (col 0 || col row) { return 1; } // 如果已经计算过直接返回 if (memo[row][col] ! null) { return memo[row][col]; } // 递归计算并存储结果到 memo memo[row][col] getValue(row - 1, col - 1, memo) getValue(row - 1, col, memo); return memo[row][col]; }
}
解法三一维数组记忆法。 private static void createRow(int[] row, int i) {if (i 0) {row[0] 1;return;}for (int j i; j 0; j--) {// 下一行当前项等于 上一行的当前项 前一项row[j] row[j] row[j - 1];}}public static void print2(int n) {int[] row new int[n];for (int i 0; i n; i) { // 行createRow(row, i);
// printSpace(n, i);for (int j 0; j i; j) {System.out.printf(%-4d, row[j]);}System.out.println();}} 4. 递归优化 - 记忆法
斐波那契数列计算过程中存在很多重复的计算例如求f(5)的递归分解过程 可以看到颜色相同的是重复的
f(3)重复了2次f(2)重复了3次f(1)重复了5次f(0)重复了3次
随着n的增大重复次数非常可观如何优化呢
Menoization记忆法也称备忘录是一种优化技术通过存储函数调用结果通常比较昂贵当再次出现相同的输入子问题时就能实现加速效果。
public static void main(String[] args) {int n 13;int[] cache new int[n 1];Arrays.fill(cache, -1);cache[0] 0;cache[1] 1;System.out.println(f(cache, n));
}public static int f(int[] cache, int n) {if (cache[n] ! -1) {return cache[n];}cache[n] f(cache, n - 1) f(cache, n - 2);return cache[n];
}
优化后的图示只要结果被缓存就不会执行其子问题 改进前的时间复杂度为Θ(1.618^n)空间复杂度O(n)改进后的时间复杂度为O(n)空间复杂度为O(n)额外的空间缓存结果 5. 递归优化 - 尾递归
用递归做 n (n - 1) (n - 2) ... 1
public static long sum(long n) {if(n 1) {return 1;}return n sum(n - 1);
}
在我的机器上n 12000时爆栈了
Exception in thread main java.lang.StackOverflowErrorat Test.sum(Test.java:10)at Test.sum(Test.java:10)at Test.sum(Test.java:10)at Test.sum(Test.java:10)at Test.sum(Test.java:10)...
为什么呢
每次方法调用都是需要消耗一定的栈内存的这些内存用来存储方法参数、方法内局部变量、返回地址等。方法调用占用的内存需要等待方法结束时才会释放而递归调用不到最深不会回头最内层方法没完成之前外层方法都结束不了。 尾调用
如果函数的最后一步是调用一个函数那么称为尾调用例如
function a() {return b()
}
下面三段代码不能叫作尾调用
function a() {const c b()return c
}
最后一步并非调用函数
function a() {return b() 1
}
最后一步执行的是加法
function a(x) {return b() x
}
最后一步执行的是加法
一些语言的编译器能够对尾调用做优化例如
function a() {// 做前面的事return b()
}function b() {// 做前面的事return c()
}function c() {return 1000
}a()
没优化之前的伪码
function a() {return function b() {return function c() {return 1000}}
}
优化后的伪码如下
a()
b()
c()
为何尾递归才能优化
调用a时
a返回时发现没什么可留给b的将来返回的结果b提供就可以了用不着我a了我的内存就可以释放
调用b时
b返回时发现没什么可以留给c的将来返回的结果c提供就可以了用不着我b了我的内存就可以释放了
如果调用a时
不是尾调用例如return b() 1那么a就不能提前结束因为它还得利用b的结果做加法
尾递归是尾调用的一种特例也就是最后一步执行的是同一个函数 尾递归避免爆栈
安装Scala Scala入门
object Main {def main(args: Array[String]): Unit {println(Hello Scala)}
}
Scala是Java的近亲Java中的类都可以拿来重用类型是放在变量后面的Unit表示无返回值类似于void不需要以分号作为结尾当然加上也对
先写一个会爆栈的函数
def sum(n: Long): Long {if (n 1) {return 1}return n sum(n - 1)
}
Scala最后一行代码若作为返回值可以省略return
在n 11000时出了异常
println(sum(11000))Exception in thread main java.lang.StackOverflowErrorat Main$.sum(Main.scala:25)at Main$.sum(Main.scala:25)at Main$.sum(Main.scala:25)at Main$.sum(Main.scala:25)...
这时因为以上代码这不是尾调用要想成为尾调用那么
最后一行代码必须是一次函数调用
内层函数必须摆脱与外层函数的关系内层函数执行后不依赖于外层的变量或常量
def sum(n: Long): Long {if (n 1) {return 1}return n sum(n - 1) // 依赖于外层函数的 n 变量
}
如何让它执行后就拜托对n的依赖呢
不能等递归回来再做加法那样就必须保留外层的n把n当作内层函数的一个参数传进去这时n就属于内层函数了传参时就完成累加不必等回来时累加
sum(n - 1, n 累加器)
改写后代码如下
tailrec
def sum(n: Long, accumulator: Long): Long {if (n 1) {return 1 accumulator} return sum(n - 1, n accumulator)
}
accumulator作为累加器
tailrec注解是scala提供的用来检查方法是否符合尾递归
这回sum(10000000, 0)也没有问题打印50000005000000 执行流程如下以伪码表示sum(4, 0)
// 首次调用
def sum(n 4, accumulator 0): Long {return sum(4 - 1, 4 accumulator)
}// 接下来调用内层 sum, 传参时就完成了累加, 不必等回来时累加当内层 sum 调用后外层 sum 空间没必要保留
def sum(n 3, accumulator 4): Long {return sum(3 - 1, 3 accumulator)
}// 继续调用内层 sum
def sum(n 2, accumulator 7): Long {return sum(2 - 1, 2 accumulator)
}// 继续调用内层 sum, 这是最后的 sum 调用完就返回最后结果 10, 前面所有其它 sum 的空间早已释放
def sum(n 1, accumulator 9): Long {if (1 1) {return 1 accumulator}
}
本质上尾递归优化就是将函数的递归调用变成了函数的循环调用 改循环避免爆栈
public static void main(String[] args) {long n 100000000;long sum 0;for (long i n; i 1; i--) {sum i;}System.out.println(sum);
} 6. 递归时间复杂度 - 主定理Master theorem
若有递归式 其中
T(n)是问题的运行时间n是数据规模a是子问题的个数T(n/b)是子问题运行时间每个子问题被拆成原问题数据规模的n/bf(n)是除递归外执行的计算
令x log_b a即x log_子问题缩小倍数 子问题个数那么 例1T(n) 2T(n/2) n ^ 4
此时x 1 4由后者决定整个时间复杂度Θ(n^4)
例2T(n) T(7n / 10) n
此时x 0 1由后者决定整个时间复杂度Θ(n)
例3T(n) 16T(n/4) n^2
a 16, b 4, x 2, x 2此时x c 2时间复杂度为Θ(n^2 * logn)
例4T(n) 7T(n/3) n^2
a 7, b 3, c 2, x 1.?此时x c由后者决定整个时间复杂度Θ(n^2)
例5T(n) 7T(n/2) n^2
a 7, b 2, c 2, x 2.? c由前者决定整个时间复杂度Θ(n^log_2 7)
例6T(n) 2T(n/4) sqrt(n)
a 2, b 4, c 1/2x c时间复杂度为Θ(sqrt(n) * logn)
例7二分查找递归
int f(int[] a, int target, int i, int j) {if (i j) {return -1;}int m (i j) 1;if (target a[m]) {return f(a, target, i, m - 1);} else if (a[m] target) {return f(a, target, m 1, j);} else {return m;}
}
子问题个数a 1子问题数据规模缩小倍数b 2除递归之外执行的计算是常数级c 0此时x 0 c时间复杂度为Θ(logn)
例8归并排序递归
void split(B[], i, j, A[])
{if (j - i 1) return; m (i j) / 2; // 递归split(A, i, m, B); split(A, m, j, B); // 合并merge(B, i, m, j, A);
}
子问题个数a 2子问题数据规模缩小倍数b 2除递归外主要时间花在合并上它可以用f(n) n表示T(n) 2T(n/2) n此时x 1 c时间复杂度Θ(nlogn)
例9快速排序递归
algorithm quicksort(A, lo, hi) is if lo hi || lo 0 then return// 分区p : partition(A, lo, hi) // 递归quicksort(A, lo, p - 1) quicksort(A, p 1, hi) 子问题个数 a2 子问题数据规模缩小倍数 如果分区分的好b2 如果分区没分好例如分区1 的数据是 0分区 2 的数据是 n-1 除递归外主要时间花在分区上它可以用 $f(n) n 表示
情况1 - 分区分的好
T(n) 2T(n\2) n 此时 x1c时间复杂度 Θ(nlogn)
情况2 - 分区没分好
T(n) T(n-1) T(1) n 此时不能用主定理求解 7. 递归时间复杂度 - 展开求解
像下面的递归式都不能用主定理求解
例1递归求和
long sum(long n) {if (n 1) {return 1;}return n sum(n - 1);
}
T(n) T(n - 1) cT(1) c
下面为展开过程
T(n) T(n-2) c c
T(n) T(n-3) c c c
...
T(n) T(n-(n-1)) (n-1)c 其中 T(n-(n-1)) 即 T(1) 带入求得 T(n) c (n-1)c nc
时间复杂度为 O(n) 例2递归冒泡排序
void bubble(int[] a, int high) {if(0 high) {return;}for (int i 0; i high; i) {if (a[i] a[i 1]) {swap(a, i, i 1);}}bubble(a, high - 1);
}
T(n) T(n - 1) nT(1) c
下面为展开过程
T(n) T(n-2) (n-1) n
T(n) T(n-3) (n-2) (n-1) n
...
T(n) T(1) 2 ... n T(1) (n-1)*(2n)/2 c n^2/2 n/2 -1
时间复杂度 O(n^2)
注等差数列求和为 个数 * (首项 末项)/2 例3递归快排
快速排序分区没分好的极端情况
T(n) T(n-1) T(1) nT(1) c
T(n) T(n-1) c n
下面为展开过程
T(n) T(n-2) c (n-1) c n
T(n) T(n-3) c (n-2) c (n-1) c n
...
T(n) T(n-(n-1)) (n-1)c 2...n n^2 / 2 (2cn n) / 2 -1
时间复杂度 O(n^2)
不会推导的同学可以进入 Wolfram|Alpha: Computational Intelligence 例1 输入 f(n) f(n - 1) c, f(1) c 例2 输入 f(n) f(n - 1) n, f(1) c 例3 输入 f(n) f(n - 1) n c, f(1) c
