网站内链越多越好嘛,好吃易做的家常菜网站,dedecms5.7 财经网站,wordpress安全登录插件下载要学会试着安静下来 —— 24.9.17 一、递归的定义
计算机科学中#xff0c;递归是一种解决计算问题的方法#xff0c;其中解决方案取决于同一类问题的更小子集
说明: ① 自己调用自己#xff0c;如果说每个函数对应着一种解决方案#xff0c;自己调用自己意味着解决方案是… 要学会试着安静下来 —— 24.9.17 一、递归的定义
计算机科学中递归是一种解决计算问题的方法其中解决方案取决于同一类问题的更小子集
说明: ① 自己调用自己如果说每个函数对应着一种解决方案自己调用自己意味着解决方案是一样的(有规律的) ② 每次调用函数处理的数据会较上次缩减(子集)而且最后会缩减至无需继续递归 ③ 内层函数调用(子集处理)完成外层函数才能算调用完成内层完成外层才能完成——先处理子问题
二、递归的解题思路
1.确定能否使用递归求解
2.推导出递推关系即父问题与子问题的关系以及递归的结束条件
① 深入到最里层叫递
② 从最里层出来叫归
③ 在递的过程中外层函数内的局部变量以及方法参数并未消失归的时候还可以用到
④ 大问题慢慢递到小问题再从小问题计算结果归回大问题
⑤ 递的时候是顺序的归的时候是逆序的
三、递归——习题
1.阶乘
用递归的方法求阶乘
阶乘的定义n 1*2*.3*(n-2)*(n-1)*n其中n为自然数当然0! 1
递推关系f(n) 1n 1f(n) n * f(n-1), n 1
public class demo1Factorial {// 递归函数public static int factorial(int n) {if (n 1){return 1;}return n * factorial(n-1);}public static void main(String[] args) {demo1Factorial demo1Factorial new demo1Factorial();System.out.println(demo1Factorial.factorial(5));System.out.println(factorial(6));System.out.println(factorial(7));System.out.println(factorial(8));}
}2.反向打印字符串
用递归反向打印字符串n为字符在整个字符串 str 中的索引位置。
递n从0开始每次n1一直递到n str.length()-1。
归从nstr.length()开始归从归打印自然是逆序的
递推关系f(m)1rn1)osns.h()-1nstr.length()
注因为是先递再归所以反向打印字符串输出语句的位置应该放在调用递归函数之后
public class demo2ReversePrintStr {// 静态方法反向打印字符串public static void reversePrintStr(String str,int n) {if (n str.length()){return;}// System.out.print(str.charAt(n) );reversePrintStr(str,n1);System.out.print(str.charAt(n) );}public static void main(String[] args) {reversePrintStr(YYSHlcl,0);}
} 3.二分查找
输入元素返回元素在有序数组中的位置
前提待查找数组是有序数组
public class demo3BinarySearch {public static int binarySearch(int[] arr, int key) {int target Finding(arr,key,0,arr.length-1);return target;}private static int Finding(int[] arr, int key,int i,int j) {if (i j){return -1;}int m (i j) 1;if (key arr[m]) {return m;}else if (key arr[m]) {j m-1;return Finding(arr,key,i,j);}else {i m1;return Finding(arr,key,i,j);}}public static void main(String[] args) {int[] arr {7,9,11,12,24,34,65,81,98};int res binarySearch(arr, 81);System.out.println(结果为res);System.out.println(binarySearch(arr, 7));System.out.println(binarySearch(arr, 9));System.out.println(binarySearch(arr, 81));}
}4.递归冒泡排序
将数组划分成两部分 [0…j][j1…a.length-1]
左边 [0…j] 是未排序部分
右边 [j1…a.length-1]是已排序部分
未排序区间内相邻的两个元素比较,如果前一个大于后一个,则交换位置
package Day7Recursion;import java.util.Arrays;public class demo4BubbleSort {public static void sort(int[] arr) {bubble(arr,arr.length-1);}// j代表未排序区域的右边界private static void bubble(int[] arr, int j) {if (j 0){return;}for (int i 0; i j; i) {if (arr[i] arr[i 1]) {int temp arr[i];arr[i] arr[i 1];arr[i 1] temp;}}bubble(arr, j - 1);}public static void main(String[] args) {int[] arr { 5, 4, 3, 2, 1 };System.out.println(Arrays.toString(arr));bubble(arr,arr.length-1);System.out.println(Arrays.toString(arr));sort(arr);System.out.println(Arrays.toString(arr));}
}将已排序的部分省略提高效率 private static void adbubble(int[] arr, int j) {if (j 0){return;}int x 0;for (int i 0; i j; i) {if (arr[i] arr[i 1]) {int temp arr[i];arr[i] arr[i 1];arr[i 1] temp;x i;}}adbubble(arr,x);}5.插入排序
插入排序Insertion Sort是一种简单直观的排序算法。它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。插入排序在实现上通常采用in-place排序即只需用到O(1)的额外空间的排序因而在从后向前扫描过程中找到排序位置后需要将已排序元素逐步向后挪位为最新元素提供插入空间。
插入排序将元素放在一个已排序的元素队列中使其仍然有序类比于扑克牌将插入位置找到后插入元素
import java.util.Arrays;public class demo5InsertSort {public static void sort(int[] arr) {insertSort(arr,1);}// low代表未排序区域的下边界private static void insertSort(int[] arr,int low) {// 代表所有元素都已经被排序if (low arr.length) {return;}int t arr[low];int i low - 1; // 已排序区域指针while (i 0 arr[i] t){ // 循环找到插入位置arr[i1] arr[i];i--;}// 找到插入位置arr[i1] t;insertSort(arr,low1);}public static void main(String[] args) {int[] arr {111,27,36,45,51,63,7,81,9};sort(arr);System.out.println(Arrays.toString(arr));}
}四、多路递归
上面写到的递归都是只调用了一次递归函数我们也称之为单路递归
如果每个递归函数包含多个自身的调用我们称之为多路递归
1.斐波那契数列
思路多路进行递归将问题转化为子问题逐步小化问题 public class demo1MoreFib {public static int fib(int n) {if (n0){return 0;}if (n1){return 1;}int x fib(n-1);int y fib(n-2);return x y;}public static void main(String[] args) {int fib fib(9);System.out.println(第九项斐波那契数列返回结果为fib);}
}斐波那契数列的时间复杂度推导 2.兔子问题
第一个月有一对未成熟的兔子
第二个月它们成熟
第三个月它们能产下一对新的小兔子
所有兔子遵循相同规律求第n 个月的兔子数
注意注意停止迭代条件与开始数列条件与斐波那契数列的变化
import java.util.Scanner;public class demo2FibRabbit {public static int fib(int n) {if (n1||n2){return 1;}return fib(n-1)fib(n-2);}public static void main(String[] args) {System.out.println(请您输入你想要得知的月份);Scanner sc new Scanner(System.in);int month sc.nextInt();int rab fib(month);System.out.println(第month月的小兔子有rab只);}
}3.青蛙爬楼梯
楼梯有 n. 阶
青蛙要爬到楼顶可以一次跳一阶也可以一次跳两阶
只能向上跳问有多少种跳法
import java.util.Scanner;public class demo3frag {public static int fibFrag(int n) {if (n 1){return 1;}if (n 2){return 2;}return fibFrag(n-1) fibFrag(n-2);}public static void main(String[] args) {Scanner sc new Scanner(System.in);System.out.println(请输入您想要让青蛙上几楼);int n sc.nextInt();int method fibFrag(n);System.out.println(共用method种跳法);}
}4.汉诺塔问题 Tower of Hanoi是一个源于印度古老传说大梵天创建世界时做了三根金刚石柱在一根柱子从下往上按大小顺序摞着 64 片黄金圆盘大梵天命令婆罗门把圆盘重新摆放在另一根柱子上并且规定 ① 一次只能移动一个圆盘 ② 小圆盘上不能放大圆盘
思路
① 一个圆盘圆盘1a——c
② 两个圆盘圆盘1a——b、圆盘2a——c、圆盘1b——c
③ 三个圆盘圆盘12a——b、圆盘3a——c、圆盘12b——c
④ 四个圆盘圆盘123a——b、圆盘4a——c、圆盘123b——c
时间复杂度计算T(n) 2T(n-1) c,T(1) c T(n) c(2^n-1)
import java.util.LinkedList;public class demo4HanoiTower {// 三个LinkedList集合代表三根柱子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);}}// 设计递归函数 n圆盘个数 a原始柱子 b借用柱子 c目标柱子static void move(int n,LinkedListInteger a,LinkedListInteger b,LinkedListInteger c){if (n0){return;}// 将n-1个盘子由a借助c移动到b上move(n - 1, a, c, b);c.addLast(a.removeLast()); // 中间步骤Print();// 将n-1个盘子由b借用a移动到c上move(n - 1, b, a, c);}public static void Print(){System.out.println(————————————————————————);System.out.println(a);System.out.println(b);System.out.println(c);}public static void main(String[] args) {init(3);Print();move(3,a,b,c);}// 时间复杂度计算T(n) 2T(n-1) c,T(1) c// T(n) c(2^n-1)
}5.杨辉三角
分析
行i列j那么[i][j]的取值应该为[ i-1 ][ j-1 ] [ i-1 ][ j ]
当 j 0 或 i j 时[ i ][ j ]的取值为-1
public class demo5YangHui {public static int element(int i,int j){if (j 0||j i){return 1;}return element(i - 1,j - 1)element(i - 1,j);}// 打印空格private static void printSpace(int n,int i){int num (n - 1 - i) * 2;for (int j 0; j num; j) {System.out.print( );}}public 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();}}public static void main(String[] args) {Print(9);}}6.杨辉三角——改进版1
用一个二维数组接收上次遍历的杨辉三角的数值然后根据上一行的数据进行相加
用二维数组的空间复杂度换取递归的时间复杂度
public class demo6YangHuiEx1 {// 记忆法利用二维数组进行缓存优化public static int element(int[][] triangle,int i,int j){if (triangle[i][j] 0){return triangle[i][j];}if (j 0 || i j){triangle[i][j] 1;return 1;}triangle[i][j] element( triangle,i - 1,j - 1) element(triangle,i - 1, j);return triangle[i][j];}// 打印空格 空格与高度和行号有关private static void printSpace(int n,int i){int num (n - 1 - i) * 2;for (int j 0; j num; j) {System.out.print( );}}public static void Print(int n){int[][] triangle new int[n][];for (int i 0; i n; i) {triangle[i] new int[i1];// 空格与高度和行号有关printSpace(n,i);for (int j 0; j i; j) {// 格式化输出 宽度为4 从左对齐System.out.printf(%-4d,element(triangle,i,j));}System.out.println();}}public static void main(String[] args) {Print(5);}
}7.杨辉三角——改进版2
利用一维数组记忆存储用少量的空间复杂度换取递归的时间复杂度
这种算法也称为动态规划算法
public class demo7YangHuiEx2 {// 记忆法利用一维数组进行缓存优化// 打印空格 空格与高度和行号有关private static void printSpace(int n,int i){int num (n - 1 - i) * 2;for (int j 0; j num; j) {System.out.print( );}}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 Print(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) {// 格式化输出 宽度为4 从左对齐System.out.printf(%-4d,row[j]);}System.out.println();}}public static void main(String[] args) {Print(7);}
}递归避免爆栈问题 —— 用循环代替递归 循环的空间复杂度通常较低主要取决于循环体内声明的局部变量和使用的数据结构。递归的空间复杂度较高主要由递归调用的最大深度和每次递归所需的辅助空间决定。在设计和分析递归算法时需要特别注意空间复杂度的控制以避免栈溢出等问题。 五、递归时间复杂度的计算
其中 ① T(n)是问题的运行时间n是数据规模 ② a是子问题个数 ③ T(n/b)是子问题运行时间每个子问题被拆成原问题数据规模的n/b ④ f(n)是除递归外执行的计算
令x logba即 x log子问题缩小倍数 子问题个数
则 1.公式求解
例一 例二 例三 例四 例五 二分查找递归 private static int Finding(int[] arr, int key,int i,int j) {if (i j){return -1;}int m (i j) 1;if (key arr[m]) {return m;}else if (key arr[m]) {j m-1;return Finding(arr,key,i,j);}else {i m1;return Finding(arr,key,i,j);}} 子问题个数a 1 子问题数据规模缩小倍数b 2 除递归外执行的计算是常数级 c 0 T(n) T(n/2) n^b 此时 x c 0时间复杂度是T(n^0*logn) T(logn) 归并排序 // 归并排序private void split(int arr[],int i,int j,int arr2[]) {if(j-i 1){return;}int m (ij)/2;// 递归split(arr,i,m,arr2);split(arr,m,j,arr2);// 合并merge(arr,i,m,j,arr2);} 子问题个数 a 2 子问题数据规模缩小倍数 b 2 除递归外主要时间花在合并上它可以用f(n) n表示 T(n) 2T(n/2) n 此时 x c 1时间复杂度是Θ(nlogn) 快速排序递归 // 快速排序递归private static void algorithm quicksort(int[] arr,int low,int high){if (low high || low 0 || high arr.length){return;}// 分区int p partition(arr,low,high);// 递归quicksort(arr,low,p-1);quicksort(arr,p1,high);} 子问题个数a 2 子问题数据规模缩小倍数 如果分区分的好b 2 如果分区没分好例如分区1的数据是0分区2的数据是n-1 除递归外主要时间花在分区上它可以用f(n) n表示 情况1 分区分的好 T(n)2T(n/2)n · 此时xc1时间复杂度Θ(nlogn) 情况2 分区没分好 T(n)T(n-1)T(1)n 不成比例此时不能用主定理求解 2.展开求解
递归式不能用公式求解每次递归时间复杂度不同所以将式子展开求出每次递归的时间复杂度进行累计求出最后的时间复杂度
例一 递归求和 例二 递归冒泡排序 例三 递归快排
