台州企业网站搭建图片,cms系统的基本功能是什么,中山百度网站推广,90设计网站几次是什么意思摘要#xff1a;大师 L. Peter Deutsch 说过#xff1a;To Iterate is Human, to Recurse, Divine.中文译为#xff1a;人理解迭代#xff0c;神理解递归。毋庸置疑地#xff0c;递归确实是一个奇妙的思维方式。对一些简单的递归问题#xff0c;我们总是惊叹于递归描述问…摘要大师 L. Peter Deutsch 说过To Iterate is Human, to Recurse, Divine.中文译为人理解迭代神理解递归。毋庸置疑地递归确实是一个奇妙的思维方式。对一些简单的递归问题我们总是惊叹于递归描述问题的能力和编写代码的简洁但要想真正领悟递归的精髓、灵活地运用递归思想来解决问题却并不是一件容易的事情。本文剖析了递归的思想内涵分析了递归与循环的联系与区别给出了递归的应用场景和一些典型应用并利用递归和非递归的方式解决了包括阶乘、斐波那契数列、汉诺塔、杨辉三角的存取、字符串回文判断、字符串全排列、二分查找、树的深度求解在内的八个经典问题。版权声明友情提示若读者需要本博文相关完整代码请移步我的Github自行获取项目名为 SwordtoOffer链接地址为https://github.com/githubofrico/SwordtoOffer。一. 引子大师 L. Peter Deutsch 说过To Iterate is Human, to Recurse, Divine.中文译为人理解迭代神理解递归。毋庸置疑地递归确实是一个奇妙的思维方式。对一些简单的递归问题我们总是惊叹于递归描述问题的能力和编写代码的简洁但要想真正领悟递归的精髓、灵活地运用递归思想来解决问题却并不是一件容易的事情。在正式介绍递归之前我们首先引用知乎用户李继刚(https://www.zhihu.com/question/20507130/answer/15551917)对递归和循环的生动解释递归你打开面前这扇门看到屋里面还有一扇门。你走过去发现手中的钥匙还可以打开它你推开门发现里面还有一扇门你继续打开它。若干次之后你打开面前的门后发现只有一间屋子没有门了。然后你开始原路返回每走回一间屋子你数一次走到入口的时候你可以回答出你到底用这你把钥匙打开了几扇门。循环你打开面前这扇门看到屋里面还有一扇门。你走过去发现手中的钥匙还可以打开它你推开门发现里面还有一扇门(若前面两扇门都一样那么这扇门和前两扇门也一样如果第二扇门比第一扇门小那么这扇门也比第二扇门小你继续打开这扇门一直这样继续下去直到打开所有的门。但是入口处的人始终等不到你回去告诉他答案。上面的比喻形象地阐述了递归与循环的内涵那么我们来思考以下几个问题什么是递归呢递归的精髓(思想)是什么递归和循环的区别是什么什么时候该用递归使用递归需要注意哪些问题递归思想解决了哪些经典的问题这些问题正是笔者准备在本文中详细阐述的问题。二. 递归的内涵1、定义 (什么是递归)在数学与计算机科学中递归(Recursion)是指在函数的定义中使用函数自身的方法。实际上递归顾名思义其包含了两个意思递 和 归这正是递归思想的精华所在。2、递归思想的内涵(递归的精髓是什么)正如上面所描述的场景递归就是有去(递去)有回(归来)如下图所示。“有去”是指递归问题必须可以分解为若干个规模较小与原问题形式相同的子问题这些子问题可以用相同的解题思路来解决就像上面例子中的钥匙可以打开后面所有门上的锁一样“有回”是指 : 这些问题的演化过程是一个从大到小由近及远的过程并且会有一个明确的终点(临界点)一旦到达了这个临界点就不用再往更小、更远的地方走下去。最后从这个临界点开始原路返回到原点原问题解决。更直接地说递归的基本思想就是把规模大的问题转化为规模小的相似的子问题来解决。特别地在函数实现时因为解决大问题的方法和解决小问题的方法往往是同一个方法所以就产生了函数调用它自身的情况这也正是递归的定义所在。格外重要的是这个解决问题的函数必须有明确的结束条件否则就会导致无限递归的情况。3、用归纳法来理解递归数学都不差的我们第一反应就是递归在数学上的模型是什么毕竟我们对于问题进行数学建模比起代码建模拿手多了。观察递归我们会发现递归的数学模型其实就是 数学归纳法这个在高中的数列里面是最常用的了下面回忆一下数学归纳法。数学归纳法适用于将解决的原问题转化为解决它的子问题而它的子问题又变成子问题的子问题而且我们发现这些问题其实都是一个模型也就是说存在相同的逻辑归纳处理项。当然有一个是例外的也就是归纳结束的那一个处理方法不适用于我们的归纳处理项当然也不能适用否则我们就无穷归纳了。总的来说归纳法主要包含以下三个关键要素步进表达式问题蜕变成子问题的表达式结束条件什么时候可以不再使用步进表达式直接求解表达式在结束条件下能够直接计算返回值的表达式事实上这也正是某些数学中的数列问题在利用编程的方式去解决时可以使用递归的原因比如著名的斐波那契数列问题。4、递归的三要素在我们了解了递归的基本思想及其数学模型之后我们如何才能写出一个漂亮的递归程序呢笔者认为主要是把握好如下三个方面1、明确递归终止条件2、给出递归终止时的处理办法3、提取重复的逻辑缩小问题规模。1). 明确递归终止条件我们知道递归就是有去有回既然这样那么必然应该有一个明确的临界点程序一旦到达了这个临界点就不用继续往下递去而是开始实实在在的归来。换句话说该临界点就是一种简单情境可以防止无限递归。2). 给出递归终止时的处理办法我们刚刚说到在递归的临界点存在一种简单情境在这种简单情境下我们应该直接给出问题的解决方案。一般地在这种情境下问题的解决方案是直观的、容易的。3). 提取重复的逻辑缩小问题规模*我们在阐述递归思想内涵时谈到递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题这些子问题可以用相同的解题思路来解决。从程序实现的角度而言我们需要抽象出一个干净利落的重复的逻辑以便使用相同的方式解决子问题。5、递归算法的编程模型在我们明确递归算法设计三要素后接下来就需要着手开始编写具体的算法了。在编写算法时不失一般性我们给出两种典型的递归算法设计模型如下所示。模型一 在递去的过程中解决问题function recursion(大规模){if (end_condition){ // 明确的递归终止条件end; // 简单情景}else{ // 在将问题转换为子问题的每一步解决该步中剩余部分的问题solve; // 递去recursion(小规模); // 递到最深处后不断地归来}}模型二 在归来的过程中解决问题function recursion(大规模){if (end_condition){ // 明确的递归终止条件end; // 简单情景}else{ // 先将问题全部描述展开再由尽头“返回”依次解决每步中剩余部分的问题recursion(小规模); // 递去solve; // 归来}}6、递归的应用场景在我们实际学习工作中递归算法一般用于解决三类问题(1). 问题的定义是按递归定义的(Fibonacci函数阶乘…)(2). 问题的解法是递归的(有些问题只能使用递归方法来解决例如汉诺塔问题…)(3). 数据结构是递归的(链表、树等的操作包括树的遍历树的深度…)。在下文我们将给出递归算法的一些经典应用案例这些案例基本都属于第三种类型问题的范畴。三. 递归与循环递归与循环是两种不同的解决问题的典型思路。递归通常很直白地描述了一个问题的求解过程因此也是最容易被想到解决方式。循环其实和递归具有相同的特性即做重复任务但有时使用循环的算法并不会那么清晰地描述解决问题步骤。单从算法设计上看递归和循环并无优劣之别。然而在实际开发中因为函数调用的开销递归常常会带来性能问题特别是在求解规模不确定的情况下而循环因为没有函数调用开销所以效率会比递归高。递归求解方式和循环求解方式往往可以互换也就是说如果用到递归的地方可以很方便使用循环替换而不影响程序的阅读那么替换成循环往往是好的。问题的递归实现转换成非递归实现一般需要两步工作(1). 自己建立“堆栈(一些局部变量)”来保存这些内容以便代替系统栈比如树的三种非递归遍历方式(2). 把对递归的调用转变为对循环处理。特别地在下文中我们将给出递归算法的一些经典应用案例对于这些案例的实现我们一般会给出递归和非递归两种解决方案以便读者体会。四. 经典递归问题实战第一类问题问题的定义是按递归定义的(1). 阶乘/*** Title: 阶乘的实现* Description:* 递归解法* 非递归解法*author rico*/public class Factorial {/***description 阶乘的递归实现*author rico*created 2017年5月10日 下午8:45:48*param n*return*/public static long f(int n){if(n 1) // 递归终止条件return 1; // 简单情景return n*f(n-1); // 相同重复逻辑缩小问题的规模}--------------------------------我是分割线-------------------------------------/***description 阶乘的非递归实现*author rico*created 2017年5月10日 下午8:46:43*param n*return*/public static long f_loop(int n) {long result n;while (n 1) {n--;result result * n;}return result;}}1(2). 斐波纳契数列/*** Title: 斐波纳契数列** Description: 斐波纳契数列又称黄金分割数列指的是这样一个数列1、1、2、3、5、8、13、21、……* 在数学上斐波纳契数列以如下被以递归的方法定义F00F11FnF(n-1)F(n-2)(n2n∈N*)。** 两种递归解法经典解法和优化解法* 两种非递归解法递推法和数组法** author rico*/public class FibonacciSequence {/***description 经典递归法求解** 斐波那契数列如下** 1,1,2,3,5,8,13,21,34,...** *那么计算fib(5)时需要计算1次fib(4),2次fib(3),3次fib(2)调用了2次fib(1)*即** fib(5) fib(4) fib(3)** fib(4) fib(3) fib(2) fib(3) fib(2) fib(1)** fib(3) fib(2) fib(1)** 这里面包含了许多重复计算而实际上我们只需计算fib(4)、fib(3)、fib(2)和fib(1)各一次即可* 后面的optimizeFibonacci函数进行了优化使时间复杂度降到了O(n).**author rico*created 2017年5月10日 下午12:00:42*param n*return*/public static int fibonacci(int n) {if (n 1 || n 2) { // 递归终止条件return 1; // 简单情景}return fibonacci(n - 1) fibonacci(n - 2); // 相同重复逻辑缩小问题的规模}——————————–我是分割线————————————-/*** description 对经典递归法的优化** 斐波那契数列如下** 1,1,2,3,5,8,13,21,34,...** 那么我们可以这样看fib(1,1,5) fib(1,2,4) fib(2,3,3) 5** 也就是说以1,1开头的斐波那契数列的第五项正是以1,2开头的斐波那契数列的第四项* 而以1,2开头的斐波那契数列的第四项也正是以2,3开头的斐波那契数列的第三项* 更直接地我们就可以一步到位fib(2,3,3) 2 3 5,计算结束。** 注意前两个参数是数列的开头两项第三个参数是我们想求的以前两个参数开头的数列的第几项。** 时间复杂度O(n)** author rico* param first 数列的第一项* param second 数列的第二项* param n 目标项* return*/public static int optimizeFibonacci(int first, int second, int n) {if (n 0) {if(n 1){ // 递归终止条件return first; // 简单情景}else if(n 2){ // 递归终止条件return second; // 简单情景}else if (n 3) { // 递归终止条件return first second; // 简单情景}return optimizeFibonacci(second, first second, n - 1); // 相同重复逻辑缩小问题规模}return -1;}--------------------------------我是分割线-------------------------------------/***description 非递归解法有去无回*author rico*created 2017年5月10日 下午12:03:04*param n*return*/public static int fibonacci_loop(int n) {if (n 1 || n 2) {return 1;}int result -1;int first 1; // 自己维护的栈,以便状态回溯int second 1; // 自己维护的栈,以便状态回溯for (int i 3; i n; i) { // 循环result first second;first second;second result;}return result;}--------------------------------我是分割线-------------------------------------/***description 使用数组存储斐波那契数列*author rico*param n*return*/public static int fibonacci_array(int n) {if (n 0) {int[] arr new int[n]; // 使用临时数组存储斐波纳契数列arr[0] arr[1] 1;for (int i 2; i n; i) { // 为临时数组赋值arr[i] arr[i-1] arr[i-2];}return arr[n - 1];}return -1;}}(3). 杨辉三角的取值/*** description 递归获取杨辉三角指定行、列(从0开始)的值* 注意与是否创建杨辉三角无关* author rico* x 指定行* y 指定列*//*** Title: 杨辉三角形又称Pascal三角形它的第i1行是(ab)i的展开式的系数。* 它的一个重要性质是三角形中的每个数字等于它两肩上的数字相加。** 例如下面给出了杨辉三角形的前4行* 1* 1 1* 1 2 1* 1 3 3 1*description 递归获取杨辉三角指定行、列(从0开始)的值* 注意与是否创建杨辉三角无关*author rico*x 指定行*y 指定列*/public static int getValue(int x, int y) {if(y x y 0){if(y 0 || x y){ // 递归终止条件return 1;}else{// 递归调用缩小问题的规模return getValue(x-1, y-1) getValue(x-1, y);}}return -1;}}(4). 回文字符串的判断/*** Title: 回文字符串的判断* Description: 回文字符串就是正读倒读都一样的字符串。如”98789”, “abccba”都是回文字符串** 两种解法* 递归判断* 循环判断** author rico*/public class PalindromeString {/***description 递归判断一个字符串是否是回文字符串*author rico*created 2017年5月10日 下午5:45:50*param s*return*/public static boolean isPalindromeString_recursive(String s){int start 0;int end s.length()-1;if(end start){ // 递归终止条件:两个指针相向移动当start超过end时完成判断if(s.charAt(start) ! s.charAt(end)){return false;}else{// 递归调用缩小问题的规模return isPalindromeString_recursive(s.substring(start1).substring(0, end-1));}}return true;}--------------------------------我是分割线-------------------------------------/***description 循环判断回文字符串*author rico*param s*return*/public static boolean isPalindromeString_loop(String s){char[] str s.toCharArray();int start 0;int end str.length-1;while(end start){ // 循环终止条件:两个指针相向移动当start超过end时完成判断if(str[end] ! str[start]){return false;}else{end --;start ;}}return true;}}(5). 字符串全排列递归解法/*** description 从字符串数组中每次选取一个元素作为结果中的第一个元素;然后对剩余的元素全排列* author rico* param s* 字符数组* param from* 起始下标* param to* 终止下标*/public static void getStringPermutations3(char[] s, int from, int to) {if (s ! null to from to s.length from 0) { // 边界条件检查if (from to) { // 递归终止条件System.out.println(s); // 打印结果} else {for (int i from; i to; i) {swap(s, i, from); // 交换前缀,作为结果中的第一个元素然后对剩余的元素全排列getStringPermutations3(s, from 1, to); // 递归调用缩小问题的规模swap(s, from, i); // 换回前缀复原字符数组}}}}/***description 对字符数组中的制定字符进行交换*author rico*param s*param from*param to*/public static void swap(char[] s, int from, int to) {char temp s[from];s[from] s[to];s[to] temp;}非递归解法(字典序全排列)/*** Title: 字符串全排列非递归算法(字典序全排列)* Description: 字典序全排列其基本思想是* 先对需要求排列的字符串进行字典排序即得到全排列中最小的排列.* 然后,找到一个比它大的最小的全排列一直重复这一步直到找到最大值,即字典排序的逆序列.** 不需要关心字符串长度** author rico*/public class StringPermutationsLoop {/*** description 字典序全排列** 设一个字符串(字符数组)的全排列有n个分别是A1,A2,A3,...,An** 1. 找到最小的排列 Ai* 2. 找到一个比Ai大的最小的后继排列Ai1* 3. 重复上一步直到没有这样的后继** 重点就是如何找到一个排列的直接后继:* 对于字符串(字符数组)a0a1a2……an,* 1. 从an到a0寻找第一次出现的升序排列的两个字符(即ai ai1),那么ai1是一个极值因为ai1之后的字符为降序排列记 topi1;* 2. 从top处(包括top)开始查找比ai大的最小的值aj记 minMax j;* 3. 交换minMax处和top-1处的字符;* 4. 翻转top之后的字符(包括top)即得到一个排列的直接后继排列** author rico* param s* 字符数组* param from* 起始下标* param to* 终止下标*/public static void getStringPermutations4(char[] s, int from, int to) {Arrays.sort(s,from,to1); // 对字符数组的所有元素进行升序排列即得到最小排列System.out.println(s);char[] descendArr getMaxPermutation(s, from, to); // 得到最大排列,即最小排列的逆序列while (!Arrays.equals(s, descendArr)) { // 循环终止条件迭代至最大排列if (s ! null to from to s.length from 0) { // 边界条件检查int top getExtremum(s, from, to); // 找到序列的极值int minMax getMinMax(s, top, to); // 从top处(包括top)查找比s[top-1]大的最小值所在的位置swap(s, top - 1, minMax); // 交换minMax处和top-1处的字符s reverse(s, top, to); // 翻转top之后的字符System.out.println(s);}}}/***description 对字符数组中的制定字符进行交换*author rico*param s*param from*param to*/public static void swap(char[] s, int from, int to) {char temp s[from];s[from] s[to];s[to] temp;}/***description 获取序列的极值*author rico*param s 序列*param from 起始下标*param to 终止下标*return*/public static int getExtremum(char[] s, int from, int to) {int index 0;for (int i to; i from; i--) {if (s[i] s[i - 1]) {index i;break;}}return index;}/***description 从top处查找比s[top-1]大的最小值所在的位置*author rico*created 2017年5月10日 上午9:21:13*param s*param top 极大值所在位置*param to*return*/public static int getMinMax(char[] s, int top, int to) {int index top;char base s[top-1];char temp s[top];for (int i top 1; i to; i) {if (s[i] base s[i] temp) {temp s[i];index i;}continue;}return index;}/***description 翻转top(包括top)后的序列*author rico*param s*param from*param to*return*/public static char[] reverse(char[] s, int top, int to) {char temp;while(top to){temp s[top];s[top] s[to];s[to] temp;top ;to --;}return s;}/***description 根据最小排列得到最大排列*author rico*param s 最小排列*param from 起始下标*param to 终止下标*return*/public static char[] getMaxPermutation(char[] s, int from, int to) {//将最小排列复制到一个新的数组中char[] dsc Arrays.copyOfRange(s, 0, s.length);int first from;int end to;while(end first){ // 循环终止条件char temp dsc[first];dsc[first] dsc[end];dsc[end] temp;first ;end --;}return dsc;}(6). 二分查找/*** description 二分查找的递归实现* author rico* param array 目标数组* param low 左边界* param high 右边界* param target 目标值* return 目标值所在位置*/public static int binarySearch(int[] array, int low, int high, int target) {//递归终止条件if(low high){int mid (low high) 1;if(array[mid] target){return mid 1; // 返回目标值的位置从1开始}else if(array[mid] target){// 由于array[mid]不是目标值因此再次递归搜索时可以将其排除return binarySearch(array, low, mid-1, target);}else{// 由于array[mid]不是目标值因此再次递归搜索时可以将其排除return binarySearch(array, mid1, high, target);}}return -1; //表示没有搜索到}--------------------------------我是分割线-------------------------------------/***description 二分查找的非递归实现*author rico*param array 目标数组*param low 左边界*param high 右边界*param target 目标值*return 目标值所在位置*/public static int binarySearchNoRecursive(int[] array, int low, int high, int target) {// 循环while (low high) {int mid (low high) 1;if (array[mid] target) {return mid 1; // 返回目标值的位置从1开始} else if (array[mid] target) {// 由于array[mid]不是目标值因此再次递归搜索时可以将其排除high mid -1;} else {// 由于array[mid]不是目标值因此再次递归搜索时可以将其排除low mid 1;}}return -1; //表示没有搜索到}第二类问题问题解法按递归算法实现(1). 汉诺塔问题/*** Title: 汉诺塔问题* Description:古代有一个梵塔塔内有三个座A、B、CA座上有64个盘子盘子大小不等大的在下小的在上。* 有一个和尚想把这64个盘子从A座移到C座但每次只能允许移动一个盘子并且在移动过程中3个座上的盘子始终保持大盘在下* 小盘在上。在移动过程中可以利用B座。要求输入层数运算后输出每步是如何移动的。** author rico*/public class HanoiTower {/***description 在程序中我们把最上面的盘子称为第一个盘子把最下面的盘子称为第N个盘子*author rico*param level盘子的个数*param from 盘子的初始地址*param inter 转移盘子时用于中转*param to 盘子的目的地址*/public static void moveDish(int level, char from, char inter, char to) {if (level 1) { // 递归终止条件System.out.println(从 from 移动盘子 level 号到 to);} else {// 递归调用将level-1个盘子从from移到inter(不是一次性移动每次只能移动一个盘子,其中to用于周转)moveDish(level - 1, from, to, inter); // 递归调用缩小问题的规模// 将第level个盘子从A座移到C座System.out.println(从 from 移动盘子 level 号到 to);// 递归调用将level-1个盘子从inter移到to,from 用于周转moveDish(level - 1, inter, from, to); // 递归调用缩小问题的规模}}public static void main(String[] args) {int nDisks 30;moveDish(nDisks, A, B, C);}第三类问题数据的结构是按递归定义的(1). 二叉树深度/*** Title: 递归求解二叉树的深度* Description:* author rico* created 2017年5月8日 下午6:34:50*/public class BinaryTreeDepth {/***description 返回二叉数的深度*author rico*param t*return*/public static int getTreeDepth(Tree t) {// 树为空if (t null) // 递归终止条件return 0;int left getTreeDepth(t.left); // 递归求左子树深度缩小问题的规模int right getTreeDepth(t.left); // 递归求右子树深度缩小问题的规模return left right ? left 1 : right 1;}}(2). 二叉树深度/*** description 前序遍历(递归)* author rico* created 2017年5月22日 下午3:06:11* param root* return*/public String preOrder(Node root) {StringBuilder sb new StringBuilder(); // 存到递归调用栈if (root null) { // 递归终止条件return ; // ji}else { // 递归终止条件sb.append(root.data ); // 前序遍历当前结点sb.append(preOrder(root.left)); // 前序遍历左子树sb.append(preOrder(root.right)); // 前序遍历右子树return sb.toString();}}
